Previous Articles     Next Articles

FAST ALGORITHMS FOR HIGHER-ORDER SINGULAR VALUE DECOMPOSITION FROM INCOMPLETE DATA

Yangyang Xu   

  1. Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, USA
  • Received:2016-05-16 Revised:2016-08-09 Online:2017-07-15 Published:2017-07-15

Yangyang Xu. FAST ALGORITHMS FOR HIGHER-ORDER SINGULAR VALUE DECOMPOSITION FROM INCOMPLETE DATA[J]. Journal of Computational Mathematics, 2017, 35(4): 397-422.

Higher-order singular value decomposition (HOSVD) is an efficient way for data reduction and also eliciting intrinsic structure of multi-dimensional array data. It has been used in many applications, and some of them involve incomplete data. To obtain HOSVD of the data with missing values, one can first impute the missing entries through a certain tensor completion method and then perform HOSVD to the reconstructed data. However, the two-step procedure can be inefficient and does not make reliable decomposition. In this paper, we formulate an incomplete HOSVD problem and combine the two steps into solving a single optimization problem, which simultaneously achieves imputation of missing values and also tensor decomposition.
We also present one algorithm for solving the problem based on block coordinate update (BCU). Global convergence of the algorithm is shown under mild assumptions and implies that of the popular higher-order orthogonality iteration (HOOI) method, and thus we, for the first time, give global convergence of HOOI.
In addition, we compare the proposed method to state-of-the-art ones for solving incomplete HOSVD and also low-rank tensor completion problems and demonstrate the superior performance of our method over other compared ones. Furthermore, we apply it to face recognition and MRI image reconstruction to show its practical performance.

CLC Number: 

[1] E. Acar, D. M. Dunlavy, T. G. Kolda, and M. Mørup, Scalable tensor factorizations with missing data., in Proceedings of the SIAM International Conference on Data Mining, (2010), 701-712.

[2] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2(2009), 183-202.

[3] D. P. Bertsekas, Nonlinear Programming, Athena Scientific, September 1999.

[4] A. M. Buchanan and A. W. Fitzgibbon, Damped newton algorithms for matrix factorization with missing data, in IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2(2005), 316-322.

[5] Y. Chen, C. Hsu, and H. Liao, Simultaneous tensor decomposition and completion using factor priors, (2013).

[6] L. De Lathauwer, B. De Moor, and J. Vandewalle, A multilinear singular value decomposition, SIAM Journal on Matrix Analysis and Applications, 21(2000), 1253-1278.

[7] L. De Lathauwer, B. De Moor, and J. Vandewalle, On the best rank-1 and rank-(r1, r12..., rn) approximation of higher-order tensors, SIAM Journal on Matrix Analysis and Applications, 21(2000), 1324-1342.

[8] M. Filipovi? and A. Juki?, Tucker factorization with missing data with application to low-n-rank tensor completion, Multidimensional Systems and Signal Processing, (2013), 1-16.

[9] K. R. Gabriel and S. Zamir, Lower rank approximation of matrices by least squares with any choice of weights, Technometrics, 21(1979), 489-498.

[10] S. Gandy, B. Recht, and I. Yamada, Tensor completion and low-n-rank tensor recovery via convex optimization, Inverse Problems, 27(2011), 1-19.

[11] X. Geng and K. Smith-Miles, Facial age estimation by multilinear subspace analysis, in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), (2009), 865-868.

[12] X. Geng, K. Smith-Miles, Z.-H. Zhou, and L. Wang, Face image modeling by multilinear subspace analysis with missing values, IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 41(2011), 881-892.

[13] A. S. Georghiades, P. N. Belhumeur, and D. Kriegman, From few to many:Illumination cone models for face recognition under variable lighting and pose, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(2001), 643-660.

[14] G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, third ed., 1996.

[15] R. Horn and C. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1991.

[16] B. Huang, C. Mu, D. Goldfarb, and J. Wright, Provable low-rank tensor recovery, Pacific Journal of Optimization, 11(2015), 339-364.

[17] T. Kolda and B. Bader, Tensor decompositions and applications, SIAM Review, 51(2009), 455-500.

[18] N. Kreimer and M. D. Sacchi, A tensor higher-order singular value decomposition for prestack seismic data noise reduction and interpolation, Geophysics, 77(2012), 113-122.

[19] D. Kressner, M. Steinlechner, and B. Vandereycken, Low-rank tensor completion by riemannian optimization, BIT Numerical Mathematics, (2013), 1-22.

[20] M. Kurucz, A. A. Benczúr, and K. Csalogány, Methods for large scale SVD with missing values, in Proceedings of KDD Cup and Workshop, 12, 2007, 31-38.

