Top

Journal of Scientific Computing

Published in:

02-08-2017

A Mixture of Nuclear Norm and Matrix Factorization for Tensor Completion

Authors: Shangqi Gao, Qibin Fan

Published in: Journal of Scientific Computing | Issue 1/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we propose a mixture model for tensor completion by combining the nuclear norm with the low-rank matrix factorization. To solve this model, we develop two algorithms: non-smooth low-rank tensor completion (NS-LRTC), smooth low-rank tensor completion (S-LRTC). When the sampling rate (SR) is high, our experiments on real-world data show that the NS-LRTC algorithm outperforms other tested methods in running time and recovery quality. In addition, whatever the SR is, the proposed S-LRTC algorithm delivers state-of-art recovery performance compared with other tested approaches. Although the objective function in our model is non-convex and non-differentiable, we prove that every cluster point of the sequence generated by NS-LRTC or S-LRTC is a stationary point.

previous article Computing the Level Set Convex Hull

next article Finite Volume HWENO Schemes for Nonconvex Conservation Laws

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

http://www1.cs.columbia.edu/CAVE/databases/multispectral/.

http://www.osirix-viewer.com/resources/dicom-image-library/.

http://trace.eas.asu.edu/yuv/.

De Lathauwer, L., Castaing, J., Cardoso, J.F.: Fourth-order cumulant based blind identification of underdetermined mixtures. IEEE Trans. Signal Process. 55(6), 2965–2973 (2007)MathSciNetCrossRef

De Lathauwer, L., De Moor, B., Vandewalle, J.: A multilinear singular value decomposition. SIAM J. Matrix Anal. Appl. 21(1), 1253–1278 (2000)MathSciNetCrossRefMATH

Vlasic, D., Brand, M., Pfrister, H., Popovic, J.: Face transfer with multilinear models. ACM Trans. Graph. 24(3), 426–433 (2005)CrossRef

Beylkin, G., Mohlencamp, M.J.: Numerical operator calculus in higher dimensions. Proc. Natl. Acad. Sci. 99(16), 10246–10251 (2002)MathSciNetCrossRefMATH

Acar, E., Bingol, C.A., Bingol, H., Bro, R., Yener, B.: Multiway analysis of epilepsy tensors. Bioinformatics 23(13), i10–i18 (2007)CrossRef

Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C.: Image Inpainting. In: Proceedings of ACM Siggraph, pp. 414–424. New Orleans, USA (2000)

Komodakis, N., Tziritas, G.: Image completion using global optimization. In: Proceedings of IEEE conference on computer vision and pattern recognition, pp. 417–424 (2006)

Korah, T., Rasmussen, C.: Spatio-temporal impainting for recovering texture maps of occluded building facades. IEEE Trans. Image Process. 16(7), 2262–2271 (2007)MathSciNetCrossRef

Patwardhan, K.A., Spiro, G., Bertalmio, M.: Video inpainting under constrained camera motion. IEEE Trans. Image Process. 16(2), 545–553 (2007)MathSciNetCrossRef

10.

Varghees, V.N., Manikandan, M.S., Gini, R.: Adaptive MRI image denoising using total-variation and local noise estimation. In: Processing of the 2012 International Conference on Advances in Engineering, Science and Management(ICAESM), pp. 506–511 (2012)

11.

Li, N., Li, B.: Tensor completion for on-board compression of hyperspectral images. In: 17th IEEE international conference on image processing (ICIP), IEEE, pp. 517–520 (2010)

12.

Xing, Z.G., Zhou, M., Castrodad, A., Saprio, G., Carin, L.: Dictionary learning for noisy and incomplete hyperspectral images. SIAM J. Imaging Sci. 5(1), 33–56 (2012)MathSciNetCrossRefMATH

13.

Liu, Y., Jiao, L., Shang, F.: An efficient matrix factorization method for tensor completion. IEEE Signal Process. Lett. 20(4), 307–310 (2013)CrossRef

14.

Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. Proc. SIAM Rev. 52(3), 471–501 (2010)MathSciNetCrossRefMATH

15.

Ma, S., Goldfarb, D., Chen, L.: Fixed point and bregman iterative methods for matrix rank minimization. Math. Progr. 128(1–2), 321–353 (2011)MathSciNetCrossRefMATH

16.

Toh, K.C., Tun, S.: An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pac. J. Optim. 6(3), 615–640 (2010)MathSciNetMATH

17.

Wen, Z., Yin, W., Zhang, Y.: Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Progr. Comput. 4(4), 1–29 (2012)MathSciNetMATH

18.

