Top

Journal of Scientific Computing

Published in:

21-05-2015

An Alternating Direction Method with Continuation for Nonconvex Low Rank Minimization

Authors: Zheng-Fen Jin, Zhongping Wan, Yuling Jiao, Xiliang Lu

Published in: Journal of Scientific Computing | Issue 2/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper we consider a nonconvex model of recovering low-rank matrices from the noisy measurement. The problem is formulated as a nonconvex regularized least square optimization problem, in which the rank function is replaced by a matrix minimax concave penalty function. An alternating direction method with a continuation (ADMc) technique (on the regularization parameter) is proposed to solve this nonconvex low rank matrix recovery problem. Moreover, under some mild assumptions, the convergence behavior of the alternating direction method for the proposed nonconvex problems is proved. Finally, comprehensive numerical experiments show that the proposed nonconvex model and the ADM algorithm are competitive with the state-of-the-art models and algorithms in terms of efficiency and accuracy.

previous article Finite Element Analysis of a Bending Moment Formulation for the Vibration Problem of a Non-homogeneous Timoshenko Beam

next article The Staggered DG Method is the Limit of a Hybridizable DG Method. Part II: The Stokes Flow

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

The APGL code is downloaded form http://www.math.nus.edu.sg/~mattohkc/NNLS.html.

The PD code is downloaded from http://www.sfu.ca/~yza30/homepage/PD_Rank/downloads.html.

Srebro, N.: Learning with matrix factorizations. Doctoral dissertation, Massachusetts Institute of Technology (2004)

Goldberg, K., Roeder, T., Gupta, D., Perkins, C.: Eigentaste: a constant time collaborative filtering algorithm. Inf. Retr. 4(2), 133–151 (2001)CrossRefMATH

Spellman, P.T., Sherlock, G., Zhang, M.Q., Iyer, V.R., Anders, K., Eisen, M.B., Brown, P.O., Botstein, D., Futcher, B.: Comprehensive identification of cell cycle-regulated genes of the yeast saccharomyces cerevisiae by microarray hybridization. Mol. Biol. Cell 9(12), 3273–3297 (1998)CrossRef

Netfix prize website http://www.netflixprize.com

Mohan, K., Fazel, M.: Reweighted nuclear norm minimization with application to system identification. In: American Control Conference, 2010, pp. 2953–2959. IEEE (2010)

Fazel, M., Hindi, H., Boyd, S.: Rank minimization and applications in system theory. In: American Control Conference, 2004. Proceedings of the 2004, vol. 4, pp. 3273–3278. IEEE (2004)

Candès, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? J. ACM 58(3), 11 (2011)CrossRefMathSciNet

Ma, S., Goldfarb, D., Chen, L.: Fixed point and bregman iterative methods for matrix rank minimization. Math. Program. 128(1–2), 321–353 (2011)CrossRefMathSciNetMATH

Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9(6), 717–772 (2009)CrossRefMathSciNetMATH

10.

Candès, E.J., Tao, T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inf. Theory 56(5), 2053–2080 (2010)CrossRef

11.

Keshavan, R.H., Montanari, A., Oh, S.: Matrix completion from a few entries. IEEE Trans. Inf. Theory 56(6), 2980–2998 (2010)CrossRefMathSciNet

12.

Tütüncü, R.H., Toh, K.-C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using sdpt3. Math. Program. 95(2), 189–217 (2003)CrossRefMathSciNetMATH

13.

Cai, J.-F., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20(4), 1956–1982 (2010)CrossRefMathSciNetMATH

14.

Liu, Y.-J., Sun, D., Toh, K.-C.: An implementable proximal point algorithmic framework for nuclear norm minimization. Math. Program. 133(1–2), 399–436 (2012)CrossRefMathSciNetMATH

15.

Toh, K.-C., Yun, S.: An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pac. J. Optim. 6(615–640), 15 (2010)MathSciNet

16.

Xiao, Y.-H., Jin, Z.-F.: An alternating direction method for linear-constrained matrix nuclear norm minimization. Numer. Linear Algebra Appl. 19(3), 541–554 (2012)CrossRefMathSciNetMATH

17.

Yang, J., Yuan, X.: Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization. Math. Comput. 82(281), 301–329 (2013)CrossRefMathSciNetMATH

18.

Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471–501 (2010)CrossRefMathSciNetMATH

19.

Hu, Y., Zhang, D., Ye, J., Li, X., He, X.: Fast and accurate matrix completion via truncated nuclear norm regularization. IEEE Trans. Pattern Anal. Mach. Intell. 35(9), 2117–2130 (2013)CrossRef

20.

Chen, X., Fengmin, X., Ye, Y.: Lower bound theory of nonzero entries in solutions of \(l_2-l_p\) minimization. SIAM J. Sci. Comput. 32(5), 2832–2852 (2010)CrossRefMathSciNetMATH

21.

Zhang, T.: Analysis of multi-stage convex relaxation for sparse regularization. J. Mach. Learn. Res. 11, 1081–1107 (2010)MathSciNetMATH

22.

Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348–1360 (2001)CrossRefMathSciNetMATH

23.

Zhang, C.H.: Nearly unbiased variable selection under minimax concave penalty. Ann. Stat. 38(2), 894–942 (2010)CrossRefMATH

24.

Li, Y.-F., Zhang, Y.-J., Huang, Z.-H.: A reweighted nuclear norm minimization algorithm for low rank matrix recovery. J. Comput. Appl. Math. 263, 338–350 (2014)CrossRefMathSciNetMATH

25.

Lu, C., Tang, J., Yan, S., Lin, Z.: Generalized nonconvex nonsmooth low-rank minimization. arXiv preprint arXiv:1404.7306 (2014)

26.

Lai, M.-J., Yangyang, X., Yin, W.: Improved iteratively reweighted least squares for unconstrained smoothed \(l_q\) minimization. SIAM J. Numer. Anal. 51(2), 927–957 (2013)CrossRefMathSciNetMATH

27.

Wang, S., Liu, D., Zhang, Z.: Nonconvex relaxation approaches to robust matrix recovery. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pp. 1764–1770. AAAI Press (2013)

28.

Jiao, Y., Jin, B., Lu, X.: A primal dual active set algorithm for a class of nonconvex sparsity optimization. arXiv preprint. arXiv:1310.1147 (2013)

29.

Yang, J., Zhang, Y.: Alternating direction algorithms for l\_1-problems in compressive sensing. SIAM J. Sci. Comput. 33(1), 250–278 (2011)CrossRefMathSciNetMATH

30.

Xiao, Y., Zhu, H., Soon-Yi, W.: Primal and dual alternating direction algorithms for \(l_1-l_1\)-norm minimization problems in compressive sensing. Comput. Optim. Appl. 54(2), 441–459 (2013)CrossRefMathSciNetMATH

31.

Yuan, X.: Alternating direction method for covariance selection models. J. Sci. Comput. 51(2), 261–273 (2012)CrossRefMathSciNetMATH

32.

Fan, Q., Jiao, Y., Lu, X.: A primal dual active set algorithm with continuation for compressed sensing. IEEE Trans. Signal Process. 62, 6276–6285 (2014)CrossRefMathSciNet

33.

Jiao, Y., Jin, B., Lu, X.: A primal dual active set with continuation algorithm for the \(\ell ^0\)-regularized optimization problem. Appl. Comput. Harmon. Anal. (2014). doi:10.1016/j.acha.2014.10.001

34.

Chen, S.S., Donoho, D.L.: Atomic decomposition by basis pursuit. SIAM J Sci. Comput. 20(1), 33–61 (1998)CrossRefMathSciNet

35.

Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B (Methodological) 58(1), 267–288 (1996)MathSciNetMATH

36.

Akaike, H.: A new look at the statistical model identification. IEEE Trans. Autom. Control 19(6), 716–723 (1974)CrossRefMathSciNetMATH

37.

Lu, Z., Zhang, Y.: Penalty decomposition methods for rank minimization. Research Paper, Department of Mathematics, Simon Fraser University. Available at http://people.math.sfu.ca/zhaosong/ResearchPapers/pd-rank-rev.pdf (2013)

38.

Jin, Z.-F., Wang, Q., Wan, Z.: Recovering low-rank matrices from corrupted observations via the linear conjugate gradient algorithm. J. Comput. Appl. Math. 256, 114–120 (2014)CrossRefMathSciNet

39.

Kelley, C.T.: Iterative Methods for Linear and Nonlinear Equations. Society for Industrial and Applied Mathematics, Philadelphia (1995)CrossRefMATH

40.

Wen, Z., Yang, C., Liu, X., Marchesini, S.: Alternating direction methods for classical and ptychographic phase retrieval. Inverse Probl. 28(11), 115010 (2012)CrossRefMathSciNet

41.

Wen, Z., Peng, X., Liu, X., Sun, X., Bai, X.: Asset allocation under the basel accord risk measures. arXiv preprint, arXiv:1308.1321 (2013)

42.

Shen, Y., Wen, Z., Zhang, Y.: Augmented lagrangian alternating direction method for matrix separation based on low-rank factorization. Optim. Methods Softw. 29(2), 239–263 (2014)CrossRefMathSciNetMATH

43.

Malek-Mohammadi, M., Babaie-Zadeh, M., Amini, A., Jutten, C.: Recovery of low-rank matrices under affine constraints via a smoothed rank function. IEEE Trans. Signal Process. 62(4), 981–992 (2014)CrossRefMathSciNet

44.

Larsen, R.M.: Propack-software for large and sparse svd calculations. Available online, http://sun.stanford.edu/rmunk/PROPACK (2004)

Title: An Alternating Direction Method with Continuation for Nonconvex Low Rank Minimization
Authors: Zheng-Fen Jin
Zhongping Wan
Yuling Jiao
Xiliang Lu
Publication date: 21-05-2015
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 2/2016
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-015-0045-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2016

Stochastic Steady-State Navier–Stokes Equations with Additive Random Noise

A Compact Difference Scheme for Fractional Sub-diffusion Equations with the Spatially Variable Coefficient Under Neumann Boundary Conditions

The Staggered DG Method is the Limit of a Hybridizable DG Method. Part II: The Stokes Flow

Analysis of a Staggered Discontinuous Galerkin Method for Linear Elasticity

Spectral Method for Fourth-Order Problems on Quadrilaterals

Local Error Estimates for the SUPG Method Applied to Evolutionary Convection–Reaction–Diffusion Equations

Premium Partner