Rank-Sparsity Incoherence for Matrix Decomposition

DOI10.1137/090761793zbMath1226.90067arXiv0906.2220OpenAlexW3104624268MaRDI QIDQ3093595

Pablo A. Parrilo, Alan S. Willsky, Sujay Sanghavi, Venkat Chandrasekaran

Publication date: 18 October 2011

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programminguncertainty principlerankconvex relaxationsparsitymatrix decompositionnuclear norm minimization\(\ell _1\) norm minimization

Mathematics Subject Classification ID

Semidefinite programming (90C22) Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59) System identification (93B30)

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Learning Gaussian graphical models with latent confounders, Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion, An efficient semi-proximal ADMM algorithm for low-rank and sparse regularized matrix minimization problems with real-world applications, Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs, Topology identification under spatially correlated noise, A separable surrogate function method for sparse and low-rank matrices decomposition, An Algebraic Estimator for Large Spectral Density Matrices, Large factor model estimation by nuclear norm plus \(\ell_1\) norm penalization, Active-learning-driven surrogate modeling for efficient simulation of parametric nonlinear systems, Multiple Change Point Detection in Reduced Rank High Dimensional Vector Autoregressive Models, Super-resolution of point sources via convex programming, Relations Among Some Low-Rank Subspace Recovery Models, Stochastic Model-Based Minimization of Weakly Convex Functions, Differential Covariance: A New Class of Methods to Estimate Sparse Connectivity from Neural Recordings, An Equivalence between Critical Points for Rank Constraints Versus Low-Rank Factorizations, Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization, On the Complexity of Recovering Incidence Matrices, A NEW MODEL FOR SPARSE AND LOW-RANK MATRIX DECOMPOSITION, A Sparse Decomposition of Low Rank Symmetric Positive Semidefinite Matrices, Median filtering‐based methods for static background extraction from surveillance video, Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Unnamed Item, Blind Source Separation with Outliers in Transformed Domains, A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA, A distributed Douglas-Rachford splitting method for multi-block convex minimization problems, A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers, Spectral Operators of Matrices: Semismoothness and Characterizations of the Generalized Jacobian, On the Complexity of Robust PCA and ℓ₁-Norm Low-Rank Matrix Approximation, Graphical Model Selection for Gaussian Conditional Random Fields in the Presence of Latent Variables, Accelerated Alternating Projections for Robust Principal Component Analysis, Isolated calmness of solution mappings and exact recovery conditions for nuclear norm optimization problems, Robust Causal Structure Learning with Some Hidden Variables, Exact Camera Location Recovery by Least Unsquared Deviations, An alternating minimization method for robust principal component analysis, Unnamed Item, Unnamed Item, Discussion: Latent variable graphical model selection via convex optimization, Discussion: Latent variable graphical model selection via convex optimization, Discussion: Latent variable graphical model selection via convex optimization, Discussion: Latent variable graphical model selection via convex optimization, Discussion: Latent variable graphical model selection via convex optimization, Unnamed Item, LOW-RANK AND SPARSE MATRIX RECOVERY FROM NOISY OBSERVATIONS VIA 3-BLOCK ADMM ALGORITHM, Robust CUR Decomposition: Theory and Imaging Applications, Unnamed Item, Distributed Stochastic Inertial-Accelerated Methods with Delayed Derivatives for Nonconvex Problems, Hierarchical subspace identification of directed acyclic graphs, Matrix Rigidity and the Ill-Posedness of Robust PCA and Matrix Completion, Adaptive estimation of the copula correlation matrix for semiparametric elliptical copulas, Variational analysis of the Ky Fan \(k\)-norm, Unbiased risk estimates for matrix estimation in the elliptical case, Alternating DC algorithm for partial DC programming problems, Two-stage convex relaxation approach to least squares loss constrained low-rank plus sparsity optimization problems, Deformable groupwise image registration using low-rank and sparse decomposition, Phaselift is robust to a constant fraction of arbitrary errors, Scalable Low-Rank Representation, Low-Rank and Sparse Multi-task Learning, Proximal Markov chain Monte Carlo algorithms, Regularized high dimension low tubal-rank tensor regression, Bayesian sparse covariance decomposition with a graphical structure, On conic QPCCs, conic QCQPs and completely positive programs, Low-Rank Inducing Norms with Optimality Interpretations, An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing, Applications of gauge duality in robust principal component analysis and semidefinite programming, New classes of matrix decompositions, Asymptotic performance of PCA for high-dimensional heteroscedastic data, Trading off \(1\)-norm and sparsity against rank for linear models using mathematical optimization: \(1\)-norm minimizing partially reflexive ah-symmetric generalized inverses, Alternating proximal gradient method for convex minimization, Multi-view low-rank dictionary learning for image classification, A partially isochronous splitting algorithm for three-block separable convex minimization problems, Complex best \(r\)-term approximations almost always exist in finite dimensions, PO-MOESP subspace identification of directed acyclic graphs with unknown topology, Pairwise sparse + low-rank models for variables of mixed type, Spectral operators of matrices, A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints, Large covariance estimation through elliptical factor models, The convex geometry of linear inverse problems, Nonsmooth rank-one matrix factorization landscape, TILT: transform invariant low-rank textures, Kronecker-structured covariance models for multiway data, Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution, Sharp recovery bounds for convex demixing, with applications, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Compressed sensing and matrix completion with constant proportion of corruptions, Compressive total variation for image reconstruction and restoration, Discussion: Latent variable graphical model selection via convex optimization, Rejoinder: Latent variable graphical model selection via convex optimization, An approximation theory of matrix rank minimization and its application to quadratic equations, Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games, Compressed sensing of low-rank plus sparse matrices, A multi-objective memetic algorithm for low rank and sparse matrix decomposition, An ADM-based splitting method for separable convex programming, From compression to compressed sensing, Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization, Convex optimization for the planted \(k\)-disjoint-clique problem, Two proposals for robust PCA using semidefinite programming, Proximity point algorithm for low-rank matrix recovery from sparse noise corrupted data, Noisy matrix decomposition via convex relaxation: optimal rates in high dimensions, Adaptive estimation in structured factor models with applications to overlapping clustering, Parameterized low-rank binary matrix approximation, Robust principal component analysis using facial reduction, A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints, Efficient algorithms for robust and stable principal component pursuit problems, An introduction to a class of matrix cone programming, A modified alternating projection based prediction-correction method for structured variational inequalities, Multi-stage convex relaxation method for low-rank and sparse matrix separation problem, Optimal rank-sparsity decomposition, An alternating direction method with increasing penalty for stable principal component pursuit, Statistical inference of semidefinite programming, Robust covariance estimation for approximate factor models, Outlier detection in networks with missing links, Interpreting latent variables in factor models via convex optimization, Robust low-rank matrix estimation, Robust matrix completion, Two-stage convex relaxation approach to low-rank and sparsity regularized least squares loss, Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset, A proximal fully parallel splitting method for stable principal component pursuit, An $\ell_{\infty}$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation, An extragradient-based alternating direction method for convex minimization, Sparse trace norm regularization, Unnamed Item, Recovering low-rank and sparse matrix based on the truncated nuclear norm, Sparse + low-energy decomposition for viscous conservation laws, Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach, Latent variable graphical model selection via convex optimization, Robust principal component pursuit via inexact alternating minimization on matrix manifolds, Practical matrix completion and corruption recovery using proximal alternating robust subspace minimization, Main effects and interactions in mixed and incomplete data frames, A large covariance matrix estimator under intermediate spikiness regimes, Matrix optimization based Euclidean embedding with outliers, Linear Models Based on Noisy Data and the Frisch Scheme, Fast global convergence of gradient methods for high-dimensional statistical recovery, Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data, Differential Covariance: A New Method to Estimate Functional Connectivity in fMRI, Linear Convergence of Descent Methods for the Unconstrained Minimization of Restricted Strongly Convex Functions, Scalable Robust Matrix Recovery: Frank--Wolfe Meets Proximal Methods, Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence, An adaptation for iterative structured matrix completion, Mixture augmented Lagrange multiplier method for tensor recovery and its applications, Alternating direction and Taylor expansion minimization algorithms for unconstrained nuclear norm optimization, Active Subspace: Toward Scalable Low-Rank Learning, A unified framework for nonconvex nonsmooth sparse and low-rank decomposition by majorization-minimization algorithm, Similarity preserving low-rank representation for enhanced data representation and effective subspace learning, Low-rank matrix completion via preconditioned optimization on the Grassmann manifold, Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates, Robust computation of linear models by convex relaxation, Rank-one and sparse matrix decomposition for dynamic MRI, Convex graph invariant relaxations for graph edit distance