Error-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion
Abstract
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-art Nuclear Norm and OptSpace methods.
Cite
Text
Kiraly and Theran. "Error-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion." Neural Information Processing Systems, 2013.Markdown
[Kiraly and Theran. "Error-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion." Neural Information Processing Systems, 2013.](https://mlanthology.org/neurips/2013/kiraly2013neurips-errorminimizing/)BibTeX
@inproceedings{kiraly2013neurips-errorminimizing,
title = {{Error-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion}},
author = {Kiraly, Franz and Theran, Louis},
booktitle = {Neural Information Processing Systems},
year = {2013},
pages = {2364-2372},
url = {https://mlanthology.org/neurips/2013/kiraly2013neurips-errorminimizing/}
}