[21] K.-C. Lee, J. Ho, and D. Kriegman, Acquiring linear subspaces for face recognition under variable lighting, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(2005), 684-698.

[22] Q. Ling, Y. Xu, W. Yin, and Z. Wen, Decentralized low-rank matrix completion, in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), (2012), 2925-2928.

[23] J. Liu, P. Musialski, P. Wonka, and J. Ye, Tensor completion for estimating missing values in visual data, IEEE Transactions on Pattern Analysis and Machine Intelligence, (2013), 208-220.

[24] Y. Liu, F. Shang, H. Cheng, J. Cheng, and H. Tong, Factor matrix trace norm minimization for low-rank tensor completion, Proceedings of the 2014 SIAM International Conference on Data Mining, (2014).

[25] L. Mirsky, A trace inequality of John von Neumann, Monatshefte für mathematik, 79(1975), 303-306.

[26] M. Mørup, L. Hansen, and S. Arnfred, Algorithms for sparse nonnegative Tucker decompositions, Neural Computation, 20(2008), 2112-2131.

[27] C. Mu, B. Huang, J. Wright, and D. Goldfarb, Square deal:Lower bounds and improved relaxations for tensor recovery, arXiv preprint arXiv:1307.5870, (2013).

[28] L. Omberg, G. H. Golub, and O. Alter, A tensor higher-order singular value decomposition for integrative analysis of dna microarray data from different studies, Proceedings of the National Academy of Sciences, 104(2007), 18371-18376.

[29] P. Paatero, A weighted non-negative least squares algorithm for three-way parafacfactor analysis, Chemometrics and Intelligent Laboratory Systems, 38(1997), 223-242.

[30] Z. Peng, T. Wu, Y. Xu, M. Yan, and W. Yin, Coordinate Friendly Structures, Algorithms and Applications, Annals of Mathematical Sciences and Applications, 1(2016), 57-119.

[31] A. Phan, P. Tichavsky, and A. Cichocki, Damped Gauss-Newton algorithm for nonnegative tucker decomposition, in IEEE Statistical Signal Processing Workshop (SSP), (2011), 665-668.

[32] B. Romera-Paredes and M. Pontil, A new convex relaxation for tensor completion, arXiv preprint arXiv:1307.4653, (2013).

[33] A. Ruhe, Numerical computation of principal components when several observations are missing, University of Umea, Institute of Mathematics and Statistics Report, (1974).

[34] B. Savas and L. Eldén, Handwritten digit classification using higher order singular value decomposition, Pattern recognition, 40(2007), 993-1003.

[35] L. Sorber, M. Van Barel, and L. De Lathauwer, Structured data fusion, ESAT-STADIUS, KU Leuven, Belgium, Tech. Rep, (2013), 13-177.

[36] N. Srebro and T. Jaakkola, Weighted low-rank approximations, in Machine Learning International Workshop, 20(2003), 720-727.

[37] J.-T. Sun, H.-J. Zeng, H. Liu, Y. Lu, and Z. Chen, Cubesvd:a novel approach to personalized web search, in Proceedings of the 14th international conference on World Wide Web, ACM, 2005, 382-390.

[38] G. Tomasi and R. Bro, Parafac and missing values, Chemometrics and Intelligent Laboratory Systems, 75(2005), 163-180.

[39] A. Uschmajew, A new convergence proof for the high-order power method and generalizations, Arxiv preprint arXiv:1407.4586, (2014).

[40] M. A. O. Vasilescu, Human motion signatures:Analysis, synthesis, recognition, in Proceedings of IEEE 16th International Conference on Pattern Recognition, 3(2002), 456-460.

[41] M. A. O. Vasilescu and D. Terzopoulos, Multilinear image analysis for facial recognition, in IEEE Computer Society International Conference on Pattern Recognition, 2(2002), 20511-20511.

[42] B. Walczak and D. Massart, Dealing with missing data:Part i, Chemometrics and Intelligent Laboratory Systems, 58(2001), 15-27.

[43] Z. Wen, W. Yin, and Y. Zhang, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Mathematical Programming Computation, 4(2012), 333-361.

[44] Y. Xu, Alternating proximal gradient method for sparse nonnegative Tucker decomposition, Mathematical Programming Computation, 7(2015), 39-70.

[45] Y. Xu, R. Hao, W. Yin, and Z. Su, Parallel matrix factorization for low-rank tensor completion, Inverse Problems and Imaging, 9(2015), 601-624.

[46] Y. Xu and W. Yin, A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM Journal on Imaging Sciences, 6(2013), 1758-1789.

