Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions

Abstract

We analyze a class of estimators based on convex relaxation for solving high-dimensional matrix decomposition problems. The observations are noisy realizations of a linear transformation $\mathfrak{X}$ of the sum of an approximately) low rank matrix ${\Theta }^{\star }$ with a second matrix ${\Gamma }^{\star }$ endowed with a complementary form of low-dimensional structure; this set-up includes many statistical models of interest, including factor analysis, multi-task regression, and robust covariance estimation. We derive a general theorem that bounds the Frobenius norm error for an estimate of the pair $({\Theta }^{\star },{\Gamma }^{\star })$ obtained by solving a convex optimization problem that combines the nuclear norm with a general decomposable regularizer. Our results utilize a "spikiness" condition that is related to but milder than singular vector incoherence. We specialize our general result to two cases that have been studied in past work: low rank plus an entrywise sparse matrix, and low rank plus a columnwise sparse matrix. For both models, our theory yields non-asymptotic Frobenius error bounds for both deterministic and stochastic noise matrices, and applies to matrices ${\Theta }^{\star }$ that can be exactly or approximately low rank, and matrices ${\Gamma }^{\star }$ that can be exactly or approximately sparse. Moreover, for the case of stochastic noise matrices and the identity observation operator, we establish matching lower bounds on the minimax error. The sharpness of our predictions is confirmed by numerical simulations.

41 pages, 2 figures

References in corpus (3)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Two Proposals for Robust PCA using Semidefinite Programming

Cited by in corpus (29)

• Challenges of Big Data Analysis
• Focal onset seizure prediction using convolutional networks
• Incoherence-Optimal Matrix Completion
• Multiclass Classification Procedure for Detecting Attacks on MQTT-IoT Protocol
• Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank
• Recovery of Low-Rank Plus Compressed Sparse Matrices with Application to Unveiling Traffic Anomalies
• A Review of Modularization Techniques in Artificial Neural Networks
• Low Rank and Structured Modeling of High-dimensional Vector Autoregressions
• Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods
• Parametric Bilinear Generalized Approximate Message Passing
• Beyond Low Rank + Sparse: Multi-scale Low Rank Matrix Decomposition
• Robust PCA with Partial Subspace Knowledge
• Bilinear Recovery using Adaptive Vector-AMP
• Robust Kronecker Product PCA for Spatio-Temporal Covariance Estimation
• Adaptive estimation of the copula correlation matrix for semiparametric elliptical copulas
• 3D Axial-Attention for Lung Nodule Classification
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Recent Developments on Factor Models and its Applications in Econometric Learning
• Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis
• Detection of Block-Exchangeable Structure in Large-Scale Correlation Matrices
• A large covariance matrix estimator under intermediate spikiness regimes
• Rejoinder: Latent variable graphical model selection via convex optimization
• Discussion: Latent variable graphical model selection via convex optimization
• Improving Neural Network Generalization by Combining Parallel Circuits with Dropout
• Stochastic Weight Matrix-based Regularization Methods for Deep Neural Networks
• Online Inference for Mixture Model of Streaming Graph Signals with Non-White Excitation
• Statistical inference based on robust low-rank data matrix approximation
• Factor-Driven Network Informed Restricted Vector Autoregression
• Dynamic Matrix Recovery