An Alternating Direction Method with Continuation for Nonconvex Low Rank Minimization

详细信息    查看全文

• 作者：Zheng-Fen Jin ; Zhongping Wan ; Yuling Jiao ; Xiliang Lu
• 关键词：Low rank minimization ; Alternating direction method ; Continuation ; Minimax concave penalty function
• 刊名：Journal of Scientific Computing
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：66
• 期：2
• 页码：849-869
• 全文大小：1,123 KB
• 参考文献：1.Srebro, N.: Learning with matrix factorizations. Doctoral dissertation, Massachusetts Institute of Technology (2004)
  2.Goldberg, K., Roeder, T., Gupta, D., Perkins, C.: Eigentaste: a constant time collaborative filtering algorithm. Inf. Retr. 4(2), 133–151 (2001)CrossRef MATH
  3.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
  4.Netfix prize website http://​www.​netflixprize.​com
  5.Mohan, K., Fazel, M.: Reweighted nuclear norm minimization with application to system identification. In: American Control Conference, 2010, pp. 2953–2959. IEEE (2010)
  6.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)
  7.Candès, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? J. ACM 58(3), 11 (2011)CrossRef MathSciNet
  8.Ma, S., Goldfarb, D., Chen, L.: Fixed point and bregman iterative methods for matrix rank minimization. Math. Program. 128(1–2), 321–353 (2011)CrossRef MathSciNet MATH
  9.Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9(6), 717–772 (2009)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet
  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)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet MATH
  17.Yang, J., Yuan, X.: Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization. Math. Comput. 82(281), 301–329 (2013)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet MATH
  21.Zhang, T.: Analysis of multi-stage convex relaxation for sparse regularization. J. Mach. Learn. Res. 11, 1081–1107 (2010)MathSciNet MATH
  22.Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348–1360 (2001)CrossRef MathSciNet MATH
  23.Zhang, C.H.: Nearly unbiased variable selection under minimax concave penalty. Ann. Stat. 38(2), 894–942 (2010)CrossRef MATH
  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)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet MATH
  31.Yuan, X.: Alternating direction method for covariance selection models. J. Sci. Comput. 51(2), 261–273 (2012)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet
  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)CrossRef MathSciNet
  35.Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B (Methodological) 58(1), 267–288 (1996)MathSciNet MATH
  36.Akaike, H.: A new look at the statistical model identification. IEEE Trans. Autom. Control 19(6), 716–723 (1974)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet
  39.Kelley, C.T.: Iterative Methods for Linear and Nonlinear Equations. Society for Industrial and Applied Mathematics, Philadelphia (1995)CrossRef MATH
  40.Wen, Z., Yang, C., Liu, X., Marchesini, S.: Alternating direction methods for classical and ptychographic phase retrieval. Inverse Probl. 28(11), 115010 (2012)CrossRef MathSciNet
  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)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet
  44.Larsen, R.M.: Propack-software for large and sparse svd calculations. Available online, http://​sun.​stanford.​edu/​rmunk/​PROPACK (2004)
  
• 作者单位：Zheng-Fen Jin (1)
  Zhongping Wan (1)
  Yuling Jiao (2)
  Xiliang Lu (1) (3)
  
  1. School of Mathematics and Statistics, Wuhan University, Wuhan, 430072, People’s Republic of China
  2. School of Statistics and Mathematics, Zhongnan University of Economics and Law, Wuhan, 430063, People’s Republic of China
  3. Computational Science Hubei Key Laboratory, Wuhan University, Wuhan, 430072, People’s Republic of China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Algorithms
  Computational Mathematics and Numerical Analysis
  Applied Mathematics and Computational Methods of Engineering
  Mathematical and Computational Physics
  
• 出版者：Springer Netherlands
• ISSN：1573-7691

文摘

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.