American Institute of Mathematical Sciences

Advanced
May  2015, 9(2): 601-624. doi: 10.3934/ipi.2015.9.601

Parallel matrix factorization for low-rank tensor completion

Yangyang Xu 1, , Ruru Hao 2, , Wotao Yin 3, and  Zhixun Su 2,

1. 

Department of Computational and Applied Mathematics, Rice University, Houston, TX 77005
2. 

School of Mathematical Sciences, Dalian University of Technology, Dalian, China, China
3. 

Department of Mathematics, University of California, Los Angeles, CA 90095-1555

Received  December 2013 Revised  October 2014 Published  March 2015

Higher-order low-rank tensors naturally arise in many applications including hyperspectral data recovery, video inpainting, seismic data reconstruction, and so on. We propose a new model to recover a low-rank tensor by simultaneously performing low-rank matrix factorizations to the all-mode matricizations of the underlying tensor. An alternating minimization algorithm is applied to solve the model, along with two adaptive rank-adjusting strategies when the exact rank is not known.
    Phase transition plots reveal that our algorithm can recover a variety of synthetic low-rank tensors from significantly fewer samples than the compared methods, which include a matrix completion method applied to tensor recovery and two state-of-the-art tensor completion methods. Further tests on real-world data show similar advantages. Although our model is non-convex, our algorithm performs consistently throughout the tests and gives better results than the compared methods, some of which are based on convex models. In addition, subsequence convergence of our algorithm can be established in the sense that any limit point of the iterates satisfies the KKT condtions.
Keywords: low-rank tensor completion, low-rank matrix completion, alternating least squares, non-convex optimization., Higher-order tensor.
Mathematics Subject Classification: Primary: 94A08, 94A12; Secondary: 90C9.
Citation: Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems & Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601
References:
[1]

J. Cai, E. Candes and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20 (2010), 1956-1982. doi: 10.1137/080738970.  Google Scholar

[2]

E. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9 (2009), 717-772. doi: 10.1007/s10208-009-9045-5.  Google Scholar

[3]

C. Chen, B. He and X. Yuan, Matrix completion via an alternating direction method, IMA Journal of Numerical Analysis, 32 (2012), 227-245. doi: 10.1093/imanum/drq039.  Google Scholar

[4]

S. Gandy, B. Recht and I. Yamada, Tensor completion and low-n-rank tensor recovery via convex optimization, Inverse Problems, 27 (2011), 025010, 1-19. doi: 10.1088/0266-5611/27/2/025010.  Google Scholar

[5]

L. Grippo and M. Sciandrone, On the convergence of the block nonlinear Gauss-Seidel method under convex constraints, Oper. Res. Lett., 26 (2000), 127-136. doi: 10.1016/S0167-6377(99)00074-7.  Google Scholar

[6]

B. Jiang, S. Ma and S. Zhang, Tensor principal component analysis via convex optimization, Mathematical Programming, (2014), 1-35. doi: 10.1007/s10107-014-0774-0.  Google Scholar

[7]

H. A. L. Kiers, Towards a standardized notation and terminology in multiway analysis, Journal of Chemometrics, 14 (2000), 105-122. doi: 10.1002/1099-128X(200005/06)14:3<105::AID-CEM582>3.0.CO;2-I.  Google Scholar

[8]

M. Kilmer, K. Braman, N. Hao and R. Hoover, Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging, SIAM Journal on Matrix Analysis and Applications, 34 (2013), 148-172. doi: 10.1137/110837711.  Google Scholar

[9]

T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM review, 51 (2009), 455-500. doi: 10.1137/07070111X.  Google Scholar

[10]

T. G. Kolda, B. W. Bader and J. P. Kenny, Higher-order web link analysis using multilinear algebra, in Data Mining, Fifth IEEE International Conference on, IEEE, 2005. doi: 10.1109/ICDM.2005.77.  Google Scholar

[11]

N. Kreimer and M. D. Sacchi, A tensor higher-order singular value decomposition for prestack seismic data noise reduction and interpolation, Geophysics, 77 (2012), V113-V122. doi: 10.1190/geo2011-0399.1.  Google Scholar

[12]

D. Kressner, M. Steinlechner and B. Vandereycken, Low-rank tensor completion by riemannian optimization, BIT, 54 (2014), 447-468. doi: 10.1007/s10543-013-0455-z.  Google Scholar

[13]

