nips nips2009 nips2009-208 nips2009-208-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, Yi Ma
Abstract: Principal component analysis is a fundamental operation in computational data analysis, with myriad applications ranging from web search to bioinformatics to computer vision and image analysis. However, its performance and applicability in real scenarios are limited by a lack of robustness to outlying or corrupted observations. This paper considers the idealized “robust principal component analysis” problem of recovering a low rank matrix A from corrupted observations D = A + E. Here, the corrupted entries E are unknown and the errors can be arbitrarily large (modeling grossly corrupted observations common in visual and bioinformatic data), but are assumed to be sparse. We prove that most matrices A can be efficiently and exactly recovered from most error sign-and-support patterns by solving a simple convex program, for which we give a fast and provably convergent algorithm. Our result holds even when the rank of A grows nearly proportionally (up to a logarithmic factor) to the dimensionality of the observation space and the number of errors E grows in proportion to the total number of entries in the matrix. A by-product of our analysis is the first proportional growth results for the related problem of completing a low-rank matrix from a small fraction of its entries. Simulations and real-data examples corroborate the theoretical results, and suggest potential applications in computer vision. 1
[1] C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211–218, 1936. 8
[2] S. Chen, D. Donoho, and M. Saunders. Atomic decomposition by basis pursuit. SIAM Review, 43(1):129– 159, 2001.
[3] J. Tenenbaum, V. de Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000.
[4] M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373–1396, 2003.
[5] I. Jolliffe. Principal Component Analysis. Springer-Verlag, New York, New York, 1986.
[6] P. Huber. Robust Statistics. Wiley, New York, New York, 1981.
[7] F. De La Torre and M. Black. A framework for robust subspace learning. IJCV, 54(1-3):117–142, 2003.
[8] R. Gnanadesikan and J. Kettenring. Robust estimates, residuals, and outlier detection with multiresponse data. Biometrics, 28(1):81–124, 1972.
[9] Q. Ke and T. Kanade. Robust l1 norm factorization in the presence of outliers and missing data by alternative convex programming. In CVPR, 2005.
[10] M. Fischler and R. Bolles. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6):381–385, 1981.
[11] E. Cand` s and T. Tao. Decoding by linear programming. IEEE Trans. Info. Thy., 51(12):4203–4215, e 2005.
[12] B. Recht, M. Fazel, and P. Parillo. Guaranteed minimum rank solution of matrix equations via nuclear norm minimization. SIAM Review, submitted for publication.
[13] E. Candes and B. Recht. Exact matrix completion via convex optimzation. Foundations of Computational Mathematics, to appear.
[14] A. Montanari R. Keshavan and S. Oh. Matrix completion from a few entries. preprint, 2009.
[15] E. Candes and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, submitted for publication.
[16] E. Candes and Y. Plan. Matrix completion with noise. Proceedings of the IEEE, to appear.
[17] D. Donoho. High-dimensional data analysis: The curses and blessings of dimensionality. AMS Math Challenges Lecture, 2000.
[18] A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Science, (1):183–202, 2009.
[19] Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127– 152, 2005.
[20] J. Cai, E. Candes, and Z. Shen. A singular value thresholding algorithm for matrix completion. preprint, http://arxiv.org/abs/0810.3286, 2008.
[21] K.-C. Toh and S. Yun. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. preprint, http://math.nus.edu.sg/˜matys/apg.pdf, 2009.
[22] J. Wright, A. Ganesh, S. Rao, and Y. Ma. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. Journal of the ACM, submitted for publication.
[23] E. Amaldi and V. Kann. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theoretical Computer Science, 209(2):237–260, 1998.
[24] D. Donoho. For most large underdetermined systems of linear equations the minimal l1 -norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics, 59(6):797–829, 2006.
[25] V. Chandrasekaran, S. Sanghavi, P. Parrilo, and A. Willsky. Sparse and low-rank matrix decompositions. In IFAC Symposium on System Identification, 2009.
[26] J. Wright and Y. Ma. Dense error correction via 1 -minimization. IEEE Transactions on Information Theory, to appear.
[27] Z. Lin, A. Ganesh, J. Wright, M. Chen, L. Wu, and Y. Ma. Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. SIAM Journal on Optimization, submitted for publication.
[28] V. Cevher, , M. F. Duarte, C. Hegde, and R. G. Baraniuk. Sparse signal recovery using markov random fields. In NIPS, 2008.
[29] L. Li, W. Huang, I. Gu, and Q. Tian. Statistical modeling of complex backgrounds for foreground object detection. IEEE Transactions on Image Processing, 13(11), 2004.
[30] R. Basri and D. Jacobs. Lambertian reflection and linear subspaces. IEEE Trans. PAMI, 25(3):218–233, 2003.
[31] A. Georghiades, P. Belhumeur, and D. Kriegman. From few to many: Illumination cone models for face recognition under variable lighting and pose. IEEE Trans. PAMI, 23(6):643–660, 2001. 9