Emmanuel J. Candès
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.
- Basri, R., and Jacobs, D. 2003. Lambertian reflectance and linear subspaces. IEEE Trans. Patt. Anal. Mach. Intel. 25, 2, 218--233. Google Scholar
Digital Library
- Beck, A., and Teboulle, M. 2009. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2, 1, 183--202. Google ScholarDigital Library
- Becker, S., Bobin, J., and Candès, E. J. 2011. NESTA: A fast and accuract first-order method for sparse recovery. SIAM J. Imag. Sci. 4, 1, 1--39. Google ScholarDigital Library
- Belkin, M., and Niyogi, P. 2003. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput. 15, 6, 1373--1396. Google ScholarDigital Library
- Bertsekas, D. 1982. Constrained Optimization and Lagrange Multiplier Method. Academic Press.Google Scholar
- Cai, J., Cand&esgrave;, E. J., and Shen, Z. 2010. A singular value thresholding algorithm for matrix completion. SIAM J. Optimiz. 20, 4, 1956--1982. Google ScholarDigital Library
- Candès, E. J., and Plan, Y. 2010. Matrix completion with noise. Proc. IEEE 98, 6, 925--936.Google ScholarCross Ref
- Candès, E. J., and Recht, B. 2009. Exact matrix completion via convex optimzation. Found. Comput. Math. 9, 717--772. Google ScholarDigital Library
- Candès, E. J., Romberg, J., and Tao, T. 2006. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory 52, 2, 489--509. Google ScholarDigital Library
- Candès, E. J., and Tao, T. 2010. The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inf. Theory 56, 5, 2053--2080. Google ScholarDigital Library
- Cevher, V., Sankaranarayanan, A., Duarte, M., Reddy, D., Baraniuk, R., and Chellappa, R. 2009. Compressive sensing for background subtraction. In Proceedings of the European Conference on Computer Vision (ECCV). Google ScholarDigital Library
- Chandrasekaran, V., Sanghavi, S., Parrilo, P., and Willsky, A. 2009. Rank-sparsity incoherence for matrix decomposition. Siam J. Optim., to appear http://arxiv.org/abs/0906.2220.Google Scholar
- Chen, S., Donoho, D., and Saunders, M. 2001. Atomic decomposition by basis pursuit. SIAM Rev. 43, 1, 129--159. Google ScholarDigital Library
- Dewester, S., Dumains, S., Landauer, T., Furnas, G., and Harshman, R. 1990. Indexing by latent semantic analysis. J. Soc. Inf. Sci. 41, 6, 391--407.Google ScholarCross Ref
- Eckart, C., and Young, G. 1936. The approximation of one matrix by another of lower rank. Psychometrika 1, 211--218.Google ScholarCross Ref
- Fazel, M., Hindi, H., and Boyd, S. 2003. Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices. In Proceedings of the American Control Conference 2156--2162.Google Scholar
- Fischler, M., and Bolles, R. 1981. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Comm. ACM 24, 381--385. Google ScholarDigital Library
- Georghiades, A., Belhumeur, P., and Kriegman, D. 2001. From few to many: Illumination cone models for face recognition under variable lighting and pose. IEEE Trans. Patt. Anal. Mach. Intel. 23, 6. Google ScholarDigital Library
- Gnanadesikan, R., and Kettenring, J. 1972. Robust estimates, residuals, and outlier detection with multiresponse data. Biometrics 28, 81--124.Google ScholarCross Ref
- Goldfarb, D., and Ma, S. 2009. Convergence of fixed point continuation algorithms for matrix rank minimization. http://arxiv.org/abs/0906.3499.Google Scholar
- Grant, M., and Boyd, S. 2009. CVX: Matlab software for disciplined convex programming (web page and software). http://stanford.edu/~boyd/cvx.Google Scholar
- Gross, D. 2011. Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inf. Theory 57, 3, 1548--1566. Google ScholarDigital Library
- Gross, D., Liu, Y.-K., Flammia, S. T., Becker, S., and Eisert, J. 2010. Quantum state tomography via compressed sensing. Phys. Rev. Lett. 105, 15.Google ScholarCross Ref
- Hey, T., Tansley, S., and Tolle, K. 2009. The Fourth Paradigm: Data-Intensive Scientific Discovery. Microsoft Research.Google Scholar
- Hotelling, H. 1933. Analysis of a complex of statistical variables into principal components. J. Educat. Psych. 24, 417--441.Google ScholarCross Ref
- Huber, P. 1981. Robust Statistics. Wiley.Google Scholar
- Jolliffe, I. 1986. Principal Component Analysis. Springer-Verlag.Google Scholar
- Ke, Q., and Kanade, T. 2005. Robust ℓ<sup>1</sup>-norm factorization in the presence of outliers and missing data. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition. Google ScholarDigital Library
- Keshavan, R. H., Montanari, A., and Oh, S. 2010. Matrix completion from a few entries. IEEE Trans. Inf. Theory 56, 6, 2980--2998. Google ScholarDigital Library
- Kontogiorgis, S., and Meyer, R. 1989. A variable-penalty alternating direction method for convex optimization. Math. Prog. 83, 29--53. Google ScholarDigital Library
- Ledoux, M. 2001. The Concentration of Measure Phenomenon. American Mathematical Society.Google Scholar
- Li, L., Huang, W., Gu, I., and Tian, Q. 2004. Statistical modeling of complex backgrounds for foreground object detection. IEEE Trans. Image Proc. 13, 11, 1459--1472. Google ScholarDigital Library
- Lin, Z., Chen, M., and Ma, Y. 2009a. The augmented Lagrange multiplier method for exact recovery of a corrupted low-rank matrices. http://arxiv.org/abs/1009.5055.Google Scholar
- Lin, Z., Ganesh, A., Wright, J., Wu, L., Chen, M., and Ma, Y. 2009b. Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. In Proceedings of the Symposium on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP).Google Scholar
- Lions, P., and Mercier, B. 1979. Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 6, 964--979.Google ScholarDigital Library
- Liu, Z., and Vandenberge, L. 2009. Interior-point method for nuclear norm approximation with application to system identification. SIAM J. Matrix Anal. Appl. 31, 3, 1235--1256. Google ScholarDigital Library
- Ma, S., Goldfarb, D., and Chen, L. 2009. Fixed point and Bregman iterative methods for matrix rank minimization. Math. Prog. Ser. A. DOI 10.1007/s10107-009-0306-5. Google ScholarDigital Library
- Nesterov, Y. 1983. A method of solving a convex programming problem with convergence rate O(1/k<sup>2</sup>). Soviet Math. Dokl. 27, 2, 372--376.Google Scholar
- Nesterov, Y. 2005. Smooth minimization of non-smooth functions. Math. Prog. 103, 1. Google ScholarDigital Library
- Nesterov, Y. 2007. Gradient methods for minimizing composite objective functions. Tech. rep. - CORE - Universite Catholique de Louvain.Google Scholar
- Netflix, Inc. The Netflix prize. http://www.netflixprize.com/.Google Scholar
- Osher, S., Burger, M., Goldfarb, D., Xu, J., and Yin, W. 2005. An iterative regularization method for total variation-based image restoration. Multi. Model. Simul. 4, 460--489.Google ScholarCross Ref
- Papadimitriou, C., Raghavan, P., Tamaki, H., and Vempala, S. 2000. Latent semantic indexing, a probabilistic analysis. J. Comput. Syst. Sci. 61, 2, 217--235. Google ScholarDigital Library
- Recht, B. 2009. A simpler approach to matrix completion. CoRR abs/0910.0651.Google Scholar
- Recht, B., Fazel, M., and Parillo, P. 2010. Guaranteed minimum rank solution of matrix equations via nuclear norm minimization. SIAM Rev. 52, 471--501. Google ScholarDigital Library
- Stauffer, C., and Grimson, E. 1999. Adaptive background mixture models for real-time tracking. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition.Google Scholar
- Tenenbaum, J., de Silva, V., and Langford, J. 2000. A global geometric framework for nonlinear dimensionality reduction. Science 290, 5500, 2319--2323.Google Scholar
- Toh, K. C., and Yun, S. 2010. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pac. J. Optim. 6, 615--640.Google Scholar
- Torre, F. D. L., and Black, M. 2003. A framework for robust subspace learning. Int. J. Comput. Vis. 54, 117--142. Google ScholarDigital Library
- Vershynin, R. 2011. Introduction to the non-asymptotic analysis of random matrices. http://www-personal.umich.edu/˜romanv/papers/non-asymptotic-rmt-plain.pdf.Google Scholar
- Yin, W., Hale, E., and Zhang, Y. 2008a. Fixed-point continuation for ℓ<sup>1</sup>-minimization: Methodology and convergence. SIAM J. Optimiz. 19, 3, 1107--1130. Google ScholarDigital Library
- Yin, W., Osher, S., Goldfarb, D., and Darbon, J. 2008b. Bregman iterative algorithms for ℓ1-minimization with applications to compressed sensing. SIAM J. Imag. Sci. 1, 1, 143--168. Google ScholarDigital Library
- Yuan, X., and Yang, J. 2009. Sparse and low-rank matrix decomposition via alternating direction methods. http://www.optimization-online.org/08_HTML/2009/11/2447.html.Google Scholar
- Zhou, Z., Wagner, A., Mobahi, H., Wright, J., and Ma, Y. 2009. Face recognition with contiguous occlusion using Markov random fields. In Proceedings of the International Conference on Computer Vision (ICCV).Google Scholar
Index Terms
- Robust principal component analysis?
Recommendations
Robust principal component analysis via capped norms
KDD '13: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data miningIn many applications such as image and video processing, the data matrix often possesses simultaneously a low-rank structure capturing the global information and a sparse component capturing the local information. How to accurately extract the low-rank ...
Robust Q-mode principal component analysis in L1
We propose principal component analysis (PCA) of a data set based on the L"1-norm. We distinguish between Q-mode and R-mode analyses. The Q-mode L"1 principal components are sequentially calculated by an enumeration procedure. We show that the Q-mode L"...
Robust block tensor principal component analysis
Highlights- The robust block tensor principle component analysis is proposed to extract the low-rank and sparse components in block tensors for a good analysis scale.
AbstractRobust tensor principal component analysis based on tensor singular value decomposition (t-SVD) is a very effective tool to extract the low rank and sparse components in multi-way signals. In this paper, instead of the tensor nuclear ...
Reviews
Jan De Beule
Consider a matrix M , such that M = L 0 + S 0, where L 0 is supposed to have low rank, and S 0 is supposed to be sparse. An interesting question, also motivated by numerous applications described in the paper, is whether one can efficiently reconstruct L 0 and S 0 if only M is given. The authors describe a procedure, called principal component pursuit (PCP), that recovers L 0 and S 0 exactly, under certain assumptions. One theorem clearly states the procedure, together with its necessary assumptions. The paper contains not only a mathematical description of PCP, but also a section describing numerical experiments using real-life data. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments