Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.00184 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916142914732032 |
|---|---|
| author | Xi, Xumei Yu, Christina Lee Chen, Yudong |
| author_facet | Xi, Xumei Yu, Christina Lee Chen, Yudong |
| contents | Low-rank matrix completion concerns the problem of estimating unobserved entries in a matrix using a sparse set of observed entries. We consider the non-uniform setting where the observed entries are sampled with highly varying probabilities, potentially with different asymptotic scalings. We show that under structured sampling probabilities, it is often better and sometimes optimal to run estimation algorithms on a smaller submatrix rather than the entire matrix. In particular, we prove error upper bounds customized to each entry, which match the minimax lower bounds under certain conditions. Our bounds characterize the hardness of estimating each entry as a function of the localized sampling probabilities. We provide numerical experiments that confirm our theoretical findings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_00184 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling Xi, Xumei Yu, Christina Lee Chen, Yudong Machine Learning Low-rank matrix completion concerns the problem of estimating unobserved entries in a matrix using a sparse set of observed entries. We consider the non-uniform setting where the observed entries are sampled with highly varying probabilities, potentially with different asymptotic scalings. We show that under structured sampling probabilities, it is often better and sometimes optimal to run estimation algorithms on a smaller submatrix rather than the entire matrix. In particular, we prove error upper bounds customized to each entry, which match the minimax lower bounds under certain conditions. Our bounds characterize the hardness of estimating each entry as a function of the localized sampling probabilities. We provide numerical experiments that confirm our theoretical findings. |
| title | Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2403.00184 |