Robust matrix completion

By Olga Klopp, Karim Lounici, Alexandre B. Tsybakov. 2014

128 citations recorded by the source corpus.

This paper considers the problem of estimation of a low-rank matrix when most of its entries are not observed and some of the observed entries are corrupted. The observations are noisy realizations of a sum of a low-rank matrix, which we wish to estimate, and a second matrix having a complementary sparse structure such as elementwise sparsity or columnwise sparsity. We analyze a class of estimators obtained as solutions of a constrained convex optimization problem combining the nuclear norm penalty and a convex relaxation penalty for the sparse constraint. Our assumptions allow for simultaneous presence of random and deterministic patterns in the sampling scheme. We establish rates of convergence for the low-rank component from partial and corrupted observations in the presence of noise and we show that these rates are minimax optimal up to logarithmic factors.

Subfields: Biomedical Engineering, Computational Mechanics, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Mathematical Physics

Citations in the corpus

Data Poisoning Attacks on Factorization-Based Collaborative Filtering (2016, background): “In terms of collaborative filtering/matrix completion, there is another line of established research that focuses on robust matrix completion, in which a small portion of elements or rows in the underlying low-rank matrix is assumed to be arbitrarily perturbed [18, 19, 20, 21].”
Training Complex Models with Multi-Task Weak Supervision (2018, methodology): “Note that in the noisy case, we instead have the bound ‖O−1 Ω + (zz T )Ω‖∞ ≤ δA + kδB using our earlier conditions; this then leads to a noisy low-rank matrix completion problem, which can be tackled via robust matrix completion techniques [5; 21].”