Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
Cited by 6,921

The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.

Robust principal component analysis?

Open access
Candès, Emmanuel J., Li, Xiaodong, Ma, Yi, Wright, John·2011·Journal of the ACM
DOI 10.1145/1970392.1970395
Open this paper in CoChat — free account

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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/1970392.1970395

Cites

4 of 4 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 4 references

Research works printed but not linked: 45

  1. 10.1109/TPAMI.2003.1177153 · DOI · Paper page
  2. 10.1137/090756855 · DOI · Paper page
  3. 10.1162/089976603321780317 · DOI · Paper page
  4. Bertsekas , D. 1982. Constrained Optimization and Lagrange Multiplier Method . Academic Press . Bertsekas, D. 1982. Constrained Optimization and Lagrange Multiplier Method. Academic Press.
  5. 10.1137/080738970 · DOI
  6. 10.1109/JPROC.2009.2035722 · DOI · Paper page
  7. 10.1007/s10208-009-9045-5 · DOI · Paper page
  8. 10.1109/TIT.2005.862083 · DOI · Paper page
  9. 10.1109/TIT.2010.2044061 · DOI · Paper page
  10. 10.1007/978-3-540-88688-4_12 · DOI · Paper page
  11. 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. 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. · arXiv
  12. 10.1137/S003614450037906X · DOI
  13. 10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9 · DOI
  14. 10.1007/BF02288367 · DOI
  15. 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 . 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.
  16. 10.1109/34.927464 · DOI · Paper page
  17. 10.2307/2528963 · DOI · Paper page
  18. Goldfarb D. and Ma S. 2009. Convergence of fixed point continuation algorithms for matrix rank minimization. http://arxiv.org/abs/0906.3499. Goldfarb D. and Ma S. 2009. Convergence of fixed point continuation algorithms for matrix rank minimization. http://arxiv.org/abs/0906.3499. · arXiv
  19. 10.1109/TIT.2011.2104999 · DOI
  20. 10.1103/PhysRevLett.105.150401 · DOI · Paper page
  21. 10.1037/h0071325 · DOI · Paper page
  22. Jolliffe , I. 1986. Principal Component Analysis . Springer-Verlag . Jolliffe, I. 1986. Principal Component Analysis. Springer-Verlag.
  23. 10.1109/CVPR.2005.309 · DOI · Paper page
  24. 10.1109/TIT.2010.2046205 · DOI · Paper page
  25. 10.1007/BF02680549 · DOI
  26. Ledoux , M. 2001. The Concentration of Measure Phenomenon . American Mathematical Society . Ledoux, M. 2001. The Concentration of Measure Phenomenon. American Mathematical Society.
  27. 10.1109/TIP.2004.836169 · DOI · Paper page
  28. 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. 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. · arXiv
  29. 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). 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).
  30. 10.1137/0716071 · DOI
  31. 10.1137/090755436 · DOI · Paper page
  32. 10.5555/3112668.3113011 · doi:10.5555/3112668.3113011
  33. Nesterov , Y. 1983 . A method of solving a convex programming problem with convergence rate O(1/k2) . Soviet Math. Dokl. 27 , 2, 372 -- 376 . Nesterov, Y. 1983. A method of solving a convex programming problem with convergence rate O(1/k2). Soviet Math. Dokl. 27, 2, 372--376.
  34. 10.1007/s10107-004-0552-5 · DOI
  35. 10.1137/040605412 · DOI · Paper page
  36. 10.1006/jcss.2000.1711 · DOI · Paper page
  37. Recht B. 2009. A simpler approach to matrix completion. CoRR abs/0910.0651. Recht B. 2009. A simpler approach to matrix completion. CoRR abs/0910.0651. · arXiv
  38. 10.1137/070697835 · DOI
  39. 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. 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.
  40. 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 . 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.
  41. 10.1023/A:1023709501986 · DOI · Paper page
  42. Vershynin R. 2011. Introduction to the non-asymptotic analysis of random matrices. http://www-personal.umich.edu/˜romanv/papers/non-asymptotic-rmt-plain.pdf. Vershynin R. 2011. Introduction to the non-asymptotic analysis of random matrices. http://www-personal.umich.edu/˜romanv/papers/non-asymptotic-rmt-plain.pdf. · DOI
  43. 10.1137/070698920 · DOI · Paper page
  44. 10.1137/070703983 · DOI · Paper page
  45. 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). 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).

Cited by

Metadata

Authors
Candès, E. J., Li, X., Ma, Y., & Wright, J.
Venue
Journal of the ACM
Publisher
Association for Computing Machinery (ACM)
Published
2011-05
Volume
58
Issue
3
Pages
1-37
ISSN
  • 0004-5411 (ISSN-L)
  • 1557-735X
DOI
10.1145/1970392.1970395
OpenAlex
W2145962650
Cited by
6,921
References
4
FWCI
357.14
Type
journal article
Language
en
Open access
green
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Funders
  • Office of Naval Research (N00014-09-1-0469N00014-08-1-0749N00014-09-1-0230)
  • Division of Electrical, Communications and Cyber Systems (IIS 08-49292ECCS 07-01676)
  • Division of Information and Intelligent Systems (IIS 08-49292ECCS 07-01676)

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.