nips nips2013 nips2013-233 nips2013-233-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jiashi Feng, Huan Xu, Shuicheng Yan
Abstract: Robust PCA methods are typically based on batch optimization and have to load all the samples into memory during optimization. This prevents them from efficiently processing big data. In this paper, we develop an Online Robust PCA (OR-PCA) that processes one sample per time instance and hence its memory cost is independent of the number of samples, significantly enhancing the computation and storage efficiency. The proposed OR-PCA is based on stochastic optimization of an equivalent reformulation of the batch RPCA. Indeed, we show that OR-PCA provides a sequence of subspace estimations converging to the optimum of its batch counterpart and hence is provably robust to sparse corruption. Moreover, OR-PCA can naturally be applied for tracking dynamic subspace. Comprehensive simulations on subspace recovering and tracking demonstrate the robustness and efficiency advantages of the OR-PCA over online PCA and batch RPCA methods. 1
[1] M. Artac, M. Jogan, and A. Leonardis. Incremental pca for on-line visual learning and recognition. In Pattern Recognition, 2002. Proceedings. 16th International Conference on, volume 3, pages 781–784. IEEE, 2002.
[2] D.P. Bertsekas. Nonlinear programming. Athena Scientific, 1999.
[3] Samuel Burer and Renato Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Progam., 2003.
[4] E.J. Candes, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? ArXiv:0912.3599, 2009.
[5] V. Chandrasekaran, S. Sanghavi, P.A. Parrilo, and A.S. Willsky. Rank-sparsity incoherence for matrix decomposition. SIAM Journal on Optimization, 21(2):572–596, 2011.
[6] M. Fazel. Matrix rank minimization with applications. PhD thesis, PhD thesis, Stanford University, 2002.
[7] J. Feng, H. Xu, and S. Yan. Robust PCA in high-dimension: A deterministic approach. In ICML, 2012.
[8] D.L. Fisk. Quasi-martingales. Transactions of the American Mathematical Society, 1965.
[9] N. Guan, D. Tao, Z. Luo, and B. Yuan. Online nonnegative matrix factorization with robust stochastic approximation. Neural Networks and Learning Systems, IEEE Transactions on, 23(7):1087–1099, 2012.
[10] Jun He, Laura Balzano, and John Lui. Online robust subspace tracking from partial information. arXiv preprint arXiv:1109.3827, 2011.
[11] P.J. Huber, E. Ronchetti, and MyiLibrary. Robust statistics. John Wiley & Sons, New York, 1981.
[12] M. Hubert, P.J. Rousseeuw, and K.V. Branden. Robpca: a new approach to robust principal component analysis. Technometrics, 2005.
[13] Y. Li. On incremental and robust subspace learning. Pattern recognition, 2004.
[14] Z. Lin, M. Chen, and Y. Ma. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv preprint arXiv:1009.5055, 2010.
[15] Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen, and Y. Ma. Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), 2009.
[16] J. Mairal, F. Bach, J. Ponce, and G. Sapiro. Online learning for matrix factorization and sparse coding. JMLR, 2010.
[17] Morteza Mardani, Gonzalo Mateos, and G Giannakis. Dynamic anomalography: Tracking network anomalies via sparsity and low rank. 2012.
[18] Morteza Mardani, Gonzalo Mateos, and Georgios B Giannakis. Rank minimization for subspace tracking from incomplete data. In ICASSP, 2013.
[19] K. Pearson. On lines and planes of closest fit to systems of points in space. Philosophical Magazine, 1901.
[20] C. Qiu, N. Vaswani, and L. Hogben. Recursive robust pca or recursive sparse recovery in large but structured noise. arXiv preprint arXiv:1211.3754, 2012.
[21] B. Recht, M. Fazel, and P.A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471–501, 2010.
[22] Jasson Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collaborative prediction. In ICML, 2005.
[23] Pablo Sprechmann, Alex M Bronstein, and Guillermo Sapiro. Learning efficient sparse and low rank models. arXiv preprint arXiv:1212.3631, 2012.
[24] H. Xu, C. Caramanis, and S. Mannor. Principal component analysis with contaminated data: The high dimensional case. In COLT, 2010.
[25] H. Xu, C. Caramanis, and S. Sanghavi. Robust pca via outlier pursuit. Information Theory, IEEE Transactions on, 58(5):3047–3064, 2012. 9