M. Lai, Y. Xu and W. Yin, Improved iteratively reweighted least squares for unconstrained smoothed $l_q$ minimization, SIAM Journal on Numerical Analysis, 51 (2013), 927-957. doi: 10.1137/110840364.  Google Scholar

[14]

N. Li and B. Li, Tensor completion for on-board compression of hyperspectral images, in 2010 17th IEEE International Conference on Image Processing (ICIP), IEEE, 2010, 517-520. doi: 10.1109/ICIP.2010.5651225.  Google Scholar

[15]

Q. Ling, Y. Xu, W. Yin and Z. Wen, Decentralized low-rank matrix completion, in 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2012, 2925-2928. doi: 10.1109/ICASSP.2012.6288528.  Google Scholar

[16]

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, (2012), 208-220. doi: 10.1109/TPAMI.2012.39.  Google Scholar

[17]

S. Ma, D. Goldfarb and L. Chen, Fixed point and bregman iterative methods for matrix rank minimization, Mathematical Programming, 128 (2011), 321-353. doi: 10.1007/s10107-009-0306-5.  Google Scholar

[18]

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

[19]

K. A. Patwardhan, G. Sapiro and M. Bertalmío, Video inpainting under constrained camera motion, IEEE Transactions on Image Processing, 16 (2007), 545-553. doi: 10.1109/TIP.2006.888343.  Google Scholar

[20]

B. Recht, M. Fazel and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52 (2010), 471-501. doi: 10.1137/070697835.  Google Scholar

[21]

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

[22]

A. C. Sauve, A. O. Hero III, W. Leslie Rogers, S. J. Wilderman and N. H. Clinthorne, 3d image reconstruction for a compton spect camera model, Nuclear Science, IEEE Transactions on, 46 (1999), 2075-2084. doi: 10.1109/23.819285.  Google Scholar

[23]

J. Sun, H. 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. doi: 10.1145/1060745.1060803.  Google Scholar

[24]

K. C. Toh and S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pacific Journal of Optimization, 6 (2010), 615-640.  Google Scholar

[25]

P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109 (2001), 475-494. doi: 10.1023/A:1017501703105.  Google Scholar

[26]

L. R. Tucker, Some mathematical notes on three-mode factor analysis, Psychometrika, 31 (1966), 279-311. doi: 10.1007/BF02289464.  Google Scholar

[27]

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. doi: 10.1007/s12532-012-0044-1.  Google Scholar

[28]

Z. Xing, M. Zhou, A. Castrodad, G. Sapiro and L. Carin, Dictionary learning for noisy and incomplete hyperspectral images, SIAM Journal on Imaging Sciences, 5 (2012), 33-56. doi: 10.1137/110837486.  Google Scholar

[29]

Y. Xu and W. Yin, A block coordinate descent method for regularized multi-convex optimization with applications to nonnegative tensor factorization and completion, SIAM Journal on Imaging Sciences, 6 (2013), 1758-1789. doi: 10.1137/120887795.  Google Scholar

[30]

Y. Xu and W. Yin, A globally convergent algorithm for nonconvex optimization based on block coordinate update, arXiv:1410.1386, (2014). Google Scholar

[31]

Y. Xu, W. Yin, Z. Wen and Y. Zhang, An alternating direction algorithm for matrix completion with nonnegative factors, Journal of Frontiers of Mathematics in China, Special Issue on Computational Mathematics, 7 (2011), 365-384. doi: 10.1007/s11464-012-0194-5.  Google Scholar

[32]

Z. Zhang, G. Ely, S. Aeron, N. Hao and M. Kilmer, Novel factorization strategies for higher order tensors: Implications for compression and recovery of multi-linear data, preprint, arXiv:1307.0805v3, (2013). Google Scholar

show all references

References:
[1]

J. Cai, E. Candes and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20 (2010), 1956-1982. doi: 10.1137/080738970.  Google Scholar

[2]

E. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9 (2009), 717-772. doi: 10.1007/s10208-009-9045-5.  Google Scholar

[3]

C. Chen, B. He and X. Yuan, Matrix completion via an alternating direction method, IMA Journal of Numerical Analysis, 32 (2012), 227-245. doi: 10.1093/imanum/drq039.  Google Scholar

[4]

S. Gandy, B. Recht and I. Yamada, Tensor completion and low-n-rank tensor recovery via convex optimization, Inverse Problems, 27 (2011), 025010, 1-19. doi: 10.1088/0266-5611/27/2/025010.  Google Scholar

