Obtaining error-minimizing estimates and universal entry-wise error bounds for low-rank matrix completion
This work addresses matrix completion for applications requiring precise entry-level accuracy, but it appears incremental as it builds on existing methods like Nuclear Norm and OptSpace.
The paper tackles the problem of reconstructing and denoising single entries in incomplete and noisy low-rank matrices, proposing algorithms that provide error-minimizing estimates and universal entry-wise error bounds, with results showing qualitative closeness to state-of-the-art methods like Nuclear Norm and OptSpace for rank-one matrices.
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 reconstructing and denoising it; and a priori bounds on the error of each entry, individually. In the noiseless case our algorithm is exact. For rank-one matrices, the new algorithm is fast, admits a highly-parallel implementation, and produces an error minimizing estimate that is qualitatively close to our theoretical and the state-of-the-are Nuclear Norm and OptSpace methods.