nips nips2011 nips2011-257 nips2011-257-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Andrew E. Waters, Aswin C. Sankaranarayanan, Richard Baraniuk
Abstract: We consider the problem of recovering a matrix M that is the sum of a low-rank matrix L and a sparse matrix S from a small set of linear measurements of the form y = A(M) = A(L + S). This model subsumes three important classes of signal recovery problems: compressive sensing, affine rank minimization, and robust principal component analysis. We propose a natural optimization problem for signal recovery under this model and develop a new greedy algorithm called SpaRCS to solve it. Empirically, SpaRCS inherits a number of desirable properties from the state-of-the-art CoSaMP and ADMiRA algorithms, including exponential convergence and efficient implementation. Simulation results with video compressive sensing, hyperspectral imaging, and robust matrix completion data sets demonstrate both the accuracy and efficacy of the algorithm. 1
[1] E. J. Cand` s. Compressive sampling. In Intl. Cong. of Math., Madrid, Spain, Aug. 2006. e
[2] E. J. Cand` s, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? J. ACM, 58(1):1–37, e 2009.
[3] E. J. Cand` s and Y. Plan. Matrix completion with noise. Proc. IEEE, 98(6):925–936, 2010. e
[4] E. J. Cand` s and J. Romberg. Quantitative robust uncertainty principles and optimally sparse decomposie tions. Found. Comput. Math., 6(2):227–254, 2006.
[5] E.J. Cand` s and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. e on Info. Theory, 56(5):2053–2080, 2010.
[6] V. Cevher, A. C. Sankaranarayanan, M. Duarte, D. Reddy, R. G. Baraniuk, and R. Chellappa. Compressive sensing for background subtraction. In European Conf. Comp. Vision, Marseilles, France, Oct. 2008.
[7] A. Chakrabarti and T. Zickler. Statistics of Real-World Hyperspectral Images. In IEEE Int. Conf. Comp. Vis., Colorado Springs, CO, June 2011.
[8] V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky. Sparse and low-rank matrix decompositions. In Allerton Conf. on Comm., Contr., and Comp., Monticello, IL, Sep. 2009.
[9] V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A.S. Willsky. Rank-sparsity incoherence for matrix decomposition. Arxiv preprint arXiv:0906.2220, 2009.
[10] Y. Chen, A. Jalali, S. Sanghavi, and C. Caramanis. Low-rank matrix recovery from errors and erasures. Arxiv preprint arXiv:1104.0354, 2011.
[11] Y. Chen, H. Xu, C. Caramanis, and S. Sanghavi. Robust matrix completion with corrupted columns. Arxiv preprint arXiv:1102.2254, 2011.
[12] R. Coifman, F. Geshwind, and Y. Meyer. Noiselets. Appl. Comput. Harmon. Anal., 10:27–44, 2001.
[13] M. F. Duarte, M. A. Davenport, D. Takhar, J. N. Laska, T. Sun, K. F. Kelly, and R. G. Baraniuk. Single pixel imaging via compressive sampling. IEEE Signal Processing Mag., 25(2):83–91, 2008.
[14] M. Fazel, E. Cand` s, B. Recht, and P. Parrilo. Compressed sensing and robust recovery of low rank e matrices. In Asilomar Conf. Signals, Systems, and Computers, Pacific Grove, CA, Nov. 2008.
[15] M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version 1.21. http://cvxr.com/cvx, Apr. 2011.
[16] R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from noisy entries. J. Mach. Learn. Res., 11:2057–2078, 2010.
[17] K. Lee and Y. Bresler. Admira: Atomic decomposition for minimum rank approximation. IEEE Trans. on Info. Theory, 56(9):4402–4416, 2010.
[18] Z. Lin, M. Chen, L. Wu, and Y. Ma. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. Technical report, University of Illinois at Urbana-Champaign, UrbanaChampaign, IL.
[19] 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. In Intl. Workshop on Comp. Adv. in Multi-Sensor Adapt. Processing, Aruba, Dutch Antilles, Dec. 2009.
[20] D. Needell and J.A. Tropp. Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmon. Anal., 26(3):301–321, 2009.
[21] J. Y. Park and M. B. Wakin. A multiscale framework for compressive sensing of video. In Picture Coding Symp., Chicago, IL, May 2009.
[22] B. Recht. A simpler approach to matrix completion. J. Mach. Learn. Res., posted Oct. 2009, to appear.
[23] B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev., 52(3):471–501, 2010.
[24] A. C. Sankaranarayanan, P. Turaga, R. G. Baraniuk, and R. Chellappa. Compressive acquisition of dynamic scenes. In European Conf. Comp. Vision, Crete, Greece, Sep. 2010.
[25] T. Sun and K. Kelly. Compressive sensing hyperspectral imager. In Comput. Opt. Sensing and Imaging, San Jose, CA, Oct. 2009.
[26] A. E. Waters, A. C. Sankaranarayanan, and R. G. Baraniuk. SpaRCS: Recovering low-rank and sparse matrices from compressive measurements. Technical report, Rice University, Houston, TX, 2011.
[27] W. Yin, S. Osher, D. Goldfarb, and J. Darbon. Bregman iterative algorithms for `1 -minimization with applications to compressed sensing. SIAM J. Imag. Sci., 1(1):143–168, 2008. 9