基于l_P范数的非凸低秩张量最小化
|
摘要
在低秩矩阵、张量最小化问题中,凸函数容易求得最优解,而非凸函数可以得到更低秩的局部解.文中基于非凸替换函数的低秩张量恢复问题,提出基于l_p范数的非凸张量模型.采用迭代加权核范数算法求解模型,实现低秩张量最小化.在合成数据和真实图像上的大量实验验证文中方法的恢复性能.
For the low-rank matrix and tensor minimization problem, the optimal solution of convex function can be obtained easily, and the better low-rank solution can be obtained from the local minimum of the corresponding nonconvex function. The low-rank tensor recovery problem based on the nonconvex function is studied in this paper. A nonconvex low-rank tensor model based on l_p norm is proposed. In addition, tensor based iteratively reweighted nuclear norm algorithm is proposed to solve the nonconvex low-rank tensor minimization problem. The weighted singular value thresholding problem is solved by the tensor based iteratively reweighted nuclear norm algorithm. The objective function value monotonically decreases and its convergence can be theoretically proved. The recovery performance of the proposed method is demonstrated by comprehensive experiments on both synthetic data and real images.
For the low-rank matrix and tensor minimization problem, the optimal solution of convex function can be obtained easily, and the better low-rank solution can be obtained from the local minimum of the corresponding nonconvex function. The low-rank tensor recovery problem based on the nonconvex function is studied in this paper. A nonconvex low-rank tensor model based on l_p norm is proposed. In addition, tensor based iteratively reweighted nuclear norm algorithm is proposed to solve the nonconvex low-rank tensor minimization problem. The weighted singular value thresholding problem is solved by the tensor based iteratively reweighted nuclear norm algorithm. The objective function value monotonically decreases and its convergence can be theoretically proved. The recovery performance of the proposed method is demonstrated by comprehensive experiments on both synthetic data and real images.
引文
[1] CUI A G,PENG J G,LI H Y.Exact Recovery Low-Rank Matrix via Transformed Affine Matrix Rank Minimization.Neurocomputing,2018,319:1-12.
[2] HUANG S M,WOLKOWICZ H.Low-Rank Matrix Completion Using Nuclear Norm Minimization and Facial Reduction.Journal of Global Optimization,2018,72(1):5-26.
[3] DAVENPORT M A,ROMBERG J.An Overview of Low-Rank Matrix Recovery from Incomplete Observations.IEEE Journal of Selected Topics in Signal Processing,2016,10(4):608-622.
[4] YU S,YIQUAN W Q.Subspace Clustering Based on Latent Low Rank Representation with Frobenius Norm Minimization.Neurocomputing,2018,275:2479-2489.
[5] LIU G C,LIN Z C,YAN S C,et al.Robust Recovery of Subspace Structures by Low-Rank Representation.IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(1):171-184.
[6] CANDèS E J,LI X D,MA Y,et al.Robust Principal Component Analysis.Journal of the ACM,2011,58(3).DOI:10.1145/1970392.1970395.
[7] LIN X F,WEI G .Accelerated Reweighted Nuclear Norm Minimization Algorithm for Low Rank Matrix Recovery.Signal Processing,2015,114:24-33.
[8] 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.
[9] HAN D R,YUAN X M.A Note on the Alternating Direction Method of Multipliers.Journal of Optimization Theory and Applications,2012,155(1):227-238.
[10] TOH K C,YUN S W.An Accelerated Proximal Gradient Algorithm for Nuclear Norm Regularized Linear Least Squares Problems.Pacific Journal of Optimization,2010,6(3):615-640.
[11] LU C Y,TANG J H,YAN S C,et al.Nonconvex Nonsmooth Low Rank Minimization via Iteratively Reweighted Nuclear Norm.IEEE Transactions on Image Processing,2016,25(2):829-839.
[12] 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.
[13] LEE J,CHOE Y.Low Rank Matrix Recovery via Augmented Lagrange Multiplier with Nonconvex Minimization // Proc of the 12th IEEE Image,Video,and Multidimensional Signal Processing Workshop.Washington,USA:IEEE,2016.DOI:10.1109/IVMSPW.2016.7528217.
[14] ZHAO T,WANG Z R,LIU H.A Nonconvex Optimization Framework for Low Rank Matrix Estimation // JORDAN M I,LECUN Y,SOLLA S A,eds.Advances in Neural Information Processing Systems 28.Cambridge,USA:The MIT Press,2015:559-567.
[15] CHEN W G,LI Y L.Stable Recovery of Low-Rank Matrix via Nonconvex Schatten p-Minimization.Science China(mathematics),2015,58(12):2643-2654.
[16] 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.
[17] GOLDFARB D,QIN Z W.Robust Low-Rank Tensor Recovery:Models and Algorithms.SIAM Journal on Matrix Analysis and Applications,2014,35(1):225-253.
[18] KILMER M E,MARTIN C D.Factorization Strategies for Third-Order Tensors.Linear Algebra and Its Applications,2011,435(3):641-658.
[19] LU C Y,FENG J S,CHEN Y D,et al.Tensor Robust Principal Component Analysis with a New Tensor Nuclear Norm[J/OL].[2018-12-12].https://arxiv.org/pdf/1804.03728v1.pdf.
[20] LIU J,MUSIALSKI P,WONKA P,et al.Tensor Completion for Estimating Missing Values in Visual Data.IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(1):208-220.
[21] LU C Y,FENG J S,LIN Z C,et al.Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements // Proc of the 27th International Joint Conference on Artificial Intelligence.New York,USA:ACM,2018:2504-2510.
[22] LU C Y,ZHU C B,XU C Y,et al.Generalized Singular Value Thresholding // Proc of the 29th AAAI Conference on Artificial Intelligence.Palo Alto,USA:AAAI Press,2015:1805-1811.
[23] BECK A,TEBOULLE M.A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems.SIAM Journal on Imaging Sciences,2009,2(1):183-202.
[2] HUANG S M,WOLKOWICZ H.Low-Rank Matrix Completion Using Nuclear Norm Minimization and Facial Reduction.Journal of Global Optimization,2018,72(1):5-26.
[3] DAVENPORT M A,ROMBERG J.An Overview of Low-Rank Matrix Recovery from Incomplete Observations.IEEE Journal of Selected Topics in Signal Processing,2016,10(4):608-622.
[4] YU S,YIQUAN W Q.Subspace Clustering Based on Latent Low Rank Representation with Frobenius Norm Minimization.Neurocomputing,2018,275:2479-2489.
[5] LIU G C,LIN Z C,YAN S C,et al.Robust Recovery of Subspace Structures by Low-Rank Representation.IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(1):171-184.
[6] CANDèS E J,LI X D,MA Y,et al.Robust Principal Component Analysis.Journal of the ACM,2011,58(3).DOI:10.1145/1970392.1970395.
[7] LIN X F,WEI G .Accelerated Reweighted Nuclear Norm Minimization Algorithm for Low Rank Matrix Recovery.Signal Processing,2015,114:24-33.
[8] 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.
[9] HAN D R,YUAN X M.A Note on the Alternating Direction Method of Multipliers.Journal of Optimization Theory and Applications,2012,155(1):227-238.
[10] TOH K C,YUN S W.An Accelerated Proximal Gradient Algorithm for Nuclear Norm Regularized Linear Least Squares Problems.Pacific Journal of Optimization,2010,6(3):615-640.
[11] LU C Y,TANG J H,YAN S C,et al.Nonconvex Nonsmooth Low Rank Minimization via Iteratively Reweighted Nuclear Norm.IEEE Transactions on Image Processing,2016,25(2):829-839.
[12] 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.
[13] LEE J,CHOE Y.Low Rank Matrix Recovery via Augmented Lagrange Multiplier with Nonconvex Minimization // Proc of the 12th IEEE Image,Video,and Multidimensional Signal Processing Workshop.Washington,USA:IEEE,2016.DOI:10.1109/IVMSPW.2016.7528217.
[14] ZHAO T,WANG Z R,LIU H.A Nonconvex Optimization Framework for Low Rank Matrix Estimation // JORDAN M I,LECUN Y,SOLLA S A,eds.Advances in Neural Information Processing Systems 28.Cambridge,USA:The MIT Press,2015:559-567.
[15] CHEN W G,LI Y L.Stable Recovery of Low-Rank Matrix via Nonconvex Schatten p-Minimization.Science China(mathematics),2015,58(12):2643-2654.
[16] 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.
[17] GOLDFARB D,QIN Z W.Robust Low-Rank Tensor Recovery:Models and Algorithms.SIAM Journal on Matrix Analysis and Applications,2014,35(1):225-253.
[18] KILMER M E,MARTIN C D.Factorization Strategies for Third-Order Tensors.Linear Algebra and Its Applications,2011,435(3):641-658.
[19] LU C Y,FENG J S,CHEN Y D,et al.Tensor Robust Principal Component Analysis with a New Tensor Nuclear Norm[J/OL].[2018-12-12].https://arxiv.org/pdf/1804.03728v1.pdf.
[20] LIU J,MUSIALSKI P,WONKA P,et al.Tensor Completion for Estimating Missing Values in Visual Data.IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(1):208-220.
[21] LU C Y,FENG J S,LIN Z C,et al.Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements // Proc of the 27th International Joint Conference on Artificial Intelligence.New York,USA:ACM,2018:2504-2510.
[22] LU C Y,ZHU C B,XU C Y,et al.Generalized Singular Value Thresholding // Proc of the 29th AAAI Conference on Artificial Intelligence.Palo Alto,USA:AAAI Press,2015:1805-1811.
[23] BECK A,TEBOULLE M.A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems.SIAM Journal on Imaging Sciences,2009,2(1):183-202.