Robust matrix completion

DOI10.1007/S00440-016-0736-YzbMATH Open1383.62167arXiv1412.8132OpenAlexW2963831709MaRDI QIDQ682808FDOQ682808

K. Lounici, Olga Klopp, Alexandre B. Tsybakov

Publication date: 5 February 2018

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: This paper considers the problem of recovery of a low-rank matrix in the situation when most of its entries are not observed and a fraction of observed entries are corrupted. The observations are noisy realizations of the sum of a low rank matrix, which we wish to recover, with a second matrix having a complementary sparse structure such as element-wise or column-wise sparsity. We analyze a class of estimators obtained by solving a constrained convex optimization problem that combines the nuclear norm and a convex relaxation for a sparse constraint. Our results are obtained for the simultaneous presence of random and deterministic patterns in the sampling scheme. We provide guarantees for recovery of low-rank and sparse components from partial and corrupted observations in the presence of noise and show that the obtained rates of convergence are minimax optimal.

Full work available at URL: https://arxiv.org/abs/1412.8132

Recommendations

• Robust low-rank matrix estimation
• Noisy low-rank matrix completion with general sampling distribution
• Structured matrix estimation and completion
• Exact matrix completion via convex optimization
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion

zbMATH Keywords

matrix completionsparsitylow-rank matrixconvex optimization problemestimators

Mathematics Subject Classification ID

Nonparametric robustness (62G35) Estimation in multivariate analysis (62H12)

Cites Work

• Matrix completion from noisy entries
• Statistics for high-dimensional data. Methods, theory and applications.
• Robust principal component analysis?
• Introduction to nonparametric estimation
• Hanson-Wright inequality and sub-Gaussian concentration
• Noisy low-rank matrix completion with general sampling distribution
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Estimation of high-dimensional low-rank matrices
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• Rank-Sparsity Incoherence for Matrix Decomposition
• Robust Matrix Decomposition With Sparse Corruptions
• Title not available (Why is that?)
• Noisy matrix decomposition via convex relaxation: optimal rates in high dimensions
• Robust PCA via Outlier Pursuit
• Compressed sensing and matrix completion with constant proportion of corruptions
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• A Simpler Approach to Matrix Completion
• Matrix completion via max-norm constrained optimization
• Absolute and monotonic norms

Cited In (23)

• Low-rank matrix recovery under heavy-tailed errors
• Outlier detection in networks with missing links
• Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries
• All-in-one robust estimator of the Gaussian mean
• Robust low-rank matrix estimation
• Nonlocal robust tensor recovery with nonconvex regularization ^*
• Tight risk bound for high dimensional time series completion
• High-dimensional VAR with low-rank transition
• A generalized non-convex method for robust tensor completion
• Title not available (Why is that?)
• Robust low-rank matrix completion by Riemannian optimization
• Matrix optimization based Euclidean embedding with outliers
• Matrix factorization for multivariate time series analysis
• Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss
• Multidimensional linear functional estimation in sparse Gaussian models and robust estimation of the mean
• Robust Tensor Completion: Equivalent Surrogates, Error Bounds, and Algorithms
• Optimal cleaning for singular values of cross-covariance matrices
• Compressed sensing of low-rank plus sparse matrices
• Main effects and interactions in mixed and incomplete data frames
• Detection thresholds in very sparse matrix completion
• Computing the Best Approximation over the Intersection of a Polyhedral Set and the Doubly Nonnegative Cone

This page was built for publication: Robust matrix completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q682808)