Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.00578 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914626096070656 |
|---|---|
| author | Capponi, Agostino Stojnic, Mihailo |
| author_facet | Capponi, Agostino Stojnic, Mihailo |
| contents | We study the completion of approximately low rank matrices with entries missing not at random (MNAR). In the context of typical large-dimensional statistical settings, we establish a framework for the performance analysis of the nuclear norm minimization ($\ell_1^*$) algorithm. Our framework produces \emph{exact} estimates of the worst-case residual root mean squared error and the associated phase transitions (PT), with both exhibiting remarkably simple characterizations. Our results enable to {\it precisely} quantify the impact of key system parameters, including data heterogeneity, size of the missing block, and deviation from ideal low rankness, on the accuracy of $\ell_1^*$-based matrix completion. To validate our theoretical worst-case RMSE estimates, we conduct numerical simulations, demonstrating close agreement with their numerical counterparts. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_00578 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Exact Error in Matrix Completion: Approximately Low-Rank Structures and Missing Blocks Capponi, Agostino Stojnic, Mihailo Information Theory 62B10, 94A16, 62D10 We study the completion of approximately low rank matrices with entries missing not at random (MNAR). In the context of typical large-dimensional statistical settings, we establish a framework for the performance analysis of the nuclear norm minimization ($\ell_1^*$) algorithm. Our framework produces \emph{exact} estimates of the worst-case residual root mean squared error and the associated phase transitions (PT), with both exhibiting remarkably simple characterizations. Our results enable to {\it precisely} quantify the impact of key system parameters, including data heterogeneity, size of the missing block, and deviation from ideal low rankness, on the accuracy of $\ell_1^*$-based matrix completion. To validate our theoretical worst-case RMSE estimates, we conduct numerical simulations, demonstrating close agreement with their numerical counterparts. |
| title | Exact Error in Matrix Completion: Approximately Low-Rank Structures and Missing Blocks |
| topic | Information Theory 62B10, 94A16, 62D10 |
| url | https://arxiv.org/abs/2401.00578 |