- 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] |
J. Cai, E. Candes and Z. Shen, A singular value thresholding algorithm for matrix completion,, SIAM J. Optim., 20 (2010), 1956.
doi: 10.1137/080738970. |
[2] |
E. Candès and B. Recht, Exact matrix completion via convex optimization,, Foundations of Computational Mathematics, 9 (2009), 717.
doi: 10.1007/s10208-009-9045-5. |
[3] |
C. Chen, B. He and X. Yuan, Matrix completion via an alternating direction method,, IMA Journal of Numerical Analysis, 32 (2012), 227.
doi: 10.1093/imanum/drq039. |
[4] |
S. Gandy, B. Recht and I. Yamada, Tensor completion and low-n-rank tensor recovery via convex optimization,, Inverse Problems, 27 (2011), 1.
doi: 10.1088/0266-5611/27/2/025010. |
[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.
doi: 10.1016/S0167-6377(99)00074-7. |
[6] |
B. Jiang, S. Ma and S. Zhang, Tensor principal component analysis via convex optimization,, Mathematical Programming, (2014), 1.
doi: 10.1007/s10107-014-0774-0. |
[7] |
H. A. L. Kiers, Towards a standardized notation and terminology in multiway analysis,, Journal of Chemometrics, 14 (2000), 105.
doi: 10.1002/1099-128X(200005/06)14:3<105::AID-CEM582>3.0.CO;2-I. |
[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.
doi: 10.1137/110837711. |
[9] |
T. G. Kolda and B. W. Bader, Tensor decompositions and applications,, SIAM review, 51 (2009), 455.
doi: 10.1137/07070111X. |
[10] |
T. G. Kolda, B. W. Bader and J. P. Kenny, Higher-order web link analysis using multilinear algebra,, in Data Mining, (2005).
doi: 10.1109/ICDM.2005.77. |
[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).
doi: 10.1190/geo2011-0399.1. |
[12] |
D. Kressner, M. Steinlechner and B. Vandereycken, Low-rank tensor completion by riemannian optimization,, BIT, 54 (2014), 447.
doi: 10.1007/s10543-013-0455-z. |
[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.
doi: 10.1137/110840364. |
[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), (2010), 517.
doi: 10.1109/ICIP.2010.5651225. |
[15] |
Q. Ling, Y. Xu, W. Yin and Z. Wen, Decentralized low-rank matrix completion,, in 2012 IEEE International Conference on Acoustics, (2012), 2925.
doi: 10.1109/ICASSP.2012.6288528. |
[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.
doi: 10.1109/TPAMI.2012.39. |
[17] |
S. Ma, D. Goldfarb and L. Chen, Fixed point and bregman iterative methods for matrix rank minimization,, Mathematical Programming, 128 (2011), 321.
doi: 10.1007/s10107-009-0306-5. |
[18] |
C. Mu, B. Huang, J. Wright and D. Goldfarb, Square deal: Lower bounds and improved relaxations for tensor recovery,, preprint, (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.
doi: 10.1109/TIP.2006.888343. |
[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.
doi: 10.1137/070697835. |
[21] |
B. Romera-Paredes and M. Pontil, A new convex relaxation for tensor completion,, preprint, (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, 46 (1999), 2075.
doi: 10.1109/23.819285. |
[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, (2005), 382.
doi: 10.1145/1060745.1060803. |
[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.
|
[25] |
P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization,, Journal of Optimization Theory and Applications, 109 (2001), 475.
doi: 10.1023/A:1017501703105. |
[26] |
L. R. Tucker, Some mathematical notes on three-mode factor analysis,, Psychometrika, 31 (1966), 279.
doi: 10.1007/BF02289464. |
[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.
doi: 10.1007/s12532-012-0044-1. |
[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.
doi: 10.1137/110837486. |
[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.
doi: 10.1137/120887795. |
[30] |
Y. Xu and W. Yin, A globally convergent algorithm for nonconvex optimization based on block coordinate update,, , (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, 7 (2011), 365.
doi: 10.1007/s11464-012-0194-5. |
[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, (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.
doi: 10.1137/080738970. |
[2] |
E. Candès and B. Recht, Exact matrix completion via convex optimization,, Foundations of Computational Mathematics, 9 (2009), 717.
doi: 10.1007/s10208-009-9045-5. |
[3] |
C. Chen, B. He and X. Yuan, Matrix completion via an alternating direction method,, IMA Journal of Numerical Analysis, 32 (2012), 227.
doi: 10.1093/imanum/drq039. |
[4] |
S. Gandy, B. Recht and I. Yamada, Tensor completion and low-n-rank tensor recovery via convex optimization,, Inverse Problems, 27 (2011), 1.
doi: 10.1088/0266-5611/27/2/025010. |
[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.
doi: 10.1016/S0167-6377(99)00074-7. |
[6] |
B. Jiang, S. Ma and S. Zhang, Tensor principal component analysis via convex optimization,, Mathematical Programming, (2014), 1.
doi: 10.1007/s10107-014-0774-0. |
[7] |
H. A. L. Kiers, Towards a standardized notation and terminology in multiway analysis,, Journal of Chemometrics, 14 (2000), 105.
doi: 10.1002/1099-128X(200005/06)14:3<105::AID-CEM582>3.0.CO;2-I. |
[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.
doi: 10.1137/110837711. |
[9] |
T. G. Kolda and B. W. Bader, Tensor decompositions and applications,, SIAM review, 51 (2009), 455.
doi: 10.1137/07070111X. |
[10] |
T. G. Kolda, B. W. Bader and J. P. Kenny, Higher-order web link analysis using multilinear algebra,, in Data Mining, (2005).
doi: 10.1109/ICDM.2005.77. |
[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).
doi: 10.1190/geo2011-0399.1. |
[12] |
D. Kressner, M. Steinlechner and B. Vandereycken, Low-rank tensor completion by riemannian optimization,, BIT, 54 (2014), 447.
doi: 10.1007/s10543-013-0455-z. |
[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.
doi: 10.1137/110840364. |
[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), (2010), 517.
doi: 10.1109/ICIP.2010.5651225. |
[15] |
Q. Ling, Y. Xu, W. Yin and Z. Wen, Decentralized low-rank matrix completion,, in 2012 IEEE International Conference on Acoustics, (2012), 2925.
doi: 10.1109/ICASSP.2012.6288528. |
[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.
doi: 10.1109/TPAMI.2012.39. |
[17] |
S. Ma, D. Goldfarb and L. Chen, Fixed point and bregman iterative methods for matrix rank minimization,, Mathematical Programming, 128 (2011), 321.
doi: 10.1007/s10107-009-0306-5. |
[18] |
C. Mu, B. Huang, J. Wright and D. Goldfarb, Square deal: Lower bounds and improved relaxations for tensor recovery,, preprint, (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.
doi: 10.1109/TIP.2006.888343. |
[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.
doi: 10.1137/070697835. |
[21] |
B. Romera-Paredes and M. Pontil, A new convex relaxation for tensor completion,, preprint, (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, 46 (1999), 2075.
doi: 10.1109/23.819285. |
[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, (2005), 382.
doi: 10.1145/1060745.1060803. |
[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.
|
[25] |
P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization,, Journal of Optimization Theory and Applications, 109 (2001), 475.
doi: 10.1023/A:1017501703105. |
[26] |
L. R. Tucker, Some mathematical notes on three-mode factor analysis,, Psychometrika, 31 (1966), 279.
doi: 10.1007/BF02289464. |
[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.
doi: 10.1007/s12532-012-0044-1. |
[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.
doi: 10.1137/110837486. |
[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.
doi: 10.1137/120887795. |
[30] |
Y. Xu and W. Yin, A globally convergent algorithm for nonconvex optimization based on block coordinate update,, , (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, 7 (2011), 365.
doi: 10.1007/s11464-012-0194-5. |
[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, (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] |
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, , () : -. 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, , () : -. doi: 10.3934/ipi.2021003 |
[4] |
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 |
[5] |
Tomasz Szostok. Inequalities of Hermite-Hadamard type for higher order convex functions, revisited. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020296 |
[6] |
Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247 |
[7] |
Peter Frolkovič, Karol Mikula, Jooyoung Hahn, Dirk Martin, Branislav Basara. Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 865-879. doi: 10.3934/dcdss.2020350 |
[8] |
Tomáš Oberhuber, Tomáš Dytrych, Kristina D. Launey, Daniel Langr, Jerry P. Draayer. Transformation of a Nucleon-Nucleon potential operator into its SU(3) tensor form using GPUs. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1111-1122. doi: 10.3934/dcdss.2020383 |
[9] |
Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135 |
[10] |
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 |
[11] |
Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020122 |
[12] |
Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067 |
[13] |
Petr Čoupek, María J. Garrido-Atienza. Bilinear equations in Hilbert space driven by paths of low regularity. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 121-154. doi: 10.3934/dcdsb.2020230 |
[14] |
Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115 |
[15] |
Russell Ricks. The unique measure of maximal entropy for a compact rank one locally CAT(0) space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 507-523. doi: 10.3934/dcds.2020266 |
[16] |
Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100 |
[17] |
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 - A, 2020 doi: 10.3934/dcds.2020379 |
[18] |
Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020347 |
[19] |
Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304 |
[20] |
Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 |
2019 Impact Factor: 1.373
Tools
Metrics
Other articles
by authors
[Back to Top]