Low rank matrix recovery with adversarial sparse noise*

Many problems in data science can be treated as recovering a low-rank matrix from a small number of random linear measurements, possibly corrupted with adversarial noise and dense noise. Recently, a bunch of theories on variants of models have been developed for different noises, but with fewer theories on the adversarial noise. In this paper, we study low-rank matrix recovery problem from linear measurements perturbed by l (1)-bounded noise and sparse noise that can arbitrarily change an adversarially chosen omega-fraction of the measurement vector. For Gaussian measurements with nearly optimal number of measurements, we show that the nuclear-norm constrained least absolute deviation (LAD) can successfully estimate the ground-truth matrix for any omega < 0.239. Similar robust recovery results are also established for an iterative hard thresholding algorithm applied to the rank-constrained LAD considering geometrically decaying step-sizes, and the unconstrained LAD based on matrix factorization as well as its subgradient descent solver.

Automated summary

This paper investigates the problem of low-rank matrix recovery from linear measurements perturbed by l(1)-bounded noise and sparse noise. The study shows that the nuclear-norm constrained least absolute deviation (LAD) can successfully estimate the ground-truth matrix for specific conditions.