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 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.
Code (0)
등록된 구현이 없습니다.
Tasks
DenoisingLow-Rank Matrix CompletionMatrix CompletionSimilar Papers 제목 키워드 기반
Obtaining 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 CompletionRobust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering
Consider the task of estimating a 3-order $n \times n \times n$ tensor from noisy observations of randomly chosen entries in the sparse regime. We introduce a similarity based collaborative filtering algorithm for estima…
Collaborative FilteringOn Universality of Deep Equivariant Networks
Universality results for equivariant neural networks remain rare. Those that do exist typically hold only in restrictive settings: either they rely on regular or higher-order tensor representations, leading to impractica…
Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
This paper is concerned with the problem of top-$K$ ranking from pairwise comparisons. Given a collection of $n$ items and a few pairwise comparisons across them, one wishes to identify the set of $K$ items that receive …
Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms
Sparse Principal Component Analysis (PCA) is a prevalent tool across a plethora of subfields of applied statistics. While several results have characterized the recovery error of the principal eigenvectors, these are typ…