Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling

arXiv:2403.00184v1 Announce Type: cross
Abstract: 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 …

abstract arxiv concerns cs.lg low matrix sampling set show stat.ml type uniform