Robust matrix completion

• 成果类型: Article
• 署名作者: Klopp, Olga; Lounici, Karim; Tsybakov, Alexandre B.
• 署名单位: Institut Polytechnique de Paris; ENSAE Paris; Universite Paris Saclay; University System of Georgia; Georgia Institute of Technology; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Humanities & Social Sciences (INSHS); Institut Polytechnique de Paris; ENSAE Paris
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-016-0736-y
• 发表日期: 2017
• 页码: 523-564
• 关键词: optimal rates; DECOMPOSITION

摘要

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.