[47] Y. Xu, W. Yin, Z. Wen, and Y. Zhang, An alternating direction algorithm for matrix completion with nonnegative factors, Frontiers of Mathematics in China, 7(2012), 365-384.

[48] M. Yuan and C.-H. Zhang, On tensor completion via nuclear norm minimization, Foundations of Computational Mathematics, (2015), 1-38.

[49] T. Zhang and G. H. Golub, Rank-one approximation to high order tensors, SIAM Journal on Matrix Analysis and Applications, 23(2001), 534-550.

[50] Q. Zhao, L. Zhang, and A. Cichocki, Bayesian CP factorization of incomplete tensors with automatic rank determination, arXiv preprint arXiv:1401.6497, (2014).
[1] Xiaoyu Wang, Ya-xiang Yuan. STOCHASTIC TRUST-REGION METHODS WITH TRUST-REGION RADIUS DEPENDING ON PROBABILISTIC MODELS [J]. Journal of Computational Mathematics, 2022, 40(2): 294-334.
[2] Yuting Chen, Mingyuan Cao, Yueting Yang, Qingdao Huang. AN ADAPTIVE TRUST-REGION METHOD FOR GENERALIZED EIGENVALUES OF SYMMETRIC TENSORS [J]. Journal of Computational Mathematics, 2021, 39(3): 358-374.
[3] Keke Zhang, Hongwei Liu, Zexian Liu. A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION [J]. Journal of Computational Mathematics, 2021, 39(2): 159-177.
[4] Wenjuan Xue, Weiai Liu. A MULTIDIMENSIONAL FILTER SQP ALGORITHM FOR NONLINEAR PROGRAMMING [J]. Journal of Computational Mathematics, 2020, 38(5): 683-704.
[5] Meng Huang, Zhiqiang Xu. SOLVING SYSTEMS OF QUADRATIC EQUATIONS VIA EXPONENTIAL-TYPE GRADIENT DESCENT ALGORITHM [J]. Journal of Computational Mathematics, 2020, 38(4): 638-660.
[6] Bothina El-Sobky, Abdallah Abotahoun. A TRUST-REGION ALGORITHM FOR SOLVING MINI-MAX PROBLEM [J]. Journal of Computational Mathematics, 2018, 36(6): 776-791.
[7] Fan Jiang, Deren Han, Xiaofei Zhang. A TRUST-REGION-BASED ALTERNATING LEAST-SQUARES ALGORITHM FOR TENSOR DECOMPOSITIONS [J]. Journal of Computational Mathematics, 2018, 36(3): 351-373.
[8] Caixia Kou, Zhongwen Chen, Yuhong Dai, Haifei Han. AN AUGMENTED LAGRANGIAN TRUST REGION METHOD WITH A BI-OBJECT STRATEGY [J]. Journal of Computational Mathematics, 2018, 36(3): 331-350.
[9] Jinkui Liu, Shengjie Li. SPECTRAL DY-TYPE PROJECTION METHOD FOR NONLINEAR MONOTONE SYSTEM OF EQUATIONS [J]. Journal of Computational Mathematics, 2015, 33(4): 341-355.
[10] Jinghui Liu, Changfeng Ma. A NEW NONMONOTONE TRUST REGION ALGORITHM FOR SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2014, 32(4): 476-490.
[11] Fusheng Wang, Chuanlong Wang, Li Wang. A NEW TRUST-REGION ALGORITHM FOR FINITE MINIMAX PROBLEM [J]. Journal of Computational Mathematics, 2012, 30(3): 262-278.
[12] Xuebin Wang, Changfeng Ma, Meiyan Li. A SMOOTHING TRUST REGION METHOD FOR NCPS BASED ON THE SMOOTHING GENERALIZED FISCHER-BURMEISTER FUNCTION [J]. Journal of Computational Mathematics, 2011, 29(3): 261-286.
[13] Duoquan Li. A NEW SQP-FILTER METHOD FOR SOLVING NONLINEAR PROGRAMMING PROBLEMS [J]. Journal of Computational Mathematics, 2006, 24(5): 609-634.
[14] Chang-yin Zhou,Guo-ping He,Yong-li Wang . A NEW CONSTRAINTS IDENTIFICATION TECHNIQUE-BASED QP-FREE ALGORITHM FOR THE SOLUTION OF INEQUALITY CONSTRAINED MINIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2006, 24(5): 591-608.
[15] Xin-long Luo. Singly Diagonally Implicit Runge-Kutta Methods Combining Line Search Techniques for Unconstrained Optimization [J]. Journal of Computational Mathematics, 2005, 23(2): 153-164.
Viewed
Full text


Abstract