Chen, C., He, B., Yuan, X.: Matrix completion via an alternating direction method. IMA J. Numer. Anal. 32(1), 227–245 (2012)MathSciNetCrossRefMATH

19.

Xu, Y., Yin, W., Wen, Z., Zhang, Y.: An alternating direction algorithm for matrix completion with nonnegative factors. J. Front. Math. China Spec. Issue Comput. Math. 7(2), 365–384 (2011)MathSciNetCrossRefMATH

20.

Tucker, L.R.: Implications of factor analysis of three-way matrices for measurement of change. In: Harris, C.W. (ed.) Problems in Measuring Change, pp. 122–137. University of Wisconsin Press, Madison (1963)

21.

Tucker, L.R.: Some mathematical notes on three-mode factor analysis. Psychometrika 31(3), 279–311 (1966)MathSciNetCrossRef

22.

Hackbusch, W., Kühn, S.: A new scheme for the tensor representation. J. Fourier Anal. Appl. 15(5), 706–722 (2009)MathSciNetCrossRefMATH

23.

Grasedyck, L.: Hierarchical singular value decomposition of tensors. SIAM J. Matrix Anal. Appl. 31(4), 2029–2054 (2010)MathSciNetCrossRefMATH

24.

Oseledets, I.V., Tyrtyshnikov, E.E.: Breaking the curse of dimensionality, or how to use SVD in many dimensions. SIAM J. Sci. Comput. 31(5), 3744–3759 (2009)MathSciNetCrossRefMATH

25.

Oseledets, I.V.: Tensor-train decomposition. SIAM J. Sci. Comput. 33(5), 2295–2317 (2011)MathSciNetCrossRefMATH

26.

Kruskal, J. B.: Rank decomposition and uniqueness for 3-way and N-way arrays. In: Multiway Data Analysis, pp. 7–18 (1988)

27.

Liu, J., Musialski, P., Wonka, P., Yw, J.P.: Tensor completion for estimating missing values in visual data. IEEE Trans. Pattern Anal. Mach. Intell. 35(1), 1126–1153 (2013)

28.

Kolda, G., Bader, W.: Tensor decomposition and application. SIAM Rev. 51(3), 455–500 (2009)MathSciNetCrossRefMATH

29.

Xu, Y.Y., Hao, R.R., Yin, W.T., Su, Z.X.: Parallel matrix factorization for low-rank tensor completion. Inverse Probl. Imaging 9(2), 601–624 (2015)MathSciNetCrossRefMATH

30.

Tseng, P.: Convergence of a block coordinate descent method for non-differential minimization. J. Optim. Theory Appl. 109(3), 475–494 (2001)MathSciNetCrossRefMATH

31.

Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9(6), 717–772 (2009)MathSciNetCrossRefMATH

32.

Wen, Z.W., Yin, W.T., Zhang, Y.: Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Program. Comput. 4(4), 333–361 (2012)MathSciNetCrossRefMATH

33.

Cai, J.F., Candès, F.J., Shen, Z.: A singular value thresholding decomposition, UCLA CAM Report (2010)

34.

Ge, R., Lee, J.D., Ma, T.: Matrix completion has no spurious local minimum, arXiv:1605.07272v3 [cs.LG] (2017)

35.

Nesterov, Y.: Smooth minimization of non-smooth function. Math. Progr. 20(6), 127–152 (2005)MathSciNetCrossRefMATH

36.

Yunus, A., Coskun, K., Akbar, A., Ismail, K., Fatemeh, K.: Uniform-geometric distribution. J. Stat. Comput. Simul. 86(9), 1754–1770 (2016)MathSciNetCrossRef

37.

Sun, W., Yuan, Y.: Optimization Theory and Methods: Nonlinear Programming. Springer, New York (2006)MATH

38.

Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equation in Several Variables. Academic Press, New York (1970)MATH

39.

Dimitri, P.: Bertsekas, Nonlinear Programming, 208–211, 2nd edn. Athena Scientific, Nashua (1999)

Title: A Mixture of Nuclear Norm and Matrix Factorization for Tensor Completion
Authors: Shangqi Gao
Qibin Fan
Publication date: 02-08-2017
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 1/2018
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-017-0521-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2018

Simultaneous Approximation Terms for Multi-dimensional Summation-by-Parts Operators

Compact Direct Flux Reconstruction for Conservation Laws

Integer Matrix Approximation and Data Mining

Using Regularization to Improve Numerical Partial Differential Equation Solvers

Energy Stability Analysis of Some Fully Discrete Numerical Schemes for Incompressible Navier–Stokes Equations on Staggered Grids

A Projection Method for the Conservative Discretizations of Parabolic Partial Differential Equations

Premium Partner