Low rank matrix recovery with adversarial sparse noise*

Abstract 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 ℓ 1 -bounded noise and sparse noise that can arbitrarily change an adversarially chosen ω -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 ω < 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.