Robust principal component analysis?
2011/05/01 by Emmanuel J. Candès, Xiaodong Li, Yi Ma +1 · 246 citations
Engineering · Computer Science · Mathematics · #Sparse and Compressive Sensing Techniques #Face and Expression Recognition #Mathematical Inequalities and Applications
paper · doi:10.1145/1970392.1970395
Abstract
This article is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program called Principal Component Pursuit ; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the ℓ 1 norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it offers a principled way of removing shadows and specularities in images of faces.
Citations
Cited by
- A Unifying Review of Deep and Shallow Anomaly Detection
- Heavy-Tailed Principal Component Analysis
- Projection Pursuit CPCANet for Domain Generalization
- Fast community detection by SCORE
- Dynamic Mode Decomposition and Its Variants
- Globally aligned Principal Component Analysis for multi-group data
- ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers
- A low-rank and sparse enhanced Tucker decomposition approach for tensor completion
- Koopman-Operator Spectral Decomposition for Nonlinear Motion Suppression in Dynamic Contrast-Enhanced MRI of the Head and Neck
- Joint Blind Deconvolution and Robust Principal Component Analysis for Blood Flow Estimation in Medical Ultrasound Imaging
- Synthetic Aperture Radar Imaging and Motion Estimation via Robust Principle Component Analysis
- Accounting for missing actors in interaction network inference from abundance data
- Higher spatial resolution and sensitivity in whole brain functional MRI at 7T using 3D EPI accelerated with variable density CAIPI sampling and temporal random walk
- Learning Hybrid Representation by Robust Dictionary Learning in Factorized Compressed Space
- Shape and Spatially-Varying Reflectance Estimation From Virtual Exemplars
- Joint Estimation of Low-Rank Components and Connectivity Graph in High-Dimensional Graph Signals: Application to Brain Imaging
- Robust High-Dimensional Linear Regression
- Weighted Low-Rank Approximation of Matrices and Background Modeling
- Provable Inductive Robust PCA via Iterative Hard Thresholding
- Interpretable Sparse Proximate Factors for Large Dimensions
- Large Covariance Estimation by Thresholding Principal Orthogonal\n Complements
- Automated quantitative analysis of first-pass myocardial perfusion magnetic resonance imaging data
- Learning Dependency Structures for Weak Supervision Models
- Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
- On the subdifferential of symmetric convex functions of the spectrum for symmetric and orthogonally decomposable tensors
- Thresholding based Efficient Outlier Robust PCA
- Alternating Direction Method of Multipliers for A Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction
- Approximating Optimal Transport via Low-rank and Sparse Factorization
- An ℓ∞ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation
- Stable Separation and Super-Resolution of Mixture Models
- Simultaneously Learning Neighborship and Projection Matrix for Supervised Dimensionality Reduction
- Principal Component Pursuit with Reduced Linear Measurements
- Proximal Markov chain Monte Carlo algorithms
- Soft Tensor Regression
- High Dimensional Data Decomposition for Anomaly Detection of Textured Images
- Distributed Estimation of Generalized Matrix Rank: Efficient Algorithms and Lower Bounds
- Alternating Direction Method of Multipliers for Nonlinear Matrix Decompositions
- Channel State Information Preprocessing for CSI-based Physical-Layer Authentication Using Reconciliation
- Data Aggregation Techniques for Internet of Things
- Fast and Robust LRSD-based SAR/ISAR Imaging and Decomposition
- A Generalized Structured Low-Rank Matrix Completion Algorithm for MR Image Recovery
- Improved Lite Audio-Visual Speech Enhancement
- Adaptive Estimation in Structured Factor Models with Applications to Overlapping Clustering
- Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics
- Deep Unfolding: Recent Developments, Theory, and Design Guidelines
- Structured signal recovery from non-linear and heavy-tailed measurements
- Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
- A Rank Revealing Factorization Using Arbitrary Norms
- Enhancing the Spatio-temporal Observability of Grid-Edge Resources in Distribution Grids
- Sketched SVD: Recovering Spectral Features from Compressive Measurements
- Solving Principal Component Pursuit in Linear Time via l1 Filtering
- Being Robust (in High Dimensions) Can Be Practical
- An Overview on Data Representation Learning: From Traditional Feature Learning to Recent Deep Learning
- Online Algorithms for Factorization-Based Structure from Motion
- DeepFTSG: Multi-stream Asymmetric USE-Net Trellis Encoders with Shared Decoder Feature Fusion Architecture for Video Motion Segmentation
- Optimal Spectral Recovery of a Planted Vector in a Subspace
- Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning
- Variational Analysis of the Ky Fan k-norm
- PCA++: How Uniformity Induces Robustness to Background Noise in Contrastive Learning
- PCA recovery thresholds in low-rank matrix inference with sparse noise
- Disentangling Emotional Bases and Transient Fluctuations: A Low-Rank Sparse Decomposition Approach for Video Affective Analysis
- New perturbation bounds for low rank approximation of matrices: Beyond Eckart-Young-Mirsky
- Online Subspace Learning on Flag Manifolds for System Identification
- The Usual Suspects? Reassessing Blame for VAE Posterior Collapse
- Proximal Markov chain Monte Carlo algorithms
- Projections onto Spectral Matrix Cones
- Hyper RPCA: Joint Maximum Correntropy Criterion and Laplacian Scale Mixture Modeling On-the-Fly for Moving Object Detection
- Incremental Methods for Weakly Convex Optimization
- Deep Learning for Anomaly Detection: A Review
- An L1 Penalty Method for General Obstacle Problems
- Contextual Deconvolution for Variance-Stable Demand Sensing: Kernel-Modulated Operators in Promotional Retail
- Geometry of First-Order Methods and Adaptive Acceleration
- Classification-Based Anomaly Detection for General Data
- Robust Reduced Rank Regression
- SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization
- Additive Tensor Decomposition Considering Structural Data Information
- Nuclear Norm based Matrix Regression with Applications to Face Recognition with Occlusion and Illumination Changes
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified\n Geometric Analysis
- Provable Low Rank Phase Retrieval
- Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants
- A Multi-criteria Approach for Fast and Outlier-aware Representative Selection from Manifolds
- Latent Variable Modeling with Diversity-Inducing Mutual Angular Regularization
- Robust Sparse Linear Discriminant Analysis
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- RUAN: Residual U-shaped attention network to approximate Taylor expansion for image denoising
- Novelty Detection via Robust Variational Autoencoding
- Accelerated Alternating Direction Method of Multipliers: an Optimal O(1/K) Nonergodic Analysis
- Outlier-robust sparse/low-rank least-squares regression and robust\n matrix completion
- Deep Low-rank plus Sparse Network for Dynamic MR Imaging
- An alternating direction method with increasing penalty for stable principal component pursuit
- Informative Data Projections: A Framework and Two Examples
- On the computational and statistical complexity of over-parameterized matrix sensing
- Multi-Resolution Dynamic Mode Decomposition
- An adaptive spatiotemporal tensor reconstruction method for GIMMS-3g+ NDVI
- L1-norm minimization for quaternion signals
- Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
- A Computationally Efficient Method for Learning Exponential Family\n Distributions
- Joint Featurewise Weighting and Lobal Structure Learning for Multi-view Subspace Clustering
- Algorithms and Hardness for Robust Subspace Recovery
- CellMCD+: An improved outlier-resistant cellwise minimum covariance determinant method
- Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems
- Haplotype Assembly: An Information Theoretic View
- Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation
- A novel speech enhancement method based on constrained low-rank and sparse matrix decomposition
- Video Processing from Electro-optical Sensors for Object Detection and Tracking in Maritime Environment: A Survey
- Binary component decomposition Part II: The asymmetric case
- First Study on Data Readiness Level
- An equivalence between critical points for rank constraints versus low-rank factorizations
- Graphical model for tensor factorization by sparse sampling
- Completing Any Low-rank Matrix, Provably
- Variable Projected Augmented Lagrangian Methods for Generalized Lasso Problems
- A Correctness Result for Online Robust PCA
- Doubly Smoothed Density Estimation with Application on Miners' Unsafe Act Detection
- Interventional Few-Shot Learning
- Stable Camera Motion Estimation Using Convex Programming
- Robust Rank Estimation for Noisy Matrices
- Convergence analysis of a relaxed inertial alternating minimization algorithm with applications
- Rethinking PCA Through Duality
- Locally upper Lipschitz of the perturbed KKT system of Ky Fan k-norm matrix conic optimization problems
- Complex best r-term approximations almost always exist in finite dimensions
- Attention Strongly Modulates Reliability of Neural Responses to Naturalistic Narrative Stimuli
- A useful variant of the Davis--Kahan theorem for statisticians
- Simple and practical algorithms for ℓp-norm low-rank approximation
- Image Denoising Using Low Rank Minimization With Modified Noise Estimation
- Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
- Simplifying Optimal Transport through Schatten-p Regularization
- Clipped Matrix Completion: A Remedy for Ceiling Effects
- Robust High Dimensional Sparse Regression and Matching Pursuit
- Color Face Recognition using High-Dimension Quaternion-based Adaptive Representation
- Quadric Hypersurface Intersection for Manifold Learning in Feature Space
- Concentration for matrix martingales in continuous time and microscopic\n activity of social networks
- Exact Subspace Segmentation and Outlier Detection by Low-Rank Representation
- Robust PCA by Manifold Optimization
- ENLighten: Lighten the Transformer, Enable Efficient Optical Acceleration
- Transformed ℓ1 Regularizations for Robust Principal Component Analysis: Toward a Fine-Grained Understanding
- Stochastic Parallel Block Coordinate Descent for Large-scale Saddle Point Problems
- An Extragradient-Based Alternating Direction Method for Convex Minimization
- Unsupervised Unfolded rPCA (U2-rPCA): Deep Interpretable Clutter Filtering for Ultrasound Microvascular Imaging
- Advanced Dimensionality Reduction for Imaging Mass Spectrometry of Human Eye Tissue through Low-Rank Modeling with Sparse and Dense Residuals
- Sketching Low-Rank Plus Diagonal Matrices
- Coarse-to-Fine Salient Object Detection with Low-Rank Matrix Recovery
- On the Convergence of Learning-based Iterative Methods for Nonconvex Inverse Problems
- Diagnosis of Intelligent Reflecting Surface in Millimeter-wave Communication Systems
- Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
- Exact recoverability from dense corrupted observations via L1 minimization
- Tensor Full Feature Measure and Its Nonconvex Relaxation Applications to Tensor Recovery
- Mixture Models, Robustness, and Sum of Squares Proofs
- Community Recovery in Graphs with Locality
- Robust Matrix Decomposition with Outliers
- Fixed-Rank Representation for Unsupervised Visual Learning
- Convex Optimization without Projection Steps
- A Single Image Is All You Need: Zero-Shot Anomaly Localization Without Training Data
- Low rank plus sparse decomposition of synthetic aperture radar data for target imaging and tracking
- On the Runtime-Efficacy Trade-off of Anomaly Detection Techniques for Real-Time Streaming Data
- Robust high dimensional factor models with applications to statistical machine learning
- Learning Robust Subspace Clustering
- Face frontalization for Alignment and Recognition
- L1-norm regularized L1-norm best-fit line problem
- Enhanced Principal Component Analysis under A Collaborative-Robust Framework
- TimeCluster with PCA is Equivalent to Subspace Identification of Linear Dynamical Systems
- A Block Lanczos with Warm Start Technique for Accelerating Nuclear Norm Minimization Algorithms
- Image Segmentation Using Subspace Representation and Sparse\n Decomposition
- RANSAC Algorithms for Subspace Recovery and Subspace Clustering
- Simultaneous Low-rank Component and Graph Estimation for High-dimensional Graph Signals: Application to Brain Imaging
- Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation
- On the Robust PCA and Weiszfeld's Algorithm
- Lightweight Deep Unfolding Networks with Enhanced Robustness for Infrared Small Target Detection
- Low Rank Approximation with Entrywise ℓ1-Norm Error
- Learning to Detect Instantaneous Changes with Retrospective Convolution and Static Sample Synthesis
- Tackling the Noisy Elephant in the Room: Label Noise-robust Out-of-Distribution Detection via Loss Correction and Low-rank Decomposition
- Robust and Adaptive Spectral Method for Representation Multi-Task Learning with Contamination
- ADMM for Multiaffine Constrained Optimization
- Point Cloud Denoising via Moving RPCA
- Nonparametric Bayesian Factor Analysis for Dynamic Count Matrices
- Learning Transformations for Clustering and Classification
- Sparse Representation based Multi-sensor Image Fusion: A Review
- Group Lasso with Overlaps: the Latent Group Lasso approach
- An Overview of Lead and Accompaniment Separation in Music
- Fast Proximal Linearized Alternating Direction Method of Multiplier with Parallel Splitting
- One Size Does Not Fit All: Multi-Scale, Cascaded RNNs for Radar Classification
- Deep Unfolding with Approximated Computations for Rapid Optimization
- Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning
- A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
- Accelerated Proximal Dogleg Majorization for Sparse Regularized Quadratic Optimization Problem
- QR-LoRA: QR-Based Low-Rank Adaptation for Efficient Fine-Tuning of Large Language Models
- Convex optimization for the planted k-disjoint-clique problem
- Detecting approximate replicate components of a high-dimensional random vector with latent structure
- GODS: Generalized One-class Discriminative Subspaces for Anomaly Detection
- Network Representation Learning: From Traditional Feature Learning to Deep Learning
- Efficient Rank Minimization via Solving Non-convexPenalties by Iterative Shrinkage-Thresholding Algorithm
- Speech Enhancement based on Denoising Autoencoder with Multi-branched Encoders
- Learning from Untrusted Data
- Deep Unrolling for Nonconvex Robust Principal Component Analysis
- On the Estimation of Coherence
- Compressed Randomized UTV Decompositions for Low-Rank Approximations and Big Data Applications
- Randomized Rank-Revealing UZV Decomposition for Low-Rank Approximation of Matrices
- A Hybrid Algorithm for Convex Semidefinite Optimization
- Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
- Local Search Algorithms for Rank-Constrained Convex Optimization
- Efficient Online Minimization for Low-Rank Subspace Clustering
- Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
- Efficient GPU-Centered Singular Value Decomposition Using the Divide-and-Conquer Method
- Robust and Explainable Autoencoders for Unsupervised Time Series Outlier Detection---Extended Version
- A Unified Framework for Sparse Relaxed Regularized Regression: SR3
- Efficient adaptive randomized algorithms for fixed-threshold low-rank matrix approximation
- Gromov-Wasserstein Factorization Models for Graph Clustering
- The synthetic instrument: from sparse association to sparse causation
- Generalized Categorization Axioms
- Single-Step Reconstruction-Free Anomaly Detection and Segmentation via Diffusion Models
- RPCANet++: Deep Interpretable Robust PCA for Sparse Object Segmentation
- RDDPM: Robust Denoising Diffusion Probabilistic Model for Unsupervised Anomaly Segmentation
- LOST: Low-rank and Sparse Pre-training for Large Language Models
- Non-convex Robust PCA
- Guided Variational Autoencoder for Disentanglement Learning
- Don't Blame the ELBO! A Linear VAE Perspective on Posterior Collapse
- Anomaly Detection via Graphical Lasso
- Learning Competitive and Discriminative Reconstructions for Anomaly Detection
- Model compression as constrained optimization, with application to neural nets. Part V: combining compressions
- Deep Anomaly Detection Using Geometric Transformations
- Structure Learning with Similarity Preserving
- Robust Sparse Reduced Rank Regression in High Dimensions
- Robust Low-Complexity Randomized Methods for Locating Outliers in Large Matrices
- PCA in Data-Dependent Noise (Correlated-PCA): Nearly Optimal Finite Sample Guarantees
- Fast and Robust Fixed-Rank Matrix Recovery
- ADAGIO: Fast Data-aware Near-Isometric Linear Embeddings
- Robust Fusion of Multi-Band Images with Different Spatial and Spectral Resolutions for Change Detection
- Attention Strongly Modulates Reliability of Neural Responses to Naturalistic Narrative Stimuli. [europepmc]
- Accelerating 3D-T 1ρ mapping of cartilage using compressed sensing with different sparse and low rank models. [europepmc]
- Compressed sensing acceleration of biexponential 3D-T 1ρ relaxation mapping of knee cartilage. [europepmc]
- Tuning characteristics of low-frequency EEG to positions and velocities in visuomotor and oculomotor tracking tasks. [europepmc]
- A Novel Sparse Compositional Technique Reveals Microbial Perturbations. [europepmc]
- Animal Scanner: Software for classifying humans, animals, and empty frames in camera trap images. [europepmc]
- The utility of multivariate outlier detection techniques for data quality evaluation in large studies: an application within the ONDRI project. [europepmc]
- Accelerated mono- and biexponential 3D-T1ρ relaxation mapping of knee cartilage using golden angle radial acquisitions and compressed sensing. [europepmc]
- Motion correction of chemical exchange saturation transfer MRI series using robust principal component analysis (RPCA) and PCA. [europepmc]
- Quantification of Morphological Features in Non-Contrast-Enhanced Ultrasound Microvasculature Imaging. [europepmc]
- Comprehensive Review of Vision-Based Fall Detection Systems. [europepmc]
- Data-driven cardiovascular flow modelling: examples and opportunities. [europepmc]
- Transcranial photobiomodulation and thermal stimulation induce distinct topographies of EEG alpha and beta power changes in healthy humans. [europepmc]
- MS-MDA: Multisource Marginal Distribution Adaptation for Cross-Subject and Cross-Session EEG Emotion Recognition. [europepmc]
- Synergies are minimally affected during emulation of cerebral palsy gait patterns. [europepmc]
- In vivo lensless microscopy via a phase mask generating diffraction patterns with high-contrast contours. [europepmc]
- Stability of sensorimotor network sculpts the dynamic repertoire of resting state over lifespan. [europepmc]
- EEG-Based Alzheimer's Disease Recognition Using Robust-PCA and LSTM Recurrent Neural Network. [europepmc]
- Neuromodulation of brain power topography and network topology by prefrontal transcranial photobiomodulation. [europepmc]
- Principal Component Pursuit for Pattern Identification in Environmental Mixtures. [europepmc]
- Multi-Step Extracellular Matrix Remodelling and Stiffening in the Development of Idiopathic Pulmonary Fibrosis. [europepmc]
- Whole-brain imaging of freely-moving zebrafish. [europepmc]
- Automatic Analysis of MRI Images for Early Prediction of Alzheimer's Disease Stages Based on Hybrid Features of CNN and Handcrafted Features. [europepmc]
- Quantitative 3D structural analysis of small colloidal assemblies under native conditions by liquid-cell fast electron tomography. [europepmc]
- Biosensors, Artificial Intelligence Biosensors, False Results and Novel Future Perspectives. [europepmc]
Related