- Previous Article
- IPI Home
- This Issue
-
Next Article
Determining an obstacle by far-field data measured at a few spots
Parallel matrix factorization for low-rank tensor completion
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 |
  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.
References:
[1] |
SIAM J. Optim., 20 (2010), 1956-1982.
doi: 10.1137/080738970. |
[2] |
Foundations of Computational Mathematics, 9 (2009), 717-772.
doi: 10.1007/s10208-009-9045-5. |
[3] |
IMA Journal of Numerical Analysis, 32 (2012), 227-245.
doi: 10.1093/imanum/drq039. |
[4] |
Inverse Problems, 27 (2011), 025010, 1-19.
doi: 10.1088/0266-5611/27/2/025010. |
[5] |
Oper. Res. Lett., 26 (2000), 127-136.
doi: 10.1016/S0167-6377(99)00074-7. |
[6] |
Mathematical Programming, (2014), 1-35.
doi: 10.1007/s10107-014-0774-0. |
[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. |
[8] |
SIAM Journal on Matrix Analysis and Applications, 34 (2013), 148-172.
doi: 10.1137/110837711. |
[9] |
SIAM review, 51 (2009), 455-500.
doi: 10.1137/07070111X. |
[10] |
in Data Mining, Fifth IEEE International Conference on, IEEE, 2005.
doi: 10.1109/ICDM.2005.77. |
[11] |
Geophysics, 77 (2012), V113-V122.
doi: 10.1190/geo2011-0399.1. |
[12] |
BIT, 54 (2014), 447-468.
doi: 10.1007/s10543-013-0455-z. |
[13] |
SIAM Journal on Numerical Analysis, 51 (2013), 927-957.
doi: 10.1137/110840364. |
[14] |
in 2010 17th IEEE International Conference on Image Processing (ICIP), IEEE, 2010, 517-520.
doi: 10.1109/ICIP.2010.5651225. |
[15] |
in 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2012, 2925-2928.
doi: 10.1109/ICASSP.2012.6288528. |
[16] |
IEEE Transactions on Pattern Analysis and Machine Intelligence, (2012), 208-220.
doi: 10.1109/TPAMI.2012.39. |
[17] |
Mathematical Programming, 128 (2011), 321-353.
doi: 10.1007/s10107-009-0306-5. |
[18] |
preprint, arXiv:1307.5870, (2013). Google Scholar |
[19] |
IEEE Transactions on Image Processing, 16 (2007), 545-553.
doi: 10.1109/TIP.2006.888343. |
[20] |
SIAM Review, 52 (2010), 471-501.
doi: 10.1137/070697835. |
[21] |
preprint, arXiv:1307.4653, (2013). Google Scholar |
[22] |
Nuclear Science, IEEE Transactions on, 46 (1999), 2075-2084.
doi: 10.1109/23.819285. |
[23] |
in Proceedings of the 14th international conference on World Wide Web, ACM, 2005, 382-390.
doi: 10.1145/1060745.1060803. |
[24] |
Pacific Journal of Optimization, 6 (2010), 615-640. |
[25] |
Journal of Optimization Theory and Applications, 109 (2001), 475-494.
doi: 10.1023/A:1017501703105. |
[26] |
Psychometrika, 31 (1966), 279-311.
doi: 10.1007/BF02289464. |
[27] |
Mathematical Programming Computation, 4 (2012), 333-361.
doi: 10.1007/s12532-012-0044-1. |
[28] |
SIAM Journal on Imaging Sciences, 5 (2012), 33-56.
doi: 10.1137/110837486. |
[29] |
SIAM Journal on Imaging Sciences, 6 (2013), 1758-1789.
doi: 10.1137/120887795. |
[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. |
[32] |
preprint, arXiv:1307.0805v3, (2013). Google Scholar |
show all references
References:
[1] |
SIAM J. Optim., 20 (2010), 1956-1982.
doi: 10.1137/080738970. |
[2] |
Foundations of Computational Mathematics, 9 (2009), 717-772.
doi: 10.1007/s10208-009-9045-5. |
[3] |
IMA Journal of Numerical Analysis, 32 (2012), 227-245.
doi: 10.1093/imanum/drq039. |
[4] |
Inverse Problems, 27 (2011), 025010, 1-19.
doi: 10.1088/0266-5611/27/2/025010. |
[5] |
Oper. Res. Lett., 26 (2000), 127-136.
doi: 10.1016/S0167-6377(99)00074-7. |
[6] |
Mathematical Programming, (2014), 1-35.
doi: 10.1007/s10107-014-0774-0. |
[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. |
[8] |
SIAM Journal on Matrix Analysis and Applications, 34 (2013), 148-172.
doi: 10.1137/110837711. |
[9] |
SIAM review, 51 (2009), 455-500.
doi: 10.1137/07070111X. |
[10] |
in Data Mining, Fifth IEEE International Conference on, IEEE, 2005.
doi: 10.1109/ICDM.2005.77. |
[11] |
Geophysics, 77 (2012), V113-V122.
doi: 10.1190/geo2011-0399.1. |
[12] |
BIT, 54 (2014), 447-468.
doi: 10.1007/s10543-013-0455-z. |
[13] |
SIAM Journal on Numerical Analysis, 51 (2013), 927-957.
doi: 10.1137/110840364. |
[14] |
in 2010 17th IEEE International Conference on Image Processing (ICIP), IEEE, 2010, 517-520.
doi: 10.1109/ICIP.2010.5651225. |
[15] |
in 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2012, 2925-2928.
doi: 10.1109/ICASSP.2012.6288528. |
[16] |
IEEE Transactions on Pattern Analysis and Machine Intelligence, (2012), 208-220.
doi: 10.1109/TPAMI.2012.39. |
[17] |
Mathematical Programming, 128 (2011), 321-353.
doi: 10.1007/s10107-009-0306-5. |
[18] |
preprint, arXiv:1307.5870, (2013). Google Scholar |
[19] |
IEEE Transactions on Image Processing, 16 (2007), 545-553.
doi: 10.1109/TIP.2006.888343. |
[20] |
SIAM Review, 52 (2010), 471-501.
doi: 10.1137/070697835. |
[21] |
preprint, arXiv:1307.4653, (2013). Google Scholar |
[22] |
Nuclear Science, IEEE Transactions on, 46 (1999), 2075-2084.
doi: 10.1109/23.819285. |
[23] |
in Proceedings of the 14th international conference on World Wide Web, ACM, 2005, 382-390.
doi: 10.1145/1060745.1060803. |
[24] |
Pacific Journal of Optimization, 6 (2010), 615-640. |
[25] |
Journal of Optimization Theory and Applications, 109 (2001), 475-494.
doi: 10.1023/A:1017501703105. |
[26] |
Psychometrika, 31 (1966), 279-311.
doi: 10.1007/BF02289464. |
[27] |
Mathematical Programming Computation, 4 (2012), 333-361.
doi: 10.1007/s12532-012-0044-1. |
[28] |
SIAM Journal on Imaging Sciences, 5 (2012), 33-56.
doi: 10.1137/110837486. |
[29] |
SIAM Journal on Imaging Sciences, 6 (2013), 1758-1789.
doi: 10.1137/120887795. |
[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. |
[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
Other articles
by authors
[Back to Top]