低秩矩阵与张量完整化问题的算法研究
|
摘要
矩阵完整化问题的主要研究内容是在己知矩阵部分元素的情况下如何将一个低秩或近似低秩的矩阵补充完整,此问题的直接推广是张量完整化问题.本文主要针对矩阵完整化问题和张量完整化问题的模型建立和求解算法进行探讨,主要有如下几点贡献：
1、我们建立了指示函数与核范数的极小化模型,并利用迫近映射的概念设计了求解该模型的迫近点算法(PPA-IF).该模型的优点是不含正则参数,并将含噪声与不含噪声的矩阵完整化问题统一为一个模型.接下来,我们分析了算法的收敛性并给出严格的证明.数值结果表明相比较于其他提到的算法我们的算法在时间和精度方面方面都有很大的改进.
2、核范数是秩函数在单位球内的最佳凸逼近,但二者之间仍有很大的差异,为此我们提出了秩函数一系列非凸逼近.
(1)首先我们用光滑函数——双曲正切函数来代替秩函数建立了求解矩阵完整化问题的光滑函数模型并设计了梯度投影算法(HTA)来求解.对随机生成的低秩矩阵完整化问题和图像恢复问题的测试结果表明我们提出的HTA算法能够得到更高的精确度,同时对于少量抽样的问题也能获得比较好的恢复效果.
(2)为了减少核范数与秩函数之间的差距,我们在核范数的定义中添加了权向量并建立了求解矩阵完整化问题的加权核范数模型.随后利用极大极小方法设计了加权软阈值算法并通过对随机生成的矩阵完整化问题和图像恢复问题的实验说明我们提出的算法在准确性和计算时间上都有所提高.
(3)我们提出利用一个新的指数型函数来代替秩函数.同样的对随机生成的矩阵完整化问题、Jester数据和图像恢复问题的测试表明该方法能够得到更高的恢复精度.
(4)针对很多非凸模型,我们进行归纳并建立了一个非凸模型框架,在这个框架下,已有的非凸模型及我们前面所提出的一些非凸模型都可以归入其中.然后,针对此框架,我们采用DC规划及DC算法进行求解.数值结果表明我们的算法能够得到更好的恢复效果.
3、我们针对硬阈值类的算法进行了改进.许多硬阈值的算法都是用负梯度方向作为使函数值下降的搜索方向,但用负梯度方向会导致“之”字型路线而减慢收敛速度.我们受半迭代方法的启示设计了半迭代硬阈值算法.与其他的迭代硬阈值算法相比,改进后的算法在计算时间上有很大的提高.
4、我们将加权核范数模型引入张量完整化问题中,建立了张量情况下的非凸模型并利用极大极小加权软阈值方法来求解.另外,对于求解张量完整化问题的硬阈值方法,我们也应用半迭代方法在下降方向上进行改进,并得到了很好的效果.
The most important research aspect in matrix completion is to recover an unknown matrix with low-rank or approximately low-rank from constraints of its sample entries. A natural generalization of matrix completion is tensor completion. This thesis focuses on the model and the corresponding algorithm for the matrix completion problem and tensor completion problem. The major contributions of this thesis are as follow:
1. We propose a new unconstraint model for matrix completion problem based on nuclear norm and indicator function and design a proximal point algorithm (PPA-IF) to solve it. The advantage of the model is that there is no regularization parameter and it unifies two constrained optimization problems (noiseless and noisy matrix completion problems). Then the convergence of our algorithm is established strictly. The numerical results suggest that significant improvement can be achieved by our algorithm compared to the other reported methods.
2. The nuclear norm is the best convex approximation of the rank function over the set of matrices with spectral norm less than or equal to one, however there is a great difference between the two function. To reconcile this imbalance, we proposed a series of nonconvex models and the corresponding algorithms.
(1) Firstly, we use a smoothed function-Hyperbolic Tangent function to approximate the rank function, and then using gradient projection method (HTA) to minimize it. We report numerical results for solving randomly generated matrix completion problems and image recovery problems. Numerical results show that accuracy of HTA is higher than others and the requisite number of sampling to recover a matrix is typically reduced.
(2) In order to decrease the gap between the nuclear norm and the rank function, we add weight vector in the nuclear norm and build a model of minimizing weighted nuclear norm. Based on the majorization-minimization approach, we propose a weighted soft-thresholding algorithm which is used to solve the model of minimizing weighted nuclear norm. Focusing on the matrices generated randomly and image recovery problems, our proposed algorithm experimentally shows a significant improvement with respect to the accuracy and running time in comparison with the existing matrix completion algorithms.
(3) We give a new non-convex function-exponential type function to instead of rank function. We make some numerical comparison between our algorithms and the state-of-the-art method on randomly generated matrices, Jester data and image recovery problems, the results suggest that our method is more effective and promising.
(4) We propose a unified nonconvex model framework, by which many nonconvex models and some previously mentioned models can be obtained as special cases of the general framework. Then we use Difference of Convex functions (DC) programming and DC Algorithms (DCA) to solve the model. The experiment results suggest that our methods are more effective and promising.
3. We improve the hard thresholding algorithm. Most algorithms about hard thresholding use the negative gradient direction of the object function as search direction. But the main drawback of choosing the negative gradient direction is making the sequence of the iterations be subject to zigzags. Inspired by semi-iterative method, we present the semi-iterative hard thresholding algorithm. Compared to other iterative shrinkage algorithms, the performances of our proposed algorithm show a clear improvment in computation time.
4. We introduce the weighted nuclear norm for tensor and develop majorization-minimization weighted soft thresholding algorithm to solve tensor completion problems. In addition, we apply the semi-iterative method to the iterative hard thresholding algorithm for tensor completion problem and improve the descent direction. The experiment results demonstrate the effectiveness of the improved algorithm.
1、我们建立了指示函数与核范数的极小化模型,并利用迫近映射的概念设计了求解该模型的迫近点算法(PPA-IF).该模型的优点是不含正则参数,并将含噪声与不含噪声的矩阵完整化问题统一为一个模型.接下来,我们分析了算法的收敛性并给出严格的证明.数值结果表明相比较于其他提到的算法我们的算法在时间和精度方面方面都有很大的改进.
2、核范数是秩函数在单位球内的最佳凸逼近,但二者之间仍有很大的差异,为此我们提出了秩函数一系列非凸逼近.
(1)首先我们用光滑函数——双曲正切函数来代替秩函数建立了求解矩阵完整化问题的光滑函数模型并设计了梯度投影算法(HTA)来求解.对随机生成的低秩矩阵完整化问题和图像恢复问题的测试结果表明我们提出的HTA算法能够得到更高的精确度,同时对于少量抽样的问题也能获得比较好的恢复效果.
(2)为了减少核范数与秩函数之间的差距,我们在核范数的定义中添加了权向量并建立了求解矩阵完整化问题的加权核范数模型.随后利用极大极小方法设计了加权软阈值算法并通过对随机生成的矩阵完整化问题和图像恢复问题的实验说明我们提出的算法在准确性和计算时间上都有所提高.
(3)我们提出利用一个新的指数型函数来代替秩函数.同样的对随机生成的矩阵完整化问题、Jester数据和图像恢复问题的测试表明该方法能够得到更高的恢复精度.
(4)针对很多非凸模型,我们进行归纳并建立了一个非凸模型框架,在这个框架下,已有的非凸模型及我们前面所提出的一些非凸模型都可以归入其中.然后,针对此框架,我们采用DC规划及DC算法进行求解.数值结果表明我们的算法能够得到更好的恢复效果.
3、我们针对硬阈值类的算法进行了改进.许多硬阈值的算法都是用负梯度方向作为使函数值下降的搜索方向,但用负梯度方向会导致“之”字型路线而减慢收敛速度.我们受半迭代方法的启示设计了半迭代硬阈值算法.与其他的迭代硬阈值算法相比,改进后的算法在计算时间上有很大的提高.
4、我们将加权核范数模型引入张量完整化问题中,建立了张量情况下的非凸模型并利用极大极小加权软阈值方法来求解.另外,对于求解张量完整化问题的硬阈值方法,我们也应用半迭代方法在下降方向上进行改进,并得到了很好的效果.
The most important research aspect in matrix completion is to recover an unknown matrix with low-rank or approximately low-rank from constraints of its sample entries. A natural generalization of matrix completion is tensor completion. This thesis focuses on the model and the corresponding algorithm for the matrix completion problem and tensor completion problem. The major contributions of this thesis are as follow:
1. We propose a new unconstraint model for matrix completion problem based on nuclear norm and indicator function and design a proximal point algorithm (PPA-IF) to solve it. The advantage of the model is that there is no regularization parameter and it unifies two constrained optimization problems (noiseless and noisy matrix completion problems). Then the convergence of our algorithm is established strictly. The numerical results suggest that significant improvement can be achieved by our algorithm compared to the other reported methods.
2. The nuclear norm is the best convex approximation of the rank function over the set of matrices with spectral norm less than or equal to one, however there is a great difference between the two function. To reconcile this imbalance, we proposed a series of nonconvex models and the corresponding algorithms.
(1) Firstly, we use a smoothed function-Hyperbolic Tangent function to approximate the rank function, and then using gradient projection method (HTA) to minimize it. We report numerical results for solving randomly generated matrix completion problems and image recovery problems. Numerical results show that accuracy of HTA is higher than others and the requisite number of sampling to recover a matrix is typically reduced.
(2) In order to decrease the gap between the nuclear norm and the rank function, we add weight vector in the nuclear norm and build a model of minimizing weighted nuclear norm. Based on the majorization-minimization approach, we propose a weighted soft-thresholding algorithm which is used to solve the model of minimizing weighted nuclear norm. Focusing on the matrices generated randomly and image recovery problems, our proposed algorithm experimentally shows a significant improvement with respect to the accuracy and running time in comparison with the existing matrix completion algorithms.
(3) We give a new non-convex function-exponential type function to instead of rank function. We make some numerical comparison between our algorithms and the state-of-the-art method on randomly generated matrices, Jester data and image recovery problems, the results suggest that our method is more effective and promising.
(4) We propose a unified nonconvex model framework, by which many nonconvex models and some previously mentioned models can be obtained as special cases of the general framework. Then we use Difference of Convex functions (DC) programming and DC Algorithms (DCA) to solve the model. The experiment results suggest that our methods are more effective and promising.
3. We improve the hard thresholding algorithm. Most algorithms about hard thresholding use the negative gradient direction of the object function as search direction. But the main drawback of choosing the negative gradient direction is making the sequence of the iterations be subject to zigzags. Inspired by semi-iterative method, we present the semi-iterative hard thresholding algorithm. Compared to other iterative shrinkage algorithms, the performances of our proposed algorithm show a clear improvment in computation time.
4. We introduce the weighted nuclear norm for tensor and develop majorization-minimization weighted soft thresholding algorithm to solve tensor completion problems. In addition, we apply the semi-iterative method to the iterative hard thresholding algorithm for tensor completion problem and improve the descent direction. The experiment results demonstrate the effectiveness of the improved algorithm.
引文
1. Candes, E.J. and B. Recht, Exact matrix completion via convex optimization. Foundations of Computational mathematics,2009.9(6):p.717-772.
2. Ji, H., et al. Robust video denoising using low rank matrix completion, in Computer Vision and Pattern Recognition (CVPR),2010 IEEE Conference on.2010:IEEE.
3. Goldberg, A., et al. Transduction with matrix completion:Three birds with one stone, in Advances in neural information processing systems.2010.
4. Cabral, R.S., et al. Matrix completion for multi-label image classification, in Advances in Neural Information Processing Systems.2011.
5. Geng, X., et al., Face image modeling by multilinear subspace analysis with missing values. Systems, Man, and Cybernetics, Part B:Cybernetics, IEEE Transactions on,2011.41(3):p. 881-892.
6. Nie, F., et al., Semisupervised dimensionality reduction and classification through virtual label regression. Systems, Man, and Cybernetics, Part B:Cybernetics, IEEE Transactions on, 2011.41(3):p.675-685.
7. Nie, F., et al., Flexible manifold embedding:A framework for semi-supervised and unsupervised dimension reduction. Image Processing, IEEE Transactions on,2010.19(7):p. 1921-1932.
8. Weinberger, K.Q. and L.K. Saul, Unsupervised learning of image manifolds by semidefinite programming. International Journal of Computer Vision,2006.70(1):p.77-90.
9. Yan, S., et al., Nonlinear discriminant analysis on embedded manifold. Circuits and Systems for Video Technology, IEEE Transactions on,2007.17(4):p.468-477.
10. Biswas, P., et al., Semidefinite programming based algorithms for sensor network localization. ACM Transactions on Sensor Networks (TOSN),2006.2(2):p.188-220.
11. Wang, X., S. Wang, and D. Bi, Distributed visual-target-surveillance system in wireless sensor networks. Systems, Man, and Cybernetics, Part B:Cybernetics, IEEE Transactions on, 2009.39(5):p.1134-1146.
12. Aguiar, P.M. and J.M. Moura, Rank 1 weighted factorization for 3D structure recovery: algorithms and performance analysis. Pattern Analysis and Machine Intelligence, IEEE Transactions on,2003.25(9):p.1134-1149.
13. Dai, W. and O. Milenkovic. SET:an algorithm for consistent matrix completion, in Acoustics Speech and Signal Processing (ICASSP),2010 IEEE International Conference on.2010: IEEE.
14. Karatzoglou, A., M. Weimer, and A.J. Smola. Collaborative filtering on a budget, in International Conference on Artificial Intelligence and Statistics.2010.
15. Sarwar, B., et al. Analysis of recommendation algorithms for e-commerce, in Proceedings of the 2nd ACM conference on Electronic commerce.2000:ACM.
16. Weimer, M., et al. Cofi rank-maximum margin matrix factorization for collaborative ranking. in Advances in neural information processing systems.2007.
17. Smilde, A., R. Bro, and P. Geladi, Multi-way analysis:applications in the chemical sciences. 2005:Wiley. com.
18. Krooneberg, P.M., Three-mode principal component analysis:Theory and applications. Vol. 2.1983:DSWO press.
19. Comon, P., Tensor decompositions. Mathematics in Signal Processing V,2002:p.1-24.
20. Gandy, S., B. Recht, and I. Yamada, Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems,2011.27(2):p.025010.
21. Liu, J., et al. Tensor completion for estimating missing values in visual data, in Computer Vision,2009 IEEE 12th International Conference on.2009:IEEE.
22. Liu, Y. and F. Shang, An Efficient Matrix Factorization Method for Tensor Completion. 2013.
23. Fazel, M., Matrix rank minimization with applications.2002, PhD thesis, Stanford University.
24. Sturm, J.F., Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization methods and software,1999.11(1-4):p.625-653.
25. Tutuntu, R.H., K.C. Toh, and M.J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3. Mathematical programming,2003.95(2):p.189-217.
26. Cai, J.-F., E.J. Candes, and Z. Shen, A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization,2010.20(4):p.1956-1982.
27. Toh, K.-C. and S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pacific Journal of Optimization,2010.6(615-640): p.15.
28. Lin, Z., M. Chen, and Y. Ma, The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv preprint arXiv:1009.5055,2010.
29. Ma, S., D. Goldfarb, and L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization. Mathematical programming,2011.128(1-2):p.321-353.
30. Chen, C., B. He, and X. Yuan, Matrix completion via an alternating direction method. IMA Journal of Numerical Analysis,2012.32(1):p.227-245.
31. Liu, Y.-J., D. Sun, and K.-C. Toh, An implementable proximal point algorithmic framework for nuclear norm minimization. Mathematical programming,2012.133(1-2):p.399-436.
32. Meka, R., P. Jain, and I.S. Dhillon, Guaranteed rank minimization via singular value projection. arXiv preprint arXiv:0909.5457,2009.
33. Ghasemi, H., et al. SRF:Matrix completion based on smoothed rank function, in Acoustics, Speech and Signal Processing (ICASSP),2011 IEEE International Conference on.2011: IEEE.
34. Majumdar, A. and R.K. Ward, Some empirical advances in matrix completion. Signal Processing,2011.91(5):p.1334-1338.
35. Kolda, T.G. and B.W. Bader, Tensor decompositions and applications. SIAM review,2009. 51(3):p.455-500.
36. Kiers, H.A., Towards a standardized notation and terminology in multiway analysis. Journal of chemometrics,2000.14(3):p.105-122.
37. Rockafellar, R.T., Convex analysis. Vol.28.1997:Princeton university press.
38. Micchelli, C.A., L. Shen, and Y. Xu, Proximity algorithms for image models:denoising. Inverse Problems,2011.27(4):p.045009.
39. Li, Q., et al., A proximity algorithm accelerated by Gauss-Seidel iterations for L1/TV denoising models. Inverse Problems,2012.28(9):p.095003.
40. Larsen, R.M., PROPACK-Software for large and sparse SVD calculations. Available online. URL http://sun.stanford.edu/rmunk/PROPACK,2004.
41. Candes, E.J. and Y. Plan, Matrix completion with noise. Proceedings of the IEEE,2010. 98(6):p.925-936.
42. Bennett, J. and S. Lanning. The netflix prize, in Proceedings of KDD cup and workshop. 2007.
43. Tomasi, C. and T. Kanade, Shape and motion from image streams under orthography:a factorization method. International Journal of Computer Vision,1992.9(2):p.137-154.
44. Abernethy, J., et al., Low-rank matrix factorization with attributes. arXiv preprint cs/0611124, 2006.
45. Mohimani, H., M. Babaie-Zadeh, and C. Jutten, A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed< formula formulatype=. Signal Processing, IEEE Transactions on,2009.57(1):p.289-301.
46. Lewis, A.S., The convex analysis of unitarily invariant matrix functions. Journal of Convex Analysis,1995.2(1):p.173-183.
47. Amit, Y., et al. Uncovering shared structures in multiclass classification, in Proceedings of the 24th international conference on Machine learning.2007:ACM.
48. Evgeniou, A. and M. Pontil. Multi-task feature learning, in Advances in neural information processing systems:Proceedings of the 2006 conference.2007:The MIT Press.
49. Candes, E.J. and T. Tao, The power of convex relaxation:Near-optimal matrix completion. Information Theory, IEEE Transactions on,2010.56(5):p.2053-2080.
50. Gross, D., Recovering low-rank matrices from few coefficients in any basis. Information Theory, IEEE Transactions on,2011.57(3):p.1548-1566.
51. Keshavan, R.H., A. Montanari, and S. Oh, Matrix completion from noisy entries. The Journal of Machine Learning Research,2010.99:p.2057-2078.
52. Recht, B., A simpler approach to matrix completion. The Journal of Machine Learning Research,2011.12:p.3413-3430.
53. Zhu, Z., A.M.-C. So, and Y. Ye, Fast and near-optimal matrix completion via randomized basis pursuit. arXiv preprint arXiv:0905.1546,2009.
54. Lee, K. and Y. Bresler, Admira:Atomic decomposition for minimum rank approximation. Information Theory, IEEE Transactions on,2010.56(9):p.4402-4416.
55. Gaiffas, S. and G. Lecue, Weighted algorithms for compressed sensing and matrix completion. arXiv preprint arXiv:1107.1638,2011.
56. Hunter, D.R. and K. Lange, A tutorial on MM algorithms. The American Statistician,2004. 58(1):p.30-37.
57. Selesnick, I.W., Sparse Signal Restoration.2010, April.
58. Goldberg, K., et al., Eigentaste:A constant time collaborative filtering algorithm. Information Retrieval,2001.4(2):p.133-151.
59. Wen, Z., W. Yin, and Y. Zhang, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Mathematical Programming Computation,2012.4(4):p.333-361.
60. Wang, M., et al., Unified video annotation via multigraph learning. Circuits and Systems for Video Technology, IEEE Transactions on,2009.19(5):p.733-746.
61. Wang, M., et al., Beyond distance measurement:constructing neighborhood similarity for video annotation. Multimedia, IEEE Transactions on,2009.11(3):p.465-476.
62. Zhu, G., S. Yan, and Y. Ma. Image tag refinement towards low-rank, content-tag prior and error sparsity. in Proceedings of the international conference on Multimedia.2010:ACM.
63. Candes, E.J., M.B. Wakin, and S.P. Boyd, Enhancing sparsity by reweighted l 1 minimization. Journal of Fourier Analysis and Applications,2008.14(5-6):p.877-905.
64. Foucart, S. and M.-J. Lai, Sparsest solutions of underdetermined linear systems via lq-minimization for 0< q□ 1. Applied and Computational Harmonic Analysis,2009.26(3):p. 395-407.
65. Lai, M.-J. and J. Wang, An Unconstrained \ell_q Minimization with Oq\leql for Sparse Solution of Underdetermined Linear Systems. SIAM Journal on Optimization,2011.21(1):p. 82-101.
66. Lai, M.-J., Y. Xu, and W. Yin, Improved Iteratively Reweighted Least Squares for Unconstrained Smoothed\ell_q Minimization. SIAM Journal on Numerical Analysis,2013. 51(2):p.927-957.
67. Horst, R. and N.V. Thoai, DC programming:overview. Journal of Optimization Theory and Applications,1999.103(1):p.1-43.
68. Le Thi Hoai, A. and P.D. Tao, Solving a class of linearly constrained indefinite quadratic problems by DC algorithms. Journal of Global Optimization,1997.11(3):p.253-285.
69. Le Thi, H. and T.P. Dinh, DC programming. Theory, algorithms, applications:the state of the art. First InternationalWorkshop on Global Constrained Optimization and Constraint Satisfaction,2002.
70. Tao, P.D., The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Annals of Operations Research,2005. 133(1-4):p.23-46.
71. Tao, P.D. and L.T.H. An, Convex analysis approach to DC programming:theory, algorithms and applications. Acta Mathematica Vietnamica,1997.22(1):p.289-355.
72. Tao, P.D. and L.T.H. An, A DC optimization algorithm for solving the trust-region subprohlem. SIAM Journal on Optimization,1998.8(2):p.476-505.
73. Kong, L. and N. Xiu, Exact Low-rank Matrix Recovery via Nonconvex Schatten p-minimization. Asia-Pacific Journal of Operational Research,2013.30(03).
74. Liu, Z. and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification. SIAM Journal on Matrix Analysis and Applications, 2009.31(3):p.1235-1256.
75. Fazel, M., H. Hindi, and S.P. Boyd. A rank minimization heuristic with application to minimum order system approximation, in American Control Conference,2001. Proceedings of the 2001.2001:IEEE.
76. Elden, L., Matrix methods in data mining and pattern recognition. Vol.4.2007:SIAM.
77. Linial, N., E. London, and Y. Rabinovich, The geometry of graphs and some of its algorithmic applications. Combinatorica,1995.15(2):p.215-245.
78. Recht, B., M. Fazel, and P.A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review,2010.52(3):p.471-501.
79. Blumensath, T. and M.E. Davies, Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis,2009.27(3):p.265-274.
80. Blumensath, T. and M.E. Davies, Normalized iterative hard thresholding:Guaranteed stability and performance. Selected Topics in Signal Processing, IEEE Journal of,2010.4(2): p.298-309.
81. Tanner, J. and K. Wei, Normalized iterative hard thresholding for matrix completion. SIAM Journal on Scientific Computing,2013.35(5):p. S104-S125.
82. Hanke, M., Accelerated Landweber iterations for the solution of ill-posed equations. Numerische mathematik,1991.60(1):p.341-373.
83. LAndwEbER, L., An iteration formula for Fredholm integral equations of the first kind. American journal of mathematics,1951:p.615-624.
84. Exl, L., et al., FFT-based Kronecker product approximation to micromagnetic long-range interactions. arXiv preprint arXiv:1212.3509,2012.
85. Exl, L., et al., Fast stray field computation on tensor grids. Journal of Computational Physics, 2012.231(7):p.2840-2850.
86. Jondeau, E., E. Jurczenko, and M. Rockinger, Moment component analysis:An illustration with international stock markets.2010:University of Geneva.
87. Kazeev, V., O. Reichmann, and C. Schwab. hp-DG-QTT solution of high-dimensional degenerate diffusion equations.2012:Tech. Rep.2012-11, Seminar for Applied Mathematics, ETH Zurich.
88. Beylkin, G., J. Garcke, and M.J. Mohlenkamp, Multivariate regression and machine learning with sums of separable functions. SIAM Journal on Scientific Computing,2009.31(3):p. 1840-1857.
89. Yang, L., Z. Huang, and X. Shi, A Fixed Point Iterative Method for Low n-Rank Tensor Pursuit.2013.
90. Rauhut, H., R. Schneider, and Z. Stojanac. Low rank tensor recovery via iterative hard thresholding, in Proc.10th International Conference on Sampling Theory and Applications. 2013.
91. Grasedyck, L., Hierarchical singular value decomposition of tensors. SIAM Journal on Matrix Analysis and Applications,2010.31(4):p.2029-2054
2. Ji, H., et al. Robust video denoising using low rank matrix completion, in Computer Vision and Pattern Recognition (CVPR),2010 IEEE Conference on.2010:IEEE.
3. Goldberg, A., et al. Transduction with matrix completion:Three birds with one stone, in Advances in neural information processing systems.2010.
4. Cabral, R.S., et al. Matrix completion for multi-label image classification, in Advances in Neural Information Processing Systems.2011.
5. Geng, X., et al., Face image modeling by multilinear subspace analysis with missing values. Systems, Man, and Cybernetics, Part B:Cybernetics, IEEE Transactions on,2011.41(3):p. 881-892.
6. Nie, F., et al., Semisupervised dimensionality reduction and classification through virtual label regression. Systems, Man, and Cybernetics, Part B:Cybernetics, IEEE Transactions on, 2011.41(3):p.675-685.
7. Nie, F., et al., Flexible manifold embedding:A framework for semi-supervised and unsupervised dimension reduction. Image Processing, IEEE Transactions on,2010.19(7):p. 1921-1932.
8. Weinberger, K.Q. and L.K. Saul, Unsupervised learning of image manifolds by semidefinite programming. International Journal of Computer Vision,2006.70(1):p.77-90.
9. Yan, S., et al., Nonlinear discriminant analysis on embedded manifold. Circuits and Systems for Video Technology, IEEE Transactions on,2007.17(4):p.468-477.
10. Biswas, P., et al., Semidefinite programming based algorithms for sensor network localization. ACM Transactions on Sensor Networks (TOSN),2006.2(2):p.188-220.
11. Wang, X., S. Wang, and D. Bi, Distributed visual-target-surveillance system in wireless sensor networks. Systems, Man, and Cybernetics, Part B:Cybernetics, IEEE Transactions on, 2009.39(5):p.1134-1146.
12. Aguiar, P.M. and J.M. Moura, Rank 1 weighted factorization for 3D structure recovery: algorithms and performance analysis. Pattern Analysis and Machine Intelligence, IEEE Transactions on,2003.25(9):p.1134-1149.
13. Dai, W. and O. Milenkovic. SET:an algorithm for consistent matrix completion, in Acoustics Speech and Signal Processing (ICASSP),2010 IEEE International Conference on.2010: IEEE.
14. Karatzoglou, A., M. Weimer, and A.J. Smola. Collaborative filtering on a budget, in International Conference on Artificial Intelligence and Statistics.2010.
15. Sarwar, B., et al. Analysis of recommendation algorithms for e-commerce, in Proceedings of the 2nd ACM conference on Electronic commerce.2000:ACM.
16. Weimer, M., et al. Cofi rank-maximum margin matrix factorization for collaborative ranking. in Advances in neural information processing systems.2007.
17. Smilde, A., R. Bro, and P. Geladi, Multi-way analysis:applications in the chemical sciences. 2005:Wiley. com.
18. Krooneberg, P.M., Three-mode principal component analysis:Theory and applications. Vol. 2.1983:DSWO press.
19. Comon, P., Tensor decompositions. Mathematics in Signal Processing V,2002:p.1-24.
20. Gandy, S., B. Recht, and I. Yamada, Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems,2011.27(2):p.025010.
21. Liu, J., et al. Tensor completion for estimating missing values in visual data, in Computer Vision,2009 IEEE 12th International Conference on.2009:IEEE.
22. Liu, Y. and F. Shang, An Efficient Matrix Factorization Method for Tensor Completion. 2013.
23. Fazel, M., Matrix rank minimization with applications.2002, PhD thesis, Stanford University.
24. Sturm, J.F., Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization methods and software,1999.11(1-4):p.625-653.
25. Tutuntu, R.H., K.C. Toh, and M.J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3. Mathematical programming,2003.95(2):p.189-217.
26. Cai, J.-F., E.J. Candes, and Z. Shen, A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization,2010.20(4):p.1956-1982.
27. Toh, K.-C. and S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pacific Journal of Optimization,2010.6(615-640): p.15.
28. Lin, Z., M. Chen, and Y. Ma, The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv preprint arXiv:1009.5055,2010.
29. Ma, S., D. Goldfarb, and L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization. Mathematical programming,2011.128(1-2):p.321-353.
30. Chen, C., B. He, and X. Yuan, Matrix completion via an alternating direction method. IMA Journal of Numerical Analysis,2012.32(1):p.227-245.
31. Liu, Y.-J., D. Sun, and K.-C. Toh, An implementable proximal point algorithmic framework for nuclear norm minimization. Mathematical programming,2012.133(1-2):p.399-436.
32. Meka, R., P. Jain, and I.S. Dhillon, Guaranteed rank minimization via singular value projection. arXiv preprint arXiv:0909.5457,2009.
33. Ghasemi, H., et al. SRF:Matrix completion based on smoothed rank function, in Acoustics, Speech and Signal Processing (ICASSP),2011 IEEE International Conference on.2011: IEEE.
34. Majumdar, A. and R.K. Ward, Some empirical advances in matrix completion. Signal Processing,2011.91(5):p.1334-1338.
35. Kolda, T.G. and B.W. Bader, Tensor decompositions and applications. SIAM review,2009. 51(3):p.455-500.
36. Kiers, H.A., Towards a standardized notation and terminology in multiway analysis. Journal of chemometrics,2000.14(3):p.105-122.
37. Rockafellar, R.T., Convex analysis. Vol.28.1997:Princeton university press.
38. Micchelli, C.A., L. Shen, and Y. Xu, Proximity algorithms for image models:denoising. Inverse Problems,2011.27(4):p.045009.
39. Li, Q., et al., A proximity algorithm accelerated by Gauss-Seidel iterations for L1/TV denoising models. Inverse Problems,2012.28(9):p.095003.
40. Larsen, R.M., PROPACK-Software for large and sparse SVD calculations. Available online. URL http://sun.stanford.edu/rmunk/PROPACK,2004.
41. Candes, E.J. and Y. Plan, Matrix completion with noise. Proceedings of the IEEE,2010. 98(6):p.925-936.
42. Bennett, J. and S. Lanning. The netflix prize, in Proceedings of KDD cup and workshop. 2007.
43. Tomasi, C. and T. Kanade, Shape and motion from image streams under orthography:a factorization method. International Journal of Computer Vision,1992.9(2):p.137-154.
44. Abernethy, J., et al., Low-rank matrix factorization with attributes. arXiv preprint cs/0611124, 2006.
45. Mohimani, H., M. Babaie-Zadeh, and C. Jutten, A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed< formula formulatype=. Signal Processing, IEEE Transactions on,2009.57(1):p.289-301.
46. Lewis, A.S., The convex analysis of unitarily invariant matrix functions. Journal of Convex Analysis,1995.2(1):p.173-183.
47. Amit, Y., et al. Uncovering shared structures in multiclass classification, in Proceedings of the 24th international conference on Machine learning.2007:ACM.
48. Evgeniou, A. and M. Pontil. Multi-task feature learning, in Advances in neural information processing systems:Proceedings of the 2006 conference.2007:The MIT Press.
49. Candes, E.J. and T. Tao, The power of convex relaxation:Near-optimal matrix completion. Information Theory, IEEE Transactions on,2010.56(5):p.2053-2080.
50. Gross, D., Recovering low-rank matrices from few coefficients in any basis. Information Theory, IEEE Transactions on,2011.57(3):p.1548-1566.
51. Keshavan, R.H., A. Montanari, and S. Oh, Matrix completion from noisy entries. The Journal of Machine Learning Research,2010.99:p.2057-2078.
52. Recht, B., A simpler approach to matrix completion. The Journal of Machine Learning Research,2011.12:p.3413-3430.
53. Zhu, Z., A.M.-C. So, and Y. Ye, Fast and near-optimal matrix completion via randomized basis pursuit. arXiv preprint arXiv:0905.1546,2009.
54. Lee, K. and Y. Bresler, Admira:Atomic decomposition for minimum rank approximation. Information Theory, IEEE Transactions on,2010.56(9):p.4402-4416.
55. Gaiffas, S. and G. Lecue, Weighted algorithms for compressed sensing and matrix completion. arXiv preprint arXiv:1107.1638,2011.
56. Hunter, D.R. and K. Lange, A tutorial on MM algorithms. The American Statistician,2004. 58(1):p.30-37.
57. Selesnick, I.W., Sparse Signal Restoration.2010, April.
58. Goldberg, K., et al., Eigentaste:A constant time collaborative filtering algorithm. Information Retrieval,2001.4(2):p.133-151.
59. Wen, Z., W. Yin, and Y. Zhang, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Mathematical Programming Computation,2012.4(4):p.333-361.
60. Wang, M., et al., Unified video annotation via multigraph learning. Circuits and Systems for Video Technology, IEEE Transactions on,2009.19(5):p.733-746.
61. Wang, M., et al., Beyond distance measurement:constructing neighborhood similarity for video annotation. Multimedia, IEEE Transactions on,2009.11(3):p.465-476.
62. Zhu, G., S. Yan, and Y. Ma. Image tag refinement towards low-rank, content-tag prior and error sparsity. in Proceedings of the international conference on Multimedia.2010:ACM.
63. Candes, E.J., M.B. Wakin, and S.P. Boyd, Enhancing sparsity by reweighted l 1 minimization. Journal of Fourier Analysis and Applications,2008.14(5-6):p.877-905.
64. Foucart, S. and M.-J. Lai, Sparsest solutions of underdetermined linear systems via lq-minimization for 0< q□ 1. Applied and Computational Harmonic Analysis,2009.26(3):p. 395-407.
65. Lai, M.-J. and J. Wang, An Unconstrained \ell_q Minimization with Oq\leql for Sparse Solution of Underdetermined Linear Systems. SIAM Journal on Optimization,2011.21(1):p. 82-101.
66. Lai, M.-J., Y. Xu, and W. Yin, Improved Iteratively Reweighted Least Squares for Unconstrained Smoothed\ell_q Minimization. SIAM Journal on Numerical Analysis,2013. 51(2):p.927-957.
67. Horst, R. and N.V. Thoai, DC programming:overview. Journal of Optimization Theory and Applications,1999.103(1):p.1-43.
68. Le Thi Hoai, A. and P.D. Tao, Solving a class of linearly constrained indefinite quadratic problems by DC algorithms. Journal of Global Optimization,1997.11(3):p.253-285.
69. Le Thi, H. and T.P. Dinh, DC programming. Theory, algorithms, applications:the state of the art. First InternationalWorkshop on Global Constrained Optimization and Constraint Satisfaction,2002.
70. Tao, P.D., The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Annals of Operations Research,2005. 133(1-4):p.23-46.
71. Tao, P.D. and L.T.H. An, Convex analysis approach to DC programming:theory, algorithms and applications. Acta Mathematica Vietnamica,1997.22(1):p.289-355.
72. Tao, P.D. and L.T.H. An, A DC optimization algorithm for solving the trust-region subprohlem. SIAM Journal on Optimization,1998.8(2):p.476-505.
73. Kong, L. and N. Xiu, Exact Low-rank Matrix Recovery via Nonconvex Schatten p-minimization. Asia-Pacific Journal of Operational Research,2013.30(03).
74. Liu, Z. and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification. SIAM Journal on Matrix Analysis and Applications, 2009.31(3):p.1235-1256.
75. Fazel, M., H. Hindi, and S.P. Boyd. A rank minimization heuristic with application to minimum order system approximation, in American Control Conference,2001. Proceedings of the 2001.2001:IEEE.
76. Elden, L., Matrix methods in data mining and pattern recognition. Vol.4.2007:SIAM.
77. Linial, N., E. London, and Y. Rabinovich, The geometry of graphs and some of its algorithmic applications. Combinatorica,1995.15(2):p.215-245.
78. Recht, B., M. Fazel, and P.A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review,2010.52(3):p.471-501.
79. Blumensath, T. and M.E. Davies, Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis,2009.27(3):p.265-274.
80. Blumensath, T. and M.E. Davies, Normalized iterative hard thresholding:Guaranteed stability and performance. Selected Topics in Signal Processing, IEEE Journal of,2010.4(2): p.298-309.
81. Tanner, J. and K. Wei, Normalized iterative hard thresholding for matrix completion. SIAM Journal on Scientific Computing,2013.35(5):p. S104-S125.
82. Hanke, M., Accelerated Landweber iterations for the solution of ill-posed equations. Numerische mathematik,1991.60(1):p.341-373.
83. LAndwEbER, L., An iteration formula for Fredholm integral equations of the first kind. American journal of mathematics,1951:p.615-624.
84. Exl, L., et al., FFT-based Kronecker product approximation to micromagnetic long-range interactions. arXiv preprint arXiv:1212.3509,2012.
85. Exl, L., et al., Fast stray field computation on tensor grids. Journal of Computational Physics, 2012.231(7):p.2840-2850.
86. Jondeau, E., E. Jurczenko, and M. Rockinger, Moment component analysis:An illustration with international stock markets.2010:University of Geneva.
87. Kazeev, V., O. Reichmann, and C. Schwab. hp-DG-QTT solution of high-dimensional degenerate diffusion equations.2012:Tech. Rep.2012-11, Seminar for Applied Mathematics, ETH Zurich.
88. Beylkin, G., J. Garcke, and M.J. Mohlenkamp, Multivariate regression and machine learning with sums of separable functions. SIAM Journal on Scientific Computing,2009.31(3):p. 1840-1857.
89. Yang, L., Z. Huang, and X. Shi, A Fixed Point Iterative Method for Low n-Rank Tensor Pursuit.2013.
90. Rauhut, H., R. Schneider, and Z. Stojanac. Low rank tensor recovery via iterative hard thresholding, in Proc.10th International Conference on Sampling Theory and Applications. 2013.
91. Grasedyck, L., Hierarchical singular value decomposition of tensors. SIAM Journal on Matrix Analysis and Applications,2010.31(4):p.2029-2054
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |