Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization

References

• E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, & D. Sorensen, LAPACK Users’ Guide SIAM, Philadelphia, 1999.
   Google Scholar
• D. P. Bertsekas, J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods Prentice-Hall, Inc, Upper Saddle River, NJ, 1989.
   Google Scholar
• J. Cai, E. J. Candès, & Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 2010, 2041956–1982 doi: 10.1137/080738970
   Web of Science ®Google Scholar
• E. J. Candès, B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 2009, 96717–772 doi: 10.1007/s10208-009-9045-5
   Web of Science ®Google Scholar
• E. J. Candès, J. Romberg, Quantitative robust uncertainty principles and optimally sparse decompositions, Found. Comput. Math., 2006, 62227–254 doi: 10.1007/s10208-004-0162-x
   Web of Science ®Google Scholar
• E. J. Candès, T. Tao, Near optimal signal recovery from random projections: Universal encoding strategies, IEEE Trans. Inform. Theory, 2006, 5215406–5425 doi: 10.1109/TIT.2006.885507
   Web of Science ®Google Scholar
• E. J. Candès, T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Trans. Inform. Theory, 2010, 5652053–2080 doi: 10.1109/TIT.2010.2044061
   Web of Science ®Google Scholar
• E. J. Candès, X. Li, Y. Ma, & J. Wright, Robust principal component analysis? Arxiv preprint. Available at arXiv:0912.3599, December 2009
   Google Scholar
• E. J. Candès, J. Romberg, & T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 2006, 52489–509 doi: 10.1109/TIT.2005.862083
   Web of Science ®Google Scholar
• V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, & A. S. Willsky, Rank-sparsity incoherence for matrix decomposition Arxiv preprint. Available at arXiv:0906.2220, 2009
   Google Scholar
• V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, & A. S. Willsky, Sparse and low-rank matrix decompositions, IFAC Symposium on System Identification, 2009. Available at http://ssg.mit.edu/ venkatc/cspw_slr_sysid09.pdf
   Google Scholar
• G. Chen, M. Teboulle, A proximal-based decomposition method for convex minimization problems, Math. Program., 1994, 641, Ser. A81–101 doi: 10.1007/BF01582566
   Web of Science ®Google Scholar
• P. L. Combettes, J.-C. Pesquet, Proximal thresholding algorithm for minimization over orthonormal bases, SIAM J. Optim., 2007, 1841351–1376 doi: 10.1137/060669498
   Web of Science ®Google Scholar
• D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 2006, 521289–1306 doi: 10.1109/TIT.2006.871582
   Web of Science ®Google Scholar
• J. Eckstein, & D. P. Bertsekas, An Alternating Direction Method for Linear Programming, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA, 1967.
   Google Scholar
• J. Eckstein, & D. P. Bertsekas, On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 1992, 553, Ser. A293–318 doi: 10.1007/BF01581204
   Web of Science ®Google Scholar
• M. Elad, Why simple shrinkage is still relevant for redundant representations?, IEEE Trans. Inform. Theory, 2006, 52125559–5569 doi: 10.1109/TIT.2006.885522
   Web of Science ®Google Scholar
• M. Fazel, & J. Goodman, Approximations for partially coherent optical imaging systems technical report, Stanford University, 1998. Available at http://faculty.washington.edu/mfazel/acc03_final.pdf
   Google Scholar
• M. Fazel, H. Hindi, & S. Boyd, Log-det heuristic for matrix rank minimization with applications to hankel and euclidean distance matrices, Proceedings of the American Control Conference, 2003. Available at http://faculty.washington.edu/mfazel/acc03_final.pdf
   Google Scholar
• M. Figueiredo, & R. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 2003, 12906–916 doi: 10.1109/TIP.2003.814255
   PubMed Web of Science ®Google Scholar
• M. Fortin, & R. Glowinski, Augmented Lagrangian methods: Applications to the numerical solution of boundary value problems, Studies in Mathematics and its Applications, North-Holland Publishing Co, Amsterdam, 1983, Vol. 15 Translated from the French by B. Hunt and D. C. Spicer
   Google Scholar
• A. Ganeshy, J. Wright, X. Li, E. J. Candes, & Y. Ma, Dense error correction for low-rank matrices via principal component pursuit, 2010 IEEE International Symposium on Information Theory Proceedings (ISIT), 20101513–1517 doi: 10.1109/ISIT.2010.5513538
   Google Scholar
• R. Glowinski, Numerical Methods for Nonlinear Variational Problems Springer, Berlin, 1984.
   Google Scholar
• R. Glowinski, & P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics SIAM, Philadelphia, PA, 1989, Vol. 9
   Google Scholar
• J. P. Haldar, & D. Hernando, Rank-constrained solutions to linear matrix equations using powerfactorization, IEEE Signal Process. Lett., 2009, 16584–587 doi: 10.1109/LSP.2009.2018223
   PubMedGoogle Scholar
• E. T. Hale, W. Yin, & Y. Zhang, Fixed-point continuation for l1-minimization: Methodology and convergence, SIAM J. Optim., 2008, 1931107–1130 doi: 10.1137/070698920
   Web of Science ®Google Scholar
• B. He, L. Liao, D. Han, & H. Yang, A new inexact alternating directions method for monotone variational inequalities, Math. Program., 2002, 921, Ser. A103–118 doi: 10.1007/s101070100280
   Web of Science ®Google Scholar
• B. He, H. Yang, & S. Wang, Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities, J. Optim. Theory Appl., 2000, 1062337–356 doi: 10.1023/A:1004603514434
   Web of Science ®Google Scholar
• H. Hindi M. Fazel, & S. Boyd, A rank minimization heuristic with application to minimum order system approximation, Proceedings American Control Conference, 2001, 64734–4739
   Google Scholar
• K. C. Kiwiel, C. H. Rosa, & A. Ruszczyński, Proximal decomposition via alternating linearization, SIAM J. Optim., 1999, 93668–689 doi: 10.1137/S1052623495288064
   Web of Science ®Google Scholar
• S. Kontogiorgis, & R. R. Meyer, A variable-penalty alternating directions method for convex optimization, Math. Program., 1998, 831, Ser. A29–53
   Web of Science ®Google Scholar
• R. M. Larsen, Propack: Software for large and sparse svd calculations Available at http://soi.stanford.edu/rmunk/PROPACK
   Google Scholar
• L. Li, W. Huang, I. Gu, & Q. Tian, Statistical modeling of complex backgrounds for foreground object detection, IEEE Trans. Image Process., 2004, 13111459–1472 doi: 10.1109/TIP.2004.836169
   PubMed Web of Science ®Google Scholar
• Z. Lin, M. Chen, L. Wu, & Y. Ma, The augmented lagrange multiplier method for exact recovery of a corrupted low-rank matrices, Math. Program., 2009. (submitted)
   Google Scholar
• Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen, & Y. Ma, Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix2009. Available at http://yima.csl.illinois.edu/psfile/rpca_algorithms.pdf
   Google Scholar
• S. Ma, D. Goldfarb, & L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, technical report, Department of IEOR, Columbia University, 2008.
   Google Scholar
• Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Applied Optimization, Kluwer Academic Publishers, Boston, 2004.
   Google Scholar
• M. Tao, & X. Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim., 2011, 21157–81 doi: 10.1137/100781894
   Web of Science ®Google Scholar
• P. Tseng, Alternating projection-proximal methods for convex programming and variational inequalities, SIAM J. Optim., 1997, 74951–965 doi: 10.1137/S1052623495279797
   Web of Science ®Google Scholar
• P. Tseng, On accelerated proximal gradient methods for convex-concave optimization, SIAM J. Optim., 2008. (submitted)
   PubMed Web of Science ®Google Scholar
• Y. Wang, J. Yang, W. Yin, Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 2008, 13248–272 doi: 10.1137/080724265
   Web of Science ®Google Scholar
• Z. Wen, D. Goldfarb, & W. Yin, Alternating direction augmented Lagrangian methods for semidefinite programming, technical report, Department of IEOR, Columbia University, 2009.
   Google Scholar
• Z. Wen, W, & ZhangY. Yin, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, technical report, 2010. Available at http://www.optimization-online.org/DB_FILE/2010/03/2581.pdf
   Google Scholar
• J. Wright, A. Ganesh, S. Rao, Y. Peng, & Y. Ma, Robust principal component analysis: Exact recovery of corrupted low-rank matrices by convex optimization Proceedings of Neural Information Processing Systems (NIPS), December, 2009. Available at https://netfiles.uiuc.edu/abalasu2/www/Files/Wright09-NIPS.pdf
   Google Scholar
• J. Wright, A. Ganesh, S. Rao, Y. Peng, & Y. Ma, Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization, J. ACM., 2009. (submitted)
   Google Scholar
• J. Yang, Y. Zhang, & W. Yin, An efficient tvl1 algorithm for deblurring multichannel images corrupted by impulsive noise, SIAM J. Sci. Comput., 2009, 3142842–2865 doi: 10.1137/080732894
   Web of Science ®Google Scholar
• X. Yuan, & J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, technical report, Department of Mathematics, Hong Kong Baptist University, 2009.
   Google Scholar
• Y. ZhangLMaFit: Low-rank matrix fitting, 2009. Available at http://www.caam.rice.edu/ optimization/L1/LMaFit/
   Google Scholar
• Y. Zhang, User's guide for yall1: Your algorithms for L1 optimization, technical report, Rice University, 2009. Available at http://www.caam.rice.edu/ zhang/reports/tr0917.pdf
   Google Scholar
• Y. Zhang, An alternating direction algorithm for nonnegative matrix factorization, technical report, Rice University, 2010. Available at http://www.caam.rice.edu/ yzhang/reports/tr1003.pdf
   Google Scholar