Robust principal component analysis

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Robust Principal Component Analysis (RPCA) is a modification of the widely used statistical procedure Principal component analysis (PCA) which works well with respect to grossly corrupted observations. A number of different approaches exist for Robust PCA, including an idealized version of Robust PCA, which aims to recover a low-rank matrix L0 from highly corrupted measurements M = L0 +S0.[1] This decomposition in low-rank and sparse matrices can be achieved by techniques such as Principal Component Pursuit method (PCP,[1] Stable PCP,[2] Quantized PCP ,[3] Block based PCP,[4] and Local PCP.[5] Then, optimization methods are used such as the Augmented Lagrange Multiplier Method (ALM[6]), Alternating Direction Method (ADM[7]), Fast Alternating Minimization (FAM[8]) or Iteratively Reweighted Least Squares (IRLS [9][10][11]). Bouwmans and Zahzah have made a complete survey [12] in 2014.

Applications[edit]

RPCA has many real life important applications particularly when the data under study can naturally be modeled as a low-rank plus a sparse contribution. Following examples are inspired by contemporary challenges in computer science, and depending on the applications, either the low-rank component or the sparse component could be the object of interest:

Video Surveillance[edit]

Given a sequence of surveillance video frames, it is often required to identify the activities that stand out from the background. If we stack the video frames as columns of a matrix M, then the low-rank component L0 naturally corresponds to the stationary background and the sparse component S0 captures the moving objects in the foreground.[1] A systematic evaluation and comparative analysis of several algorithms on a large scale dataset in video surveillance can be found in a complete review.[12] (For more information: http://sites.google.com/site/rpcaforegrounddetection/)

Face Recognition[edit]

Images of a convex, Lambertian surface under varying illuminations span a low-dimensional subspace.[13] This is one of the reasons for effectiveness of low-dimensional models for imagery data. In particular, it is easy to approximate images of a human’s face by a low-dimensional subspace. To be able to correctly retrieve this subspace is crucial in many applications such as face recognition and alignment. It turns out that RPCA can be applied successfully to this problem to exactly recover the face.[1]

Resources, Datasets and Codes[edit]

University of Illinois Website[edit]

This website provides MATLAB packages to solve the RPCA optimization problem by different methods. All of the codes are Copyright 2009 Perception and Decision Lab, University of Illinois at Urbana-Champaign, and Microsoft Research Asia, Beijing. (For more information: http://perception.csl.illinois.edu/matrix-rank/sample_code.html)

BGS Website[edit]

The Background Subtraction Web Site (T. Bouwmans, Univ. La Rochelle, France) contains a full list of references on RPCA algorithms which can be applied to video surveillance, links to available datasets and codes. (For more information: http://sites.google.com/site/backgroundsubtraction/Home)

References[edit]

  1. ^ a b c d Emmanuel J. Candes; Xiaodong Li; Yi Ma; John Wright. "Robust Principal Component Analysis?". 
  2. ^ J. Wright; Y. Peng, Y. Ma, A. Ganesh, S. Rao (2009). "Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices by Convex Optimization". Neural Information Processing Systems, NIPS 2009. 
  3. ^ S. Becker; E. Candes, M. Grant (2011). "TFOCS: Flexible First-order Methods for Rank Minimization". Low-rank Matrix Optimization Symposium, SIAM Conference on Optimization. 
  4. ^ G. Tang; A. Nehorai (2011). "Robust principal component analysis based on low-rank and block-sparse matrix decomposition". Annual Conference on Information Sciences and Systems, CISS 2011. 
  5. ^ B. Wohlberg; R. Chartrand, J. Theiler (2012). "Local Principal Component Pursuit for Nonlinear Datasets". International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012. 
  6. ^ Z. Lin; M. Chen, L. Wu, Y. Ma (2009). "The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices". UIUC Technical Report. 
  7. ^ X. Yuan; J. Yang (2009). "Sparse and Low-Rank Matrix Decomposition via Alternating Direction Methods". Optimization Online. 
  8. ^ P. Rodríguez; B. Wohlberg (2013). "Fast Principal Component Pursuit Via Alternating Minimization". IEEE International Conference on Image Processing, ICIP 2013. 
  9. ^ C. Guyon; T. Bouwmans. E. Zahzah (2012). "Foreground Detection via Robust Low Rank Matrix Decomposition including Spatio-Temporal Constraint". International Workshop on Background Model Challenges, ACCV 2012. 
  10. ^ C. Guyon; T. Bouwmans. E. Zahzah (2012). "Foreground Detection via Robust Low Rank Matrix Factorization including Spatial Constraint with Iterative Reweighted Regression". International Conference on Pattern Recognition, ICPR 2012. 
  11. ^ C. Guyon; T. Bouwmans. E. Zahzah (2012). "Moving Object Detection via Robust Low Rank Matrix Decomposition with IRLS scheme". International Symposium on Visual Computing, ISVC 2012. 
  12. ^ a b T. Bouwmans; E. Zahzah (2014). "Robust PCA via Principal Component Pursuit: A Review for a Comparative Evaluation in Video Surveillance". Special Issue on Background Models Challenge, Computer Vision and Image Understanding. 
  13. ^ R. Basri; D. Jacobs. "Lambertian reflectance and linear subspaces".