[5]

L. Grippo and M. Sciandrone, On the convergence of the block nonlinear Gauss-Seidel method under convex constraints, Oper. Res. Lett., 26 (2000), 127-136. doi: 10.1016/S0167-6377(99)00074-7.  Google Scholar

[6]

B. Jiang, S. Ma and S. Zhang, Tensor principal component analysis via convex optimization, Mathematical Programming, (2014), 1-35. doi: 10.1007/s10107-014-0774-0.  Google Scholar

[7]

H. A. L. Kiers, Towards a standardized notation and terminology in multiway analysis, Journal of Chemometrics, 14 (2000), 105-122. doi: 10.1002/1099-128X(200005/06)14:3<105::AID-CEM582>3.0.CO;2-I.  Google Scholar

[8]

M. Kilmer, K. Braman, N. Hao and R. Hoover, Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging, SIAM Journal on Matrix Analysis and Applications, 34 (2013), 148-172. doi: 10.1137/110837711.  Google Scholar

[9]

T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM review, 51 (2009), 455-500. doi: 10.1137/07070111X.  Google Scholar

[10]

T. G. Kolda, B. W. Bader and J. P. Kenny, Higher-order web link analysis using multilinear algebra, in Data Mining, Fifth IEEE International Conference on, IEEE, 2005. doi: 10.1109/ICDM.2005.77.  Google Scholar

[11]

N. Kreimer and M. D. Sacchi, A tensor higher-order singular value decomposition for prestack seismic data noise reduction and interpolation, Geophysics, 77 (2012), V113-V122. doi: 10.1190/geo2011-0399.1.  Google Scholar

[12]

D. Kressner, M. Steinlechner and B. Vandereycken, Low-rank tensor completion by riemannian optimization, BIT, 54 (2014), 447-468. doi: 10.1007/s10543-013-0455-z.  Google Scholar

[13]

M. Lai, Y. Xu and W. Yin, Improved iteratively reweighted least squares for unconstrained smoothed $l_q$ minimization, SIAM Journal on Numerical Analysis, 51 (2013), 927-957. doi: 10.1137/110840364.  Google Scholar

[14]

N. Li and B. Li, Tensor completion for on-board compression of hyperspectral images, in 2010 17th IEEE International Conference on Image Processing (ICIP), IEEE, 2010, 517-520. doi: 10.1109/ICIP.2010.5651225.  Google Scholar

[15]

Q. Ling, Y. Xu, W. Yin and Z. Wen, Decentralized low-rank matrix completion, in 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2012, 2925-2928. doi: 10.1109/ICASSP.2012.6288528.  Google Scholar

[16]

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, (2012), 208-220. doi: 10.1109/TPAMI.2012.39.  Google Scholar

[17]

S. Ma, D. Goldfarb and L. Chen, Fixed point and bregman iterative methods for matrix rank minimization, Mathematical Programming, 128 (2011), 321-353. doi: 10.1007/s10107-009-0306-5.  Google Scholar

[18]

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

[19]

K. A. Patwardhan, G. Sapiro and M. Bertalmío, Video inpainting under constrained camera motion, IEEE Transactions on Image Processing, 16 (2007), 545-553. doi: 10.1109/TIP.2006.888343.  Google Scholar

[20]

B. Recht, M. Fazel and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52 (2010), 471-501. doi: 10.1137/070697835.  Google Scholar

[21]

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

[22]

A. C. Sauve, A. O. Hero III, W. Leslie Rogers, S. J. Wilderman and N. H. Clinthorne, 3d image reconstruction for a compton spect camera model, Nuclear Science, IEEE Transactions on, 46 (1999), 2075-2084. doi: 10.1109/23.819285.  Google Scholar

[23]

J. Sun, H. 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. doi: 10.1145/1060745.1060803.  Google Scholar

[24]

K. C. Toh and S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pacific Journal of Optimization, 6 (2010), 615-640.  Google Scholar

[25]

P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109 (2001), 475-494. doi: 10.1023/A:1017501703105.  Google Scholar

[26]

L. R. Tucker, Some mathematical notes on three-mode factor analysis, Psychometrika, 31 (1966), 279-311. doi: 10.1007/BF02289464.  Google Scholar

[27]

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. doi: 10.1007/s12532-012-0044-1.  Google Scholar

[28]

Z. Xing, M. Zhou, A. Castrodad, G. Sapiro and L. Carin, Dictionary learning for noisy and incomplete hyperspectral images, SIAM Journal on Imaging Sciences, 5 (2012), 33-56. doi: 10.1137/110837486.  Google Scholar

[29]

Y. Xu and W. Yin, A block coordinate descent method for regularized multi-convex optimization with applications to nonnegative tensor factorization and completion, SIAM Journal on Imaging Sciences, 6 (2013), 1758-1789. doi: 10.1137/120887795.  Google Scholar

[30]

Y. Xu and W. Yin, A globally convergent algorithm for nonconvex optimization based on block coordinate update, arXiv:1410.1386, (2014). Google Scholar

[31]

Y. Xu, W. Yin, Z. Wen and Y. Zhang, An alternating direction algorithm for matrix completion with nonnegative factors, Journal of Frontiers of Mathematics in China, Special Issue on Computational Mathematics, 7 (2011), 365-384. doi: 10.1007/s11464-012-0194-5.  Google Scholar

[32]

Z. Zhang, G. Ely, S. Aeron, N. Hao and M. Kilmer, Novel factorization strategies for higher order tensors: Implications for compression and recovery of multi-linear data, preprint, arXiv:1307.0805v3, (2013). Google Scholar

[1]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076
[2]

Ke Wei, Jian-Feng Cai, Tony F. Chan, Shingyu Leung. Guarantees of riemannian optimization for low rank matrix completion. Inverse Problems & Imaging, 2020, 14 (2) : 233-265. doi: 10.3934/ipi.2020011
[3]

Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems & Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030
[4]

Wei Wan, Weihong Guo, Jun Liu, Haiyang Huang. Non-local blind hyperspectral image super-resolution via 4d sparse tensor factorization and low-rank. Inverse Problems & Imaging, 2020, 14 (2) : 339-361. doi: 10.3934/ipi.2020015
[5]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[6]

Zhouchen Lin. A review on low-rank models in data analysis. Big Data & Information Analytics, 2016, 1 (2&3) : 139-161. doi: 10.3934/bdia.2016001
[7]

Meng Ding, Ting-Zhu Huang, Xi-Le Zhao, Michael K. Ng, Tian-Hui Ma. Tensor train rank minimization with nonlocal self-similarity for tensor completion. Inverse Problems & Imaging, 2021, 15 (3) : 475-498. doi: 10.3934/ipi.2021001
[8]

Simon Foucart, Richard G. Lynch. Recovering low-rank matrices from binary measurements. Inverse Problems & Imaging, 2019, 13 (4) : 703-720. doi: 10.3934/ipi.2019032
[9]

Qilin Wang, Liu He, Shengjie Li. Higher-order weak radial epiderivatives and non-convex set-valued optimization problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 465-480. doi: 10.3934/jimo.2018051
[10]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103
[11]

Qun Liu, Lihua Fu, Meng Zhang, Wanjuan Zhang. Two-dimensional seismic data reconstruction using patch tensor completion. Inverse Problems & Imaging, 2020, 14 (6) : 985-1000. doi: 10.3934/ipi.2020052
[12]

Mingchao Zhao, You-Wei Wen, Michael Ng, Hongwei Li. A nonlocal low rank model for poisson noise removal. Inverse Problems & Imaging, 2021, 15 (3) : 519-537. doi: 10.3934/ipi.2021003
[13]

Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357
[14]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134
[15]

H. D. Scolnik, N. E. Echebest, M. T. Guardarucci. Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 175-191. doi: 10.3934/jimo.2009.5.175
[16]

Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305
[17]

Yongge Tian. A survey on rank and inertia optimization problems of the matrix-valued function $A + BXB^{*}$. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 289-326. doi: 10.3934/naco.2015.5.289
[18]

Nurullah Yilmaz, Ahmet Sahiner. On a new smoothing technique for non-smooth, non-convex optimization. Numerical Algebra, Control & Optimization, 2020, 10 (3) : 317-330. doi: 10.3934/naco.2020004
[19]

Yi Yang, Jianwei Ma, Stanley Osher. Seismic data reconstruction via matrix completion. Inverse Problems & Imaging, 2013, 7 (4) : 1379-1392. doi: 10.3934/ipi.2013.7.1379
[20]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

2020 Impact Factor: 1.639

Tools

Metrics

  • PDF downloads (244)
  • HTML views (0)
  • Cited by (84)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences