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]

SIAM J. Optim., 20 (2010), 1956-1982. doi: 10.1137/080738970.  Google Scholar

[2]

Foundations of Computational Mathematics, 9 (2009), 717-772. doi: 10.1007/s10208-009-9045-5.  Google Scholar

[3]

IMA Journal of Numerical Analysis, 32 (2012), 227-245. doi: 10.1093/imanum/drq039.  Google Scholar

[4]

Inverse Problems, 27 (2011), 025010, 1-19. doi: 10.1088/0266-5611/27/2/025010.  Google Scholar

[5]

Oper. Res. Lett., 26 (2000), 127-136. doi: 10.1016/S0167-6377(99)00074-7.  Google Scholar

[6]

Mathematical Programming, (2014), 1-35. doi: 10.1007/s10107-014-0774-0.  Google Scholar

[7]

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]

SIAM Journal on Matrix Analysis and Applications, 34 (2013), 148-172. doi: 10.1137/110837711.  Google Scholar

[9]

SIAM review, 51 (2009), 455-500. doi: 10.1137/07070111X.  Google Scholar

[10]

in Data Mining, Fifth IEEE International Conference on, IEEE, 2005. doi: 10.1109/ICDM.2005.77.  Google Scholar

[11]

Geophysics, 77 (2012), V113-V122. doi: 10.1190/geo2011-0399.1.  Google Scholar

[12]

BIT, 54 (2014), 447-468. doi: 10.1007/s10543-013-0455-z.  Google Scholar

[13]

SIAM Journal on Numerical Analysis, 51 (2013), 927-957. doi: 10.1137/110840364.  Google Scholar

[14]

in 2010 17th IEEE International Conference on Image Processing (ICIP), IEEE, 2010, 517-520. doi: 10.1109/ICIP.2010.5651225.  Google Scholar

[15]

in 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2012, 2925-2928. doi: 10.1109/ICASSP.2012.6288528.  Google Scholar

[16]

IEEE Transactions on Pattern Analysis and Machine Intelligence, (2012), 208-220. doi: 10.1109/TPAMI.2012.39.  Google Scholar

[17]

Mathematical Programming, 128 (2011), 321-353. doi: 10.1007/s10107-009-0306-5.  Google Scholar

[18]

preprint, arXiv:1307.5870, (2013). Google Scholar

[19]

IEEE Transactions on Image Processing, 16 (2007), 545-553. doi: 10.1109/TIP.2006.888343.  Google Scholar

[20]

SIAM Review, 52 (2010), 471-501. doi: 10.1137/070697835.  Google Scholar

[21]

preprint, arXiv:1307.4653, (2013). Google Scholar

[22]

Nuclear Science, IEEE Transactions on, 46 (1999), 2075-2084. doi: 10.1109/23.819285.  Google Scholar

[23]

in Proceedings of the 14th international conference on World Wide Web, ACM, 2005, 382-390. doi: 10.1145/1060745.1060803.  Google Scholar

[24]

Pacific Journal of Optimization, 6 (2010), 615-640.  Google Scholar

[25]

Journal of Optimization Theory and Applications, 109 (2001), 475-494. doi: 10.1023/A:1017501703105.  Google Scholar

[26]

Psychometrika, 31 (1966), 279-311. doi: 10.1007/BF02289464.  Google Scholar

[27]

Mathematical Programming Computation, 4 (2012), 333-361. doi: 10.1007/s12532-012-0044-1.  Google Scholar

[28]

SIAM Journal on Imaging Sciences, 5 (2012), 33-56. doi: 10.1137/110837486.  Google Scholar

[29]

SIAM Journal on Imaging Sciences, 6 (2013), 1758-1789. doi: 10.1137/120887795.  Google Scholar

[30]

arXiv:1410.1386, (2014). Google Scholar

[31]

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]

preprint, arXiv:1307.0805v3, (2013). Google Scholar

show all references

References:
[1]

SIAM J. Optim., 20 (2010), 1956-1982. doi: 10.1137/080738970.  Google Scholar

[2]

Foundations of Computational Mathematics, 9 (2009), 717-772. doi: 10.1007/s10208-009-9045-5.  Google Scholar

[3]

IMA Journal of Numerical Analysis, 32 (2012), 227-245. doi: 10.1093/imanum/drq039.  Google Scholar

[4]

Inverse Problems, 27 (2011), 025010, 1-19. doi: 10.1088/0266-5611/27/2/025010.  Google Scholar

[5]

Oper. Res. Lett., 26 (2000), 127-136. doi: 10.1016/S0167-6377(99)00074-7.  Google Scholar

[6]

Mathematical Programming, (2014), 1-35. doi: 10.1007/s10107-014-0774-0.  Google Scholar

[7]

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]

SIAM Journal on Matrix Analysis and Applications, 34 (2013), 148-172. doi: 10.1137/110837711.  Google Scholar

[9]

SIAM review, 51 (2009), 455-500. doi: 10.1137/07070111X.  Google Scholar

[10]

in Data Mining, Fifth IEEE International Conference on, IEEE, 2005. doi: 10.1109/ICDM.2005.77.  Google Scholar

[11]

Geophysics, 77 (2012), V113-V122. doi: 10.1190/geo2011-0399.1.  Google Scholar

[12]

BIT, 54 (2014), 447-468. doi: 10.1007/s10543-013-0455-z.  Google Scholar

[13]

SIAM Journal on Numerical Analysis, 51 (2013), 927-957. doi: 10.1137/110840364.  Google Scholar

[14]

in 2010 17th IEEE International Conference on Image Processing (ICIP), IEEE, 2010, 517-520. doi: 10.1109/ICIP.2010.5651225.  Google Scholar

[15]

in 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2012, 2925-2928. doi: 10.1109/ICASSP.2012.6288528.  Google Scholar

[16]

IEEE Transactions on Pattern Analysis and Machine Intelligence, (2012), 208-220. doi: 10.1109/TPAMI.2012.39.  Google Scholar

[17]

Mathematical Programming, 128 (2011), 321-353. doi: 10.1007/s10107-009-0306-5.  Google Scholar

[18]

preprint, arXiv:1307.5870, (2013). Google Scholar

[19]

IEEE Transactions on Image Processing, 16 (2007), 545-553. doi: 10.1109/TIP.2006.888343.  Google Scholar

[20]

SIAM Review, 52 (2010), 471-501. doi: 10.1137/070697835.  Google Scholar

[21]

preprint, arXiv:1307.4653, (2013). Google Scholar

[22]

Nuclear Science, IEEE Transactions on, 46 (1999), 2075-2084. doi: 10.1109/23.819285.  Google Scholar

[23]

in Proceedings of the 14th international conference on World Wide Web, ACM, 2005, 382-390. doi: 10.1145/1060745.1060803.  Google Scholar

[24]

Pacific Journal of Optimization, 6 (2010), 615-640.  Google Scholar

[25]

Journal of Optimization Theory and Applications, 109 (2001), 475-494. doi: 10.1023/A:1017501703105.  Google Scholar

[26]

Psychometrika, 31 (1966), 279-311. doi: 10.1007/BF02289464.  Google Scholar

[27]

Mathematical Programming Computation, 4 (2012), 333-361. doi: 10.1007/s12532-012-0044-1.  Google Scholar

[28]

SIAM Journal on Imaging Sciences, 5 (2012), 33-56. doi: 10.1137/110837486.  Google Scholar

[29]

SIAM Journal on Imaging Sciences, 6 (2013), 1758-1789. doi: 10.1137/120887795.  Google Scholar

[30]

arXiv:1410.1386, (2014). Google Scholar

[31]

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]

preprint, arXiv:1307.0805v3, (2013). Google Scholar

[1]

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
[2]

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
[3]

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
[4]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83
[5]

Pavel I. Naumkin, Isahi Sánchez-Suárez. Asymptotics for the higher-order derivative nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021028
[6]

Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365
[7]

Muhammad Aslam Noor, Khalida Inayat Noor. Properties of higher order preinvex functions. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 431-441. doi: 10.3934/naco.2020035
[8]

Mario Pulvirenti, Sergio Simonella. On the cardinality of collisional clusters for hard spheres at low density. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3903-3914. doi: 10.3934/dcds.2021021
[9]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[10]

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597
[11]

Abdeslem Hafid Bentbib, Smahane El-Halouy, El Mostafa Sadek. Extended Krylov subspace methods for solving Sylvester and Stein tensor equations. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021026
[12]

Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080
[13]

F.J. Herranz, J. de Lucas, C. Sardón. Jacobi--Lie systems: Fundamentals and low-dimensional classification. Conference Publications, 2015, 2015 (special) : 605-614. doi: 10.3934/proc.2015.0605
[14]

Emily McMillon, Allison Beemer, Christine A. Kelley. Extremal absorbing sets in low-density parity-check codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021003
[15]

Jan Rychtář, Dewey T. Taylor. Moran process and Wright-Fisher process favor low variability. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3491-3504. doi: 10.3934/dcdsb.2020242
[16]

Mao Okada. Local rigidity of certain actions of solvable groups on the boundaries of rank-one symmetric spaces. Journal of Modern Dynamics, 2021, 17: 111-143. doi: 10.3934/jmd.2021004
[17]

Mirela Kohr, Sergey E. Mikhailov, Wolfgang L. Wendland. Dirichlet and transmission problems for anisotropic stokes and Navier-Stokes systems with L∞ tensor coefficient under relaxed ellipticity condition. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021042
[18]

Fei Liu, Xiaokai Liu, Fang Wang. On the mixing and Bernoulli properties for geodesic flows on rank 1 manifolds without focal points. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021057
[19]

Tobias Breiten, Sergey Dolgov, Martin Stoll. Solving differential Riccati equations: A nonlinear space-time method using tensor trains. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 407-429. doi: 10.3934/naco.2020034
[20]

Maoding Zhen, Binlin Zhang, Vicenţiu D. Rădulescu. Normalized solutions for nonlinear coupled fractional systems: Low and high perturbations in the attractive case. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2653-2676. doi: 10.3934/dcds.2020379

2019 Impact Factor: 1.373

Tools

Metrics

  • PDF downloads (192)
  • HTML views (0)
  • Cited by (82)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences