The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices

Abstract

This paper proposes scalable and fast algorithms for solving the Robust PCA problem, namely recovering a low-rank matrix with an unknown fraction of its entries being arbitrarily corrupted. This problem arises in many applications, such as image processing, web data ranking, and bioinformatic data analysis. It was recently shown that under surprisingly broad conditions, the Robust PCA problem can be exactly solved via convex optimization that minimizes a combination of the nuclear norm and the ${\ell }^1$-norm . In this paper, we apply the method of augmented Lagrange multipliers (ALM) to solve this convex program. As the objective function is non-smooth, we show how to extend the classical analysis of ALM to such new objective functions and prove the optimality of the proposed algorithms and characterize their convergence rate. Empirically, the proposed new algorithms can be more than five times faster than the previous state-of-the-art algorithms for Robust PCA, such as the accelerated proximal gradient (APG) algorithm. Moreover, the new algorithms achieve higher precision, yet being less storage/memory demanding. We also show that the ALM technique can be used to solve the (related but somewhat simpler) matrix completion problem and obtain rather promising results too. We further prove the necessary and sufficient condition for the inexact ALM to converge globally. Matlab code of all algorithms discussed are available at http://perception.csl.illinois.edu/matrix-rank/home.html

Please cite "Zhouchen Lin, Risheng Liu, and Zhixun Su, Linearized Alternating Direction Method with Adaptive Penalty for Low Rank Representation, NIPS 2011." (available at arXiv:1109.0367) instead for a more general method called Linearized Alternating Direction Method This manuscript first appeared as University of Illinois at Urbana-Champaign technical report #UILU-ENG-09-2215 in October 2009 Zhouchen Lin, Risheng Liu, and Zhixun Su, Linearized Alternating Direction Method with Adaptive Penalty for Low Rank Representation, NIPS 2011. (available at http://arxiv.org/abs/1109.0367)

References in corpus (2)

• A Singular Value Thresholding Algorithm for Matrix Completion
• Low-rank matrix factorization with attributes

Cited by in corpus (262)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation
• Robust Low-rank Tensor Recovery: Models and Algorithms
• Bilinear Generalized Approximate Message Passing
• Smooth PARAFAC Decomposition for Tensor Completion
• Generalized Nonconvex Nonsmooth Low-Rank Minimization
• Learnable Manifold Alignment (LeMA) : A Semi-supervised Cross-modality Learning Framework for Land Cover and Land Use Classification
• Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
• Robust Face Recognition via Adaptive Sparse Representation
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Collaborative Representation based Classification for Face Recognition
• Incoherence-Optimal Matrix Completion
• Connections Between Nuclear Norm and Frobenius Norm Based Representations
• Discriminative Block-Diagonal Representation Learning for Image Recognition
• Fast Algorithms for Robust PCA via Gradient Descent
• Rain Removal in Traffic Surveillance: Does it Matter?
• Low-Rank Structure Learning via Log-Sum Heuristic Recovery
• Learning Deep CNN Denoiser Prior for Image Restoration
• Non-Convex Tensor Low-Rank Approximation for Infrared Small Target Detection
• Hankel Matrix Nuclear Norm Regularized Tensor Completion for $N$-dimensional Exponential Signals
• Randomized Matrix Decompositions using R
• Constructing a Non-Negative Low Rank and Sparse Graph with Data-Adaptive Features
• Non-convex Robust PCA
• Online Alternating Direction Method
• Online Robust Subspace Tracking from Partial Information
• Clustering Partially Observed Graphs via Convex Optimization
• Outlier Detection and Optimal Anchor Placement for 3D Underwater Optical Wireless Sensor Networks Localization
• Learning a Target Sample Re-Generator for Cross-Database Micro-Expression Recognition
• Efficient single pixel imaging in Fourier space
• Predicting shim gaps in aircraft assembly with machine learning and sparse sensing
• High Dimensional Low Rank plus Sparse Matrix Decomposition
• Sparse Signal Recovery via Generalized Entropy Functions Minimization
• Vandermonde Factorization of Hankel Matrix for Complex Exponential Signal Recovery -- Application in Fast NMR Spectroscopy
• Fixed-Rank Representation for Unsupervised Visual Learning
• Universal Matrix Completion
• Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods
• Fast Low-Rank Bayesian Matrix Completion with Hierarchical Gaussian Prior Models
• Linearized Alternating Direction Method with Adaptive Penalty and Warm Starts for Fast Solving Transform Invariant Low-Rank Textures
• A Tensor Approach to Learning Mixed Membership Community Models
• Robust Subspace Clustering with Compressed Data
• Provable Tensor Ring Completion
• Joint Embedding Learning and Low-Rank Approximation: A Framework for Incomplete Multi-view Learning
• De novo visual proteomics in single cells through pattern mining
• Sketched Subspace Clustering
• Quaternion-based bilinear factor matrix norm minimization for color image inpainting
• Subspace clustering using a symmetric low-rank representation
• Robust Rotation Synchronization via Low-rank and Sparse Matrix Decomposition
• Exactly Robust Kernel Principal Component Analysis
• A variational approach to stable principal component pursuit
• Learning Transformations for Clustering and Classification
• Improved Sparse Low-Rank Matrix Estimation
• Fast, Robust and Non-convex Subspace Recovery
• Generalized Singular Value Thresholding
• An MDL framework for sparse coding and dictionary learning
• Recovery of Low-Rank Matrices under Affine Constraints via a Smoothed Rank Function
• Weakly Supervised Vessel Segmentation in X-ray Angiograms by Self-Paced Learning from Noisy Labels with Suggestive Annotation
• Online Alternating Direction Method (longer version)
• Visual Processing by a Unified Schatten-$p$ Norm and ${\ell }_q$ Norm Regularized Principal Component Pursuit
• Online Structured Sparsity-based Moving Object Detection from Satellite Videos
• Singing Voice Separation and Vocal F0 Estimation based on Mutual Combination of Robust Principal Component Analysis and Subharmonic Summation
• Camera-trap images segmentation using multi-layer robust principal component analysis
• Robust PCA with Partial Subspace Knowledge
• Recovery of Future Data via Convolution Nuclear Norm Minimization
• Bilinear Recovery using Adaptive Vector-AMP
• On Geometric Analysis of Affine Sparse Subspace Clustering
• Polar $n$-Complex and $n$-Bicomplex Singular Value Decomposition and Principal Component Pursuit
• Solving Principal Component Pursuit in Linear Time via $l_1$ Filtering
• Domain Adaptations for Computer Vision Applications
• Structured and Unstructured Outlier Identification for Robust PCA: A Non iterative, Parameter free Algorithm
• Symmetric low-rank representation for subspace clustering
• Fast First-Order Methods for Stable Principal Component Pursuit
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Scalable Algorithms for Tractable Schatten Quasi-Norm Minimization
• Constrained Low-Rank Learning Using Least Squares-Based Regularization
• Adaptive Low-Rank Kernel Subspace Clustering
• Complex and Quaternionic Principal Component Pursuit and Its Application to Audio Separation
• A Survey on Matrix Completion: Perspective of Signal Processing
• Tensor Completion Algorithms in Big Data Analytics
• Joint Group Feature Selection and Discriminative Filter Learning for Robust Visual Object Tracking
• Completing Any Low-rank Matrix, Provably
• Non-Convex Rank Minimization via an Empirical Bayesian Approach
• Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection
• Low-rank matrix completion by Riemannian optimization---extended version
• Network Topology Mapping from Partial Virtual Coordinates and Graph Geodesics
• Background Subtraction via Generalized Fused Lasso Foreground Modeling
• Online Optimization in Dynamic Environments
• Robust Data Geometric Structure Aligned Close yet Discriminative Domain Adaptation
• Time Series Forecasting via Learning Convolutionally Low-Rank Models
• Non-Convex Rank Minimization via an Empirical Bayesian Approach
• Low-rank Matrix Recovery from Errors and Erasures
• Nuclear Norm based Matrix Regression with Applications to Face Recognition with Occlusion and Illumination Changes
• A Block Lanczos with Warm Start Technique for Accelerating Nuclear Norm Minimization Algorithms
• Value function approximation via low-rank models
• Hidden Talents of the Variational Autoencoder
• Principal Components and Regularized Estimation of Factor Models
• Developing Univariate Neurodegeneration Biomarkers with Low-Rank and Sparse Subspace Decomposition
• Temporal Graph Signal Decomposition
• A Fast Implementation of Singular Value Thresholding Algorithm using Recycling Rank Revealing Randomized Singular Value Decomposition
• Network Topology Mapping from Partial Virtual Coordinates and Graph Geodesics
• Big Data Analytics in Future Internet of Things
• Tensor-Ring Nuclear Norm Minimization and Application for Visual Data Completion
• MotionVideoGAN: A Novel Video Generator Based on the Motion Space Learned from Image Pairs
• L1-norm Error Function Robustness and Outlier Regularization
• Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy
• Multi-Image Matching via Fast Alternating Minimization
• SA-CNN: Dynamic Scene Classification using Convolutional Neural Networks
• Best Pair Formulation & Accelerated Scheme for Non-convex Principal Component Pursuit
• DeepFont: Identify Your Font from An Image
• Low Rank plus Sparse Decomposition of ODFs for Improved Detection of Group-level Differences and Variable Correlations in White Matter
• Link prediction for egocentrically sampled networks
• Deep Learning Approach for Matrix Completion Using Manifold Learning
• Some Software Packages for Partial SVD Computation
• Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints
• Large-Scale Low-Rank Matrix Learning with Nonconvex Regularizers
• On Unifying Multi-View Self-Representations for Clustering by Tensor Multi-Rank Minimization
• Sparse + Low Rank Decomposition of Annihilating Filter-based Hankel Matrix for Impulse Noise Removal
• Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
• Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory
• A Fast Algorithm for Cosine Transform Based Tensor Singular Value Decomposition
• Nonlocal Low-Rank Tensor Factor Analysis for Image Restoration
• Low-Rank Spatial Channel Estimation for Millimeter Wave Cellular Systems
• Multilayer Collaborative Low-Rank Coding Network for Robust Deep Subspace Discovery
• Weighted Low-Rank Approximation of Matrices and Background Modeling
• Estimation for bivariate quantile varying coefficient model
• Regularized Quantile Regression with Interactive Fixed Effects
• Matrix ALPS: Accelerated Low Rank and Sparse Matrix Reconstruction
• Weighted Singular Value Thresholding and its Application to Background Estimation
• Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems
• Quaternion matrix regression for color face recognition
• An Alternating Direction Method for Total Variation Denoising
• Learning Robust Subspace Clustering
• Bilinear Generalized Vector Approximate Message Passing
• Online Learning for Classification of Low-rank Representation Features and Its Applications in Audio Segment Classification
• An Efficient Approach for Cell Segmentation in Phase Contrast Microscopy Images
• Stacking Ensemble Learning in Deep Domain Adaptation for Ophthalmic Image Classification
• Trace Norm Regularized Tensor Classification and Its Online Learning Approaches
• Robust Kernelized Multi-View Self-Representations for Clustering by Tensor Multi-Rank Minimization
• Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation
• Multimodal Remote Sensing Benchmark Datasets for Land Cover Classification with A Shared and Specific Feature Learning Model
• Robust Low-Rank Subspace Segmentation with Semidefinite Guarantees
• Sparse And Low Rank Decomposition Based Batch Image Alignment for Speckle Reduction of retinal OCT Images
• Weighted Low Rank Approximation for Background Estimation Problems
• Accelerated Alternating Direction Method of Multipliers: an Optimal $O(1/K)$ Nonergodic Analysis
• Low-Rank Modeling and Its Applications in Image Analysis
• Optimal Schatten-q and Ky-Fan-k Norm Rate of Low Rank Matrix Estimation
• CAST: A Correlation-based Adaptive Spectral Clustering Algorithm on Multi-scale Data
• Fast algorithms for robust principal component analysis with an upper bound on the rank
• Greedy Approach for Low-Rank Matrix Recovery
• A Synchrophasor Data-driven Method for Forced Oscillation Localization under Resonance Conditions
• Sufficient Conditions for Low-rank Matrix Recovery, Translated from Sparse Signal Recovery
• Relaxed Majorization-Minimization for Non-smooth and Non-convex Optimization
• RPCA-Based High Resolution Through-the-Wall Human Motion Detection and Classification
• Nonconvex Approach for Sparse and Low-Rank Constrained Models with Dual Momentum
• Collaborative representation-based robust face recognition by discriminative low-rank representation
• Exploring Auxiliary Context: Discrete Semantic Transfer Hashing for Scalable Image Retrieval
• Low-Rank Matrix Recovery from Noise via an MDL Framework-based Atomic Norm
• ProPPA: A Fast Algorithm for ${\ell }_1$ Minimization and Low-Rank Matrix Completion
• Two-Dimensional Semi-Nonnegative Matrix Factorization for Clustering
• Moving target inference with hierarchical Bayesian models in synthetic aperture radar imagery
• MmWave MIMO Communication with Semi-Passive RIS: A Low-Complexity Channel Estimation Scheme
• Strongly Convex Programming for Exact Matrix Completion and Robust Principal Component Analysis
• Effective Image Retrieval via Multilinear Multi-index Fusion
• Block-Diagonal Sparse Representation by Learning a Linear Combination Dictionary for Recognition
• Robust Principal Component Analysis with Non-Sparse Errors
• Stable and Compact Face Recognition via Unlabeled Data Driven Sparse Representation-Based Classification
• Frequency-Weighted Robust Tensor Principal Component Analysis
• Multi-Feature Discrete Collaborative Filtering for Fast Cold-start Recommendation
• Matrix Completion with Prior Subspace Information via Maximizing Correlation
• Anomaly Detection via Graphical Lasso
• Dual Reweighted Lp-Norm Minimization for Salt-and-pepper Noise Removal
• Faster Matrix Completion Using Randomized SVD
• SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs
• Advanced Algorithms for Penalized Quantile and Composite Quantile Regression
• A generalized method toward drug-target interaction prediction via low-rank matrix projection
• High-Performance Out-of-core Block Randomized Singular Value Decomposition on GPU
• Multi-modal Fusion for Diabetes Mellitus and Impaired Glucose Regulation Detection
• Nonconvex Sparse Spectral Clustering by Alternating Direction Method of Multipliers and Its Convergence Analysis
• Dual Smoothing and Level Set Techniques for Variational Matrix Decomposition
• Low Rank Representation on Riemannian Manifold of Square Root Densities
• A Fast Factorization-based Approach to Robust PCA
• Subspace clustering based on low rank representation and weighted nuclear norm minimization
• Efficient Online Minimization for Low-Rank Subspace Clustering
• Robust Hashing for Multi-View Data: Jointly Learning Low-Rank Kernelized Similarity Consensus and Hash Functions
• Cognitive Deep Machine Can Train Itself
• A Fast Algorithm for a Weighted Low Rank Approximation
• ROML: A Robust Feature Correspondence Approach for Matching Objects in A Set of Images
• Cognitive Internet of Things: A New Paradigm beyond Connection
• Signal Recovery on Incoherent Manifolds
• Confidence-Constrained Maximum Entropy Framework for Learning from Multi-Instance Data
• Neighborhood Preserved Sparse Representation for Robust Classification on Symmetric Positive Definite Matrices
• Deep Pose Consensus Networks
• Efficient Neural Network Approximation of Robust PCA for Automated Analysis of Calcium Imaging Data
• Side Information for Face Completion: a Robust PCA Approach
• Fast, Parameter free Outlier Identification for Robust PCA
• Scalable Nuclear-norm Minimization by Subspace Pursuit Proximal Riemannian Gradient
• Network Reconstruction and Controlling Based on Structural Regularity Analysis
• Beyond Unfolding: Exact Recovery of Latent Convex Tensor Decomposition under Reshuffling
• Single-Channel Blind Source Separation for Singing Voice Detection: A Comparative Study
• Near-separable Non-negative Matrix Factorization with ${\ell }_1$- and Bregman Loss Functions
• Bilinear Factor Matrix Norm Minimization for Robust PCA: Algorithms and Applications
• Efficient Algorithms for Robust and Stable Principal Component Pursuit Problems
• Cross-Database Micro-Expression Recognition: A Benchmark
• Learning Hybrid Representation by Robust Dictionary Learning in Factorized Compressed Space
• Robust Face Recognition by Constrained Part-based Alignment
• A Group Norm Regularized Factorization Model for Subspace Segmentation
• Greedy Approach for Subspace Clustering from Corrupted and Incomplete Data
• Grant-Free Access via Bilinear Inference for Cell-Free MIMO with Low-Coherent Pilots
• Face Recognition via Locality Constrained Low Rank Representation and Dictionary Learning
• Learning from Ambiguously Labeled Face Images
• Matrix Completion Based Localization in the Internet of Things Network
• Recovery of Sparse and Low Rank Components of Matrices Using Iterative Method with Adaptive Thresholding
• Learning of Generalized Low-Rank Models: A Greedy Approach
• Image segmentation with superpixel-based covariance descriptors in low-rank representation
• Robust Sparse Coding via Self-Paced Learning
• Adaptive Feature Representation for Visual Tracking
• Low-Rank Subspaces in GANs
• Enhancing the Spatio-Temporal Observability of Residential Loads
• Online Optimization for Large-Scale Max-Norm Regularization
• The Sparse Reverse of Principal Component Analysis for Fast Low-Rank Matrix Completion
• Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants
• A Non-structural Representation Scheme for Articulated Shapes
• Convex Total Least Squares
• $l_1$-regularized Outlier Isolation and Regression
• Low Rank Regularization: A Review
• Thick Cloud Removal of Remote Sensing Images Using Temporal Smoothness and Sparsity-Regularized Tensor Optimization
• Scalable Iterative Algorithm for Robust Subspace Clustering
• Simultaneous Measurement Imputation and Outcome Prediction for Achilles Tendon Rupture Rehabilitation
• A Splitting Augmented Lagrangian Method for Low Multilinear-Rank Tensor Recovery
• Internet Traffic Matrix Structural Analysis Based on Multi-Resolution RPCA
• Low-rank SIFT: An Affine Invariant Feature for Place Recognition
• An Iteratively Re-weighted Method for Problems with Sparsity-Inducing Norms
• Online high rank matrix completion
• Infrared target tracking based on proximal robust principal component analysis method
• Learning Parameters for Weighted Matrix Completion via Empirical Estimation
• Multi-modal and frequency-weighted tensor nuclear norm for hyperspectral image denoising
• Low rank plus sparse decomposition of synthetic aperture radar data for target imaging and tracking
• Robust Dictionary based Data Representation
• Parallel Active Subspace Decomposition for Scalable and Efficient Tensor Robust Principal Component Analysis
• Pseudo-Bayesian Robust PCA: Algorithms and Analyses
• Low-rank Matrix Optimization Using Polynomial-filtered Subspace Extraction
• Nonparametric Estimation of Low Rank Matrix Valued Function
• Revisiting L21-norm Robustness with Vector Outlier Regularization
• Binary matrix completion with nonconvex regularizers
• Low Rank Quaternion Matrix Recovery via Logarithmic Approximation
• An iALM-ICA-based Anti-Jamming DS-CDMA Receiver for LMS Systems
• Fast greedy algorithm for subspace clustering from corrupted and incomplete data
• Superpixel-guided Discriminative Low-rank Representation of Hyperspectral Images for Classification
• Modal Regression based Structured Low-rank Matrix Recovery for Multi-view Learning
• Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers
• Fast and Robust Fixed-Rank Matrix Recovery
• Efficient Registration of Pathological Images: A Joint PCA/Image-Reconstruction Approach
• Partial Sum Minimization of Singular Values in Robust PCA: Algorithm and Applications
• A Robust Scheme for 3D Point Cloud Copy Detection
• Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy
• Low-rank representations with incoherent dictionary for face recognition
• Local Search Algorithms for Rank-Constrained Convex Optimization
• A survey of the noise-correcting tools for Dynamic Mode Decomposition
• Robust Orthogonal Complement Principal Component Analysis
• Dense Error Correction for Low-Rank Matrices via Principal Component Pursuit
• An Introduction to Robust Graph Convolutional Networks
• Decomposition of Longitudinal Deformations via Beltrami Descriptors