Abstract
Given a set of corrupted data drawn from a union of multiple subspace, the subspace recovery problem is to segment the data into their respective subspace and to correct the possible noise simultaneously. Recently, it is discovered that the task can be characterized, both theoretically and numerically, by solving a matrix nuclear-norm and a ℓ2,1-mixed norm involved convex minimization problems. The minimization model actually has separable structure in both the objective function and constraint; it thus falls into the framework of the augmented Lagrangian alternating direction approach. In this paper, we propose and investigate an augmented Lagrangian algorithm. We split the augmented Lagrangian function and minimize the subproblems alternatively with one variable by fixing the other one. Moreover, we linearize the subproblem and add a proximal point term to easily derive the closed-form solutions. Global convergence of the proposed algorithm is established under some technical conditions. Extensive experiments on the simulated and the real data verify that the proposed method is very effective and faster than the sate-of-the-art algorithm LRR.
Similar content being viewed by others
References
Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and distributed computation: numerical methods. PrenticeHall, Englewood Cliffs, NJ (1989)
Cai, J.F., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 1956–1982 (2010)
Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9, 717–772 (2009)
Candès, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? J. ACM 58, 1–37 (2011)
Chen, C., He, B.S., Yuan, X.: Matrix completion via alternating direction method. IMA J. Numer. Anal. doi:10.1093/imanum/drq039
Deng, W., Yin, W., Zhang, Y.: Group sparse optimization by alternating direction method. Avaiable at http://www.optimization-online.org/DB_HTML/2011/04/3006.html
Duchi, J., Singer, Y.: Efficient online and batch learning using forward backward splitting. J. Mach. Learn. Res. 10, 2899–2934 (2009)
Elhamifar, E., Vidal, R.: Sparse subspace clustering. In: IEEE Conference on Computer Vision and Pattern Recongnition, vol. 2, pp. 2970–2997 (2009)
Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split Bregman. TR. 09-31, CAM, UCLA. Available at ftp://ftp.math.ucla.edu/pub/camreport/cam09-31.pdf (2009)
Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite-element approximations. Comput. Math. Appl. 2, 17–40 (1976)
Glowinski, R., Marrocco, A.: Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet nonlinéaires. Revue Francaise d’automatique, informatique, recherche opéretionnelle. Analyse numérique 2, 41–76 (1975)
Goldstein, T., Osher, S.: The split Bregman method for ℓ1-regularized problems. SIAM J. Imag. Sci. 2, 323–343 (2009)
Hale, E.T., Yin, W., Zhang., Y.: Fixed-point continuation for ℓ1-minimization: methodology and convergence. SIAM J. Optim. 19, 1107–1130 (2008)
He, B.S., Tao, M., Yuan, X.M.: A splitting method for separate convex programming with linking linear constraints. Available at http://www.optimization-online.org/DB_HTML/2010/06/2665.html
He, B.S., Tao, M., Xu, M.H., Yuan, X.M.: Alternating directions based contraction method for generally separable linearly constrained convex programming problems. Available at http://www.optimization-online.org/DB_HTML/2009/11/2465.html
He, B.S., Tao, M., Yuan, X.M.: A splitting method for separate convex programming with linking linear constraints. Available at http://www.optimization-online.org/DB_HTML/2010/06/2665.html
He, B.S., Xu, M.H., Yuan, X.M.: Solving large-scale least squares semidefinite programming by alternating direction methods. SIAM. J. Matrix Anal. Appl. 32, 136–152 (2011)
Lin, Z., Chen, M., Wu, L., Ma, Y.: The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices. Math. Program. Available at http://arxiv.org/abs/1009.5055
Lin, Z., Ganesh, A., Wright, J., Wu, L., Chen, M., Ma, Y.: Fast convex optimization algorithm for exact recovery of a corrupted low-rank matrix. Available at http://yima.csl.illinois.edu/psfile/rpca_algorithms.pdf
G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, Ma, Y.: Robust recovery of subspace structures by low-rank representation. Available at http://arxiv.org/abs/1010.2955
Ma, S., Goldfarb, D., Chen, L.: Fixed point and Bregman iterative methods for matrix rank minimization. Math. Program. doi:10.1007/s10107-009-0306-5
Nesterov, Y.: A method of solving a convex programming proble with convergence rate O(1/k 2). Sov. Math., Dokl. 27, 372–376 (1983)
Rao, S., Tron, R., Vida, R., Ma, Y.: Motion segmentation in the presence of outlying, incomplete, or corrupted trajectories. IEEE Trans. Pattern Anal. 32, 1832–1845 (2010)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1998)
Steidl, G., Teuber, T.: Removing multiplicative noise by Douglas-Rachford splitting methods. J. Math. Imag. Vis. 36, 168–184 (2010)
Sturm, J.F.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim. Method. Softw. 11–12, 625–653 (1999)
Sun, J., Zhang, S.: A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs. Eur. J. Oper. Res. 207, 1210–1220 (2010)
Tao, M., Yuan, X.M.: Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21, 57–81 (2011)
Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. SIAM J. Optim. (2008, submitted)
Tütüncü, R.H., Toh, K.C., Todd., M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. 95, 189–217 (2003)
Wang, Y., Yang, J., Yin, W., Zhang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imag. Sci. 1, 248–272 (2008)
Wen, Z., Goldfard, D. W. Yin: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Prog. Comp. 2, 203–230 (2010)
Wright, J., Ma, Y., Ganesh, A., Rao, S.: Robust principal component analysis: exact recovery of corrupted low-rank matrices via convex optimization. In: Proceedings of the Conference on Neural Information Processing Systems (NIPS), 2009.
Xiao, Y., Jin, Z.F.: An alternative direction method for linear constrained matrix nuclear norm minimization. Numer. Linear Algebra Appl. doi:10.1002/nla.783
Xiao, Y., Song, H.N.: An inexact alternating directions algorithm for constrained total variation regularized compressive sensing problems. J. Math. Imag. Vis. doi:10.1007/s10851-011-0314-y
Xiao, Y., Yang, J., Yuan, X.M.: Fast algorithms for total variation image reconstruction from random projections. Available at http://arxiv.org/abs/1001.1774v1
Yang, J., Yuan, X.M.: Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization (submitted)
Yang, J., Zhang, Y.: Alternating direction algorithms for ℓ1-problems in compressive sensing. SIAM J. Sci. Comput. 33, 250–278 (2011)
Yuan, X.M., Yang, J.: Sparse and low-rank matrix decomposition via alternating direction methods. Pac. J. Optim. (2011, to appear)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Lixin Shen.
Rights and permissions
About this article
Cite this article
Xiao, Y., Wu, SY. & Li, DH. Splitting and linearizing augmented Lagrangian algorithm for subspace recovery from corrupted observations. Adv Comput Math 38, 837–858 (2013). https://doi.org/10.1007/s10444-011-9261-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10444-011-9261-9
Keywords
- Principal component analysis
- Low-rank representation
- Subspace recovery
- Augmented Lagrangian function
- Convex optimization
- Nuclear norm minimization