Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Low-Rank Matrix CompletionMatrix CompletionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A Generalized Latent Factor Model Approach to Mixed-data Matrix Completion with Entrywise Consistency
Matrix completion is a class of machine learning methods that concerns the prediction of missing entries in a partially observed matrix. This paper studies matrix completion for mixed data, i.e., data involving mixed typ…
Collaborative FilteringMatrix CompletionEntry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows
Matrix completion tackles the task of predicting missing values in a low-rank matrix based on a sparse set of observed entries. It is often assumed that the observation pattern is generated uniformly at random or has a v…
Matrix CompletionMissing ValuesError-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion
We propose a general framework for reconstructing and denoising single entries of incomplete and noisy entries. We describe: effective algorithms for deciding if and entry can be reconstructed and, if so, for reconstruct…
DenoisingLow-Rank Matrix CompletionMatrix CompletionObtaining error-minimizing estimates and universal entry-wise error bounds for low-rank matrix completion
We propose a general framework for reconstructing and denoising single entries of incomplete and noisy entries. We describe: effective algorithms for deciding if and entry can be reconstructed and, if so, for reconstruct…
DenoisingLow-Rank Matrix CompletionMatrix CompletionThe Algebraic Combinatorial Approach for Low-Rank Matrix Completion
We present a novel algebraic combinatorial view on low-rank matrix completion based on studying relations between a few entries with tools from algebraic geometry and matroid theory. The intrinsic locality of the approac…
Low-Rank Matrix CompletionMatrix Completion