低秩矩阵近似与优化问题研究进展

doi:10.16451/j.cnki.issn1003-6059.201801003

摘要
图/表
参考文献(0)
相关文章 (0)

全文: PDF (1797 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要

首先以高维数据压缩与恢复为背景,详细阐述由香农采样理论到稀疏表示和压缩感知理论再到低秩矩阵问题的发展历程,引出低秩矩阵近似与优化问题的重要性.然后,从低秩矩阵最小化问题、低秩矩阵分解问题、低秩矩阵的优化与应用三方面对现有方法进行详细的综述.最后对当前研究的不足之处与未来的研究方向提出合理的建议.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	张恒敏
	杨健
	郑玮

关键词 ：秩最小化, 凸及非凸优化, 低秩矩阵分解, 收敛性分析

Abstract：

Based on the compression and recovery of high-dimensional data, the development process from the theory of Shannon sampling to sparse representation and compression perception and then to low-rank matrix problem is described. Then, the importance of low rank matrix relaxation and optimization problem is discussed. Subsequently, a detailed review of the existing methods is introduced from three aspects of low rank matrix minimization, decomposition, optimization and applications. Finally, some reasonable suggestions on the deficiencies of current research and the future research direction are put forward.

Key words： Rank Minimization Convex and Nonconvex Optimizations Low Rank Matrix Decomposition Convergence Analysis

收稿日期: 2017-09-25

基金资助:

国家自然科学基金项目(No.91420201,61472187,61502235,61233011,61373063,61601235)、江苏省研究生科研与实践创新计划项目(No.KYCX17_0359,KYCX17_0361)资助

作者简介: 张恒敏,博士研究生,主要研究方向为统计机器学习、非凸优化算法.E-mail:zhanghengmin@126.com.杨健 (通讯作者),博士,教授,主要研究方向为模式识别理论与应用、图形图像技术与应用、认知计算.E-mail:csjyang@njust.edu.cn.郑玮,博士,讲师,主要研究方向为机器学习、特征选择.E-mail:zhengwei@jit.edu.cn.

引用本文:

张恒敏, 杨健, 郑玮. 低秩矩阵近似与优化问题研究进展[J]. 模式识别与人工智能, 2018, 31(1): 23-36. ZHANG Hengmin, YANG Jian, ZHENG Wei. Research Progress of Low-Rank Matrix Approximation and #br# Optimization Problem. , 2018, 31(1): 23-36.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/10.16451/j.cnki.issn1003-6059.201801003 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2018/V31/I1/23

[1] BERCHTOLD S, BHM C, KRIEGAL H P. The Pyramid-Technique: Towards Breaking the Curse of Dimensionality // Proc of the ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 1998: 142-153.
[2] HIGGINS J R. Sampling Theory in Fourier and Signal Analysis: Foundations. Oxford, UK: Oxford University Press, 1996.
[3] SALOMON D. Data Compression: the Complete Reference. 4th Edition. Northridge, USA: Springer Science & Business Media, 2007.
[4] OLSHAUSEN B A, FIELD D J. Sparse Coding with an Overcomplete Basis Set: A Strategy Employed by V1? Vision Research, 1997, 37(23): 3311-3325.
[5] ADLER A, ELAD M, HEL R Y. Probabilistic Subspace Clustering via Sparse Representations. IEEE Signal Processing Letters, 2012, 20(1): 63-66.
[6] WRIGHT J, YANG A Y, GANESH A, et al. Robust Face Recognition via Sparse Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227.
[7] DONOHO D L. Compressed Sensing. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.
[8] ELDAR Y C, KUTYNIOK G. Compressed Sensing: Theory and Applications. Cambridge, UK: Cambridge University Press, 2012.
[9] BARANIUK R G. Compressive Sensing. IEEE Signal Processing Magazine, 2007, 24(4): 118-121.
[10] BOYD S, VANDENBERGHE L. Convex Optimization. Cambridge, UK: Cambridge University Press, 2004.
[11] MALLAT S G, ZHANG Z F. Matching Pursuits with Time-Frequency Dictionaries. IEEE Transactions on Signal Processing, 1993, 41(12): 3397-3415.
[12] TROPP J A, GILBERT A C. Signal Recovery from Random Mea-surements via Orthogonal Matching Pursuit. IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666.
[13] DONOHO D L, TSAIG Y, DRORI I, et al. Sparse Solution of Underdetermined Systems of Linear Equations by Stage-Wise Orthogonal Matching Pursuit. IEEE Transactions on Information Theory, 2012, 58(2): 1094-1121.
[14] NEEDELL D, VERSHYNIN R. Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit. Foundations of Computational Mathematics, 2009, 9(3): 317-334.
[15] DO T T, GAN L, NGUYEN N, et al. Sparsity Adaptive Matching Pursuit Algorithm for Practical Compressed Sensing // Proc of the 42nd Asilomar Conference on Signals, Systems and Computers. Washington, USA: IEEE, 2009: 581-587.
[16] EDMONDS J. Matroids and the Greedy Algorithm. Mathematical Programming, 1971, 1(1): 127-136.
[17] DONOHO D L, ELAD M, TEMLYAKOV V. Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise. IEEE Transactions on Information Theory, 2006, 52: 6-18.
[18] CHEN S S, DONOHO D L, SAUNDERS M A. Atomic Decomposition by Basis Pursuit. SIAM Review, 2001, 43(1): 129-159.
[19] CANDS E J, ROMBERG J. Sparsity and Incoherence in Compressive Sampling. Inverse Problems, 2007, 23(3): 969-985.
[20] KOH K, KIM S J, BOYD S. An Interior-Point Method for Large-Scale l₁-Regularized Logistic Regression. Journal of Machine Learning Research, 2007, 8: 1519-1555.
[21] DONOHO D L, TSAIG Y. Fast Solution of l₁-Norm Minimization Problems When the Solution May Be Sparse. IEEE Transactions on Information Theory, 2008, 54(11): 4789-4812.
[22] FIGUEIREDO M A T, NOWAK R D, WRIGHT S J. Gradient Projection for Sparse Reconstruction: Application to Compressed Sen-sing and Other Inverse Problems. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 586-597.
[23] YIN W T, OSHER S, GOLDFARB D, et al. Bregman Iterative Algorithms for l₁-Minimization with Applications to Compressed Sen-sing. SIAM Journal on Imaging Sciences, 2008, 1(1): 143-168.
[24] GOLDSTEIN T, OSHER S. The Split Bregman Method for l₁-Re-gularized Problems. SIAM Journal on Imaging Sciences, 2009, 2(2): 323-343.
[25] WEN Z W, YIN W T, GOLDFARB D, et al. A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation. SIAM Journal on Scientific Computing, 2010, 32(4): 1832-1857.
[26] BECK A, TEBOULLE M. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems. SIAM Journal on Imaging Sciences, 2009, 2(1): 183-202.
[27] BECKER S, BOBIN J, CANDS E J. NESTA: A Fast and Accurate First-Order Method for Sparse Recovery. SIAM Journal on Imaging Sciences, 2011, 4(1): 1-39.
[28] BOYD S, PARIKH N, CHU E, et al. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends^ in Machine Learning, 2011, 3(1): 1-122.
[29] YANG J F, ZHANG Y. Alternating Direction Algorithms for l₁-Problems in Compressive Sensing. SIAM Journal on Scientific Computing, 2011, 33(1): 250-278.
[30] ZHANG H M, YANG J, XIE J C, et al. Weighted Sparse Coding Regularized Nonconvex Matrix Regression for Robust Face Recognition. Information Sciences, 2017, 394/395: 1-17.
[31] NIE F P, WANG H, CAI X, et al. Robust Matrix Completion via Joint Schatten p-norm and l_p-Norm Minimization // Proc of the 12th IEEE International Conference on Data Mining. Washington, USA: IEEE, 2012: 566-574.
[32] ZUO W M, MENG D Y, ZHANG L, et al. A Generalized Iterated Shrinkage Algorithm for Non-convex Sparse Coding // Proc of the IEEE International Conference on Computer Vision. Washington, USA: IEEE, 2013: 217-224.
[33] ZHANG C H. Nearly Unbiased Variable Selection under Minimax Concave Penalty. The Annals of Statistics, 2010, 38(2): 894-942.
[34] FAN J Q, LI R Z. Variable Selection via Nonconcave Penalized Likelihood and Its Oracle Properties. Journal of the American Statistical Association, 2001, 96(456): 1348-1360.
[35] JIANG W H, NIE F P, HUANG H. Robust Dictionary Learning with Capped l₁-Norm // Proc of the 24th International Joint Conference on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2015: 3590-3596.
[36] GAO C X, WANG N Y, YU Q, et al. A Feasible Nonconvex Relaxation Approach to Feature Selection // Proc of the 25th Confe-rence on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2014: 356-361.
[37] GEMAN D, YANG C. Nonlinear Image Recovery with Half-Quadratic Regularization. IEEE Transactions on Image Processing, 1995, 4(7): 932-946.
[38] TRZASKO J, MANDUCA A. Highly Undersampled Magnetic Re-sonance Image Reconstruction via Homotopic l₀-Minimization. IEEE Transactions on Medical imaging, 2009, 28(1): 106-121.
[39] YAO Q M, KWOK J T, ZHONG W L. Fast Low-Rank Matrix Learning with Nonconvex Regularization // Proc of the IEEE International Conference on Data Mining. Washington, USA: IEEE, 2015: 539-548.
[40] LU C Y, TANG J H, YAN S C, et al. Nonconvex Non-smooth Low-Rank Minimization via Iteratively Reweighted Nuclear Norm. IEEE Transactions on Image Processing, 2016, 25(2): 829-839.
[41] BOLTE J, SABACH S, TEBOULLE M. Proximal Alternating Li-nearized Minimization for Nonconvex and Non-smooth Problems. Mathematical Programming, 2014, 146(1/2): 459-494.
[42] ATTOUCH H, BOLTE J, SVAITER B F. Convergence of Descent Methods for Semi-algebraic and Tame Problems: Proximal Algorithms, Forward-Backward Splitting, and Regularized Gauss-Seidel Methods. Mathematical Programming, 2013, 137(1/2): 91-129.
[43] CHEN J H, YANG J, LUO L, et al. Matrix Variate Distribution-induced Sparse Representation for Robust Image Classification. IEEE Transactions on Neural Networks and Learning Systems, 2015, 26(10): 2291-2300.
[44] LUO L, YANG J, QIAN J J, et al. Robust Image Regression Based on the Extended Matrix Variate Power Exponential Distribution of Dependent Noise. IEEE Transactions on Neural Networks and Learning Systems, 2017, 28(9): 2168-2182.
[45] TOIC/ I, FROSSARD P. Dictionary Learning. IEEE Signal Processing Magazine, 2011, 28(2): 27-38.
[46] MAIRAL J, ELAD M, SAPIRO G. Sparse Representation for Color Image Restoration. IEEE Transactions on Image Processing, 2008, 17(1): 53-69.
[47] YANG J C, WRIGHT J, HUANG T S, et al. Image Super-Resolution via Sparse Representation. IEEE Transactions on Image Processing, 2010, 19(11): 2861-2873.
[48] LEE H, EKANADHAM C, NG A Y. Sparse Deep Belief Net Mo-del for Visual Area V2 // Proc of the 21st Annual Conference on Neural Information Processing Systems. Cambridge, USA: The MIT Press, 2008: 873-880.
[49] LI J, ZHANG T, LUO W, et al. Sparseness Analysis in the Pretraining of Deep Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, 2017, 28(6): 1425-1438.
[50] TSO M K S. Reduced-Rank Regression and Canonical Analysis. Journal of the Royal Statistical Society(Methodological), 1981, 43(2): 183-189.
[51] MA Y, SOATTO S, KOSECK J, et al. An Invitation to 3-D Vision: From Images to Geometric Models. New York, USA: Springer-Verlag, 2004.
[52] FAZEL M. Matrix Rank Minimization with Applications. Ph.D. Dissertation. Stanford, USA: Stanford University, 2002.
[53] NIE F P, HUANG H, DING C. Low-Rank Matrix Recovery via Efficient Schatten p-Norm Minimization // Proc of the 26th AAAI Conference on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2012: 655-661.
[54] RECHT B, FAZEL M, PARRILO P A. Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization. SIAM Review, 2010, 52(3): 471-501.
[55] CANDS E J, TAO T. The Power of Convex Relaxation: Near-Optimal Matrix Completion. IEEE Transactions on Information Theory, 2010, 56(5): 2053-2080.
[56] XU Z B, CHANG X Y, XU F M, et al. L_1/2 Regularization: A Thresholding Representation Theory and a Fast Solver. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(7): 1013-1027.
[57] CAO W, SUN J, XU Z B. Fast Image Deconvolution Using Closed-Form Thresholding Formulas of Regularization. Journal of Visual Communication and Image Representation, 2013, 24(1): 31-41.
[58] CAI J F, CANDS E J, SHEN Z W. A Singular Value Thresholding Algorithm for Matrix Completion. SIAM Journal on Optimization, 2010, 20(4): 1956-1982.
[59] LU C Y, LIN Z C, YAN S C. Smoothed Low Rank and Sparse Matrix Recovery by Iteratively Reweighted Least Squares Minimization. IEEE Transactions on Image Processing, 2015, 24(2): 646-654.
[60] GU S H, ZHANG L, ZUO W M, et al. Weighted Nuclear Norm Minimization with Application to Image Denoising // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2014: 2862-2869.
[61] XIE Y, GU S H, LIU Y, et al. Weighted Schatten p-Norm Minimization for Image Denoising and Background Subtraction. IEEE Transactions on Image Processing, 2016, 25(10): 4842-4857.
[62] HU Y, ZHANG D B, YE J P, et al. Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(9): 2117-2130.
[63] 张凡龙.基于核范数的低秩理论与方法研究.博士学位论文.南京:南京理工大学, 2015.
(ZHANG F L. Nuclear Norm Based Low Rank: Theory and Algorithms. Ph.D. Dissertation. Nanjing, China: Nanjing University of Science and Technology, 2015.)
[64] CAI T T, ZHOU W X. Matrix Completion via Max-Norm Constrained Optimization. The Computing Research Repository (CoRR), 2013. DOI: 10.1214/16-EJS1147.
[65] SHANG F H, LIU Y Y, TONG H H, et al. Robust Bilinear Factorization with Missing and Grossly Corrupted Observation. Information Sciences, 2015, 307: 53-72.
[66] LIU Y Y, JIAO L C, SHANG F H. An Efficient Matrix Factorization Based Low-Rank Representation for Subspace Clustering. Pa-ttern Recognition, 2013, 46(1): 284-292.
[67] LIU Y Y, JIAO L C, SHANG F H. A Fast Tri-factorization Method for Low-Rank Matrix Recovery and Completion. Pattern Recognition, 2013, 46(1): 163-173.
[68] SREBRO N, RENNIE J D M, JAAKKOLA T S. Maximum-Margin Matrix Factorization // SAUL L K, WEISS Y, BOTTOU L, eds. Advances in Neural Information Processing Systems 17. Cambridge, USA: The MIT Press, 2005: 1329-1336.
[69] SHANG F H, CHENG J, LIU Y Y, et al. Bilinear Factor Matrix Norm Minimization for Robust PCA: Algorithms and Applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017. DOI: 10.1109/TPAMI.2017.2748590.
[70] SHANG F H, LIU Y Y, CHENG J. Tractable and Scalable Scha-tten Quasi-Norm Approximations for Rank Minimization // Proc of the 19th International Conference on Artificial Intelligence and Statistics. New York, USA: ACM, 2016: 620-629.
[71] SHANG F H, LIU Y Y, CHENG J. Unified Scalable Equivalent Formulations for Schatten Quasi-Norms[C/OL]. [2017-10-20]. https://arxiv.org/pdf/1606.00668.pdf.
[72] NESTEROV Y. A Method of Solving a Convex Programming Pro-blem with Convergence Rate O(1/k₂ ). Soviet Mathematics Doklady, 1983, 27(2): 372-376.
[73] TOH K C, YUN S. An Accelerated Proximal Gradient Algorithm for Nuclear Norm Regularized Linear Least Squares Problems. Pacific Journal of Optimization, 2010, 6(3): 615-640.
[74] JI S W, YE J P. An Accelerated Gradient Method for Trace Norm Minimization // Proc of the 26th Annual International Conference on Machine Learning. New York, USA: ACM, 2009: 457-464.
[75] LIN Z C, CHEN M M, WU L Q, et al. The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices [C/OL]. [2017-10-20]. http://yima.csl.illinois.edu/psfile/Lin09-MP.pdf.
[76] LIN Z C, LIU R S, SU Z X. Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation // Proc of the 25th Annual Conference on Neural Information Proce-ssing Systems. Cambridge, USA: The MIT Press, 2011: 612-620.
[77] CHEN C H, HE B S, YE Y Y, et al. The Direct Extension of ADMM for Multi-block Convex Minimization Problems Is Not Ne-cessarily Convergent. Mathematical Programming, 2016, 155(1/2): 57-79.
[78] YANG J, LUO L, QIAN J J, et al. Nuclear Norm Based Matrix Regression with Applications to Face Recognition with Occlusion and Illumination Changes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017, 39(1): 156-171.
[79] HUNTER D R, LI R Z. Variable Selection Using MM Algorithms. Annals of Statistics, 2005, 33(4): 1617-1642.
[80] GONG P H, ZHANG C S, LU Z S, et al. A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems // Proc of the 30th International Conference on Machine Learning. New York, USA: ACM, 2013: 37-45.
[81] GASSO G, RAKOTOMAMONJY A, CANU S. Recovering Sparse Signals with a Certain Family of Nonconvex Penalties and DC Programming. IEEE Transactions on Signal Processing, 2009, 57(12): 4686-4698.
[82] SUN T, JIANG H, CHENG L Z. Convergence of Proximal Iteratively Reweighted Nuclear Norm Algorithm for Image Processing. IEEE Transactions on Image Processing, 2017, 26(12): 5632-5644.
[83] LI H, LIN Z. Accelerated Proximal Gradient Methods for Nonconvex Programming // Proc of the Annual Conference on Neural Information Processing Systems. Cambridge, USA: The MIT Press, 2015: 379-387.
[84] LI Q W, ZHOU Y, LIANG Y B, et al. Convergence Analysis of Proximal Gradient with Momentum for Nonconvex Optimization // Proc of the 34th International Conference on Machine Learning. New York, USA: ACM, 2017: 2111-2119.
[85] HONG M, LUO Z Q, RAZAVIYAYN M. Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Noncon-vex Problems. SIAM Journal on Optimization, 2016, 26(1): 337-364.
[86] OH T H, MATSUSHITA Y, TAI Y W, et al. Fast Randomized Singular Value Thresholding for Nuclear Norm Minimization // Proc of the IEEE Conference on Computer Vision and Pattern Re-cognition. Washington, USA: IEEE, 2015: 4484-4493.
[87] YAO Q M, KWOK J T, GAO F, et al. Efficient Inexact Proximal Gradient Algorithm for Nonconvex Problems // Proc of the 26th International Joint Conference on Artificial Intelligence. San Francisco, USA: Morgan Kaufmann, 2017: 3308-3314.
[88] GHADIMI S, LAN G H. Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming. Mathematical Programming, 2016, 156(1/2): 59-99.
[89] XIAO L. Dual Averaging Methods for Regularized Stochastic Lear-ning and Online Optimization. Journal of Machine Learning Research, 2010, 11: 2543-2596.
[90] CANDS E J, LI X D, MA Y, et al. Robust Principal Component Analysis. Journal of the ACM(JACM), 2011, 58(3). DOI:10.1145/1970392.1970395.
[91] LIU G C, LIN Z C, YAN S C, et al. Robust Recovery of Subspace Structures by Low-Rank Representation. IEEE Transactions on Pa-ttern Analysis and Machine Intelligence, 2013, 35(1): 171-184.
[92] CHEN J H, YANG J. Robust Subspace Segmentation via Low-Rank Representation. IEEE Transactions on Cybernetics, 2014, 44(8): 1432-1445.
[93] ZHANG H M, YANG J, SHANG F H, et al. LRR for Subspace Segmentation via Tractable Schatten-p Norm Minimization and Factorization[EB/OL] .[2018-01-23]. http://blog.sciencenet.cn/home.php?mod=space&uid=910693&do=blog&quickfor ward=1&id=1096324.
[94] LU C Y, FENG J S, CHEN Y D, et al. Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2016: 5249-5257.
[95] BOUWMANS T, SOBRAL A, JAVED S, et al. Decomposition into Low-Rank Plus Additive Matrices for Background/Foreground Se-paration: A Review for a Comparative Evaluation with a Large-Scale Dataset. Computer Science Review, 2017, 23: 1-71.
[96] 彭义刚,索津莉,戴琼海,等.从压缩传感到低秩矩阵恢复:理论与应用.自动化学报, 2013, 39(7): 981-994.
(PENG Y G, SUO J L, DAI Q H, et al. From Compressed Sen-sing to Low-Rank Matrix Recovery: Theory and Applications. Acta Automatica Sinica, 2013, 39(7): 981-994.)
[97] 马坚伟,徐杰,鲍跃全,等.压缩感知及其应用:从稀疏约束到低秩约束优化.信号处理, 2012, 28(5): 609-623.
(MA J W, XU J, BAO Y Q, et al. Compressive Sensing and Its Application: From Sparse to Low-Rank Regularized Optimization.
Signal Processing, 2012, 28(5): 609-623.)