nach oben

Calcolo

Erschienen in:

01.03.2022

A proximal point like method for solving tensor least-squares problems

verfasst von: Maolin Liang, Bing Zheng, Yutao Zheng

Erschienen in: Calcolo | Ausgabe 1/2022

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The goal of this paper is to solve the tensor least-squares (TLS) problem associated with multilinear system \(\mathcal {A}{} \mathbf{x} ^{m-1}=\mathbf{b}\), where \(\mathcal {A}\) is an mth-order n-dimensional tensor and \(\mathbf{b}\) is a vector in \(\mathbb {R}^{n}\), which has practical applications in numerical PDEs, data mining, tensor complementary problems, higher order statistics and so on. We transform the TLS problem into a multi-block optimization problem with consensus constraints, and propose an alternating linearized method with proximal regularization for it. Under some mild assumptions, it is shown that every limit point of the sequence generated by this method is a stationary point. Moreover, when the tensor \(\mathcal {A}\) can be constructed in the tensor-train format explicitly, the total number of operations with respect to the method mentioned above decreases from the order of \(\mathcal {O}(n^{m-1})\) to \(\mathcal {O}((m-1)^2nr^2)+\mathcal {O}(mnr^3)\), alleviating the curse-of-dimensionality. As an application, the inverse iteration methods, derived from the proposed methods, for solving the tensor eigenvalue problems are presented. Some numerical examples are provided to illustrate the feasibility of our algorithms.

Vorheriger Artikel Low-rank tensor approximation of singularly perturbed boundary value problems in one dimension

Nächster Artikel On the convergence rate of the Kačanov scheme for shear-thinning fluids

Generally, we can not conclude that the two suquences are convergent, although \(\Vert \widetilde{\mathbf{x }}^{(k)}-\widetilde{\mathbf{x }}^{(k+1)}\Vert ^2 \ge \Vert \widetilde{\mathbf{x }}^{(k)}-\overline{\overline{\mathbf{x }}}\,^{(k)}\Vert ^2\). A couterexample is \(x_i^{(k)}=1+\dfrac{1}{2}+\cdots +\dfrac{1}{k}\) in the sense that \(n=1\) and \(i=2,3,\ldots ,m\).

http://www.tensortoolbox.org.

Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51, 455–500 (2009)MathSciNetCrossRef

Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2013)MATH

Qi, L.-Q.: Eigenvalues of a real supersymmetric tensor. J. Symb. Comput. 40, 1302–1324 (2005)MathSciNetCrossRef

Lim, L.-H.: Singular values and eigenvalues of tensors: a variational approach. In: Proceedings of the 1st IEEE International Workshop on Computational Advances of Multi-sensor Adaptive Processing (CAMSAP), pp. 129–132 (2005)

Ding, W.-Y., Qi, L.-Q., Wei, Y.-M.: \(\cal{M}\)-tensors and nonsingular \(\cal{M}\)-tensors. Linear Algebra Appl. 439(10), 3264–3278 (2013)MathSciNetCrossRef

Zhang, L.-P., Qi, L.-Q., Zhou, G.-L.: \(\cal{M}\)-tensors and some applications. SIAM J. Matrix Anal. Appl. 35(2), 437–452 (2014)MathSciNetCrossRef

Li, X.-T., Ng, M.K.: Solving sparse non-negative tensor equations: algorithms and applications. Front. Math. China 10(3), 649–680 (2015)MathSciNetCrossRef

Ding, W.-Y., Wei, Y.-M.: Solving multi-linear systems with \(\cal{M}\)-tensors. J. Sci. Comput. 68(2), 689–715 (2016)MathSciNetCrossRef

Luo, Z.-Y., Qi, L.-Q., Xiu, N.-H.: The sparsest solutions to Z-tensor complementarity problems. Optim. Lett. 11, 471–482 (2017)MathSciNetCrossRef

10.

Elden, L., Ahmadi-Asl, S.: Solving bilinear tensor least squares problems. In: Report on the Sixth International Conference on Numerical Algebra and Scientific Computing (NASC 2016), Zhejiang University, Hangzhou, P.R. China (2016)

11.

Azimzadeh, P., Bayraktar, E.: High order Bellman equations and weakly chained diagonally dominant tensors. SIAM J. Matrix Anal. Appl. 40(1), 276–298 (2019)MathSciNetCrossRef

12.

Schnabel, R.B., Frank, P.D.: Tensor methods for nonlinear equations. SIAM J. Numer. Anal. 21(5), 815–843 (1984)MathSciNetCrossRef

13.

Bouaricha, A.: Tensor methods for large, sparse unconstrained optimization. SIAM J. Optim. 7(3), 732–756 (1997)MathSciNetCrossRef

14.

Han, L.-X.: A homotopy method for solving multilinear systems with \(\cal{M}\)-tensors. Appl. Math. Lett. 69, 49–54 (2017)MathSciNetCrossRef

15.

Li, D.-H., Xie, S.-L., Xu, H.-R.: Splitting methods for tensor equations. Numer. Linear Algebra. 24, e2102 (2017)MathSciNetCrossRef

16.

Xie, Z.-J., Jin, X.-Q., Wei, Y.-M.: Tensor methods for solving symmetric M-tensor systems. J. Sci. Comput. 74, 412–425 (2018)MathSciNetCrossRef

17.

Xie, Z.-J., Jin, X.-Q., Wei, Y.-M.: A fast algorithm for solving circulant tensor systems. Linear Multilinear Algebra 65(9), 1894–1904 (2017)MathSciNetCrossRef

18.

Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1–2), 459–494 (2014)MathSciNetCrossRef

19.

Kiers, H.: Towards a standardized notation and terminology in multiway analysis. J. Chemometr. 14, 105–122 (2000)CrossRef

20.

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

21.

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

22.

Silva, V.D., Lim, L.H.: Tensor rank and the ill-posedness of the best low-rank approximation problem. SIAM J. Matrix Anal. Appl. 30(3), 1084–1127 (2008)MathSciNetCrossRef

23.

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

24.

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

25.

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)MathSciNetCrossRef

26.

Grasedyck, L., Kressner, D., Tobler, C.: A literature survey of low-rank tensor approximation techniques. GAMM-Mitteilungen 36(1), 53–78 (2013)MathSciNetCrossRef

27.

Oseledets, I.V.: Compact matrix form of the d-dimensional tensor decomposition. Preprint 2009-01, INM RAS, Moscow (2009)

28.

Wang, X.-F., Navasca, C.: Low rank approximation of tensors via sparse optimization. Numer. Linear Algebra Appl. 25, e2136 (2018)MathSciNetCrossRef

29.

Karim, R.G., Guo, G.-M., Yan, D., Navasca, C.: Accurate tensor decomposition with simultaneous rank approximation for surveillance videos. In: The 54th IEEE Asilomar Conference on Signals, Systems and Computers, Pacific Grove (2020)

30.

Hong, D., Kolda, T..G., Duersch, J..A.: Generalized canonical polyadic tensor decomposition. SIAM Rev. 62(1), 133–163 (2020)MathSciNetCrossRef

31.

Ng, M.K., Qi, L.-Q., Zhou, G.-L.: Finding the largest eigenvalue of a nonnegative tensor. SIAM J. Matrix Anal. Appl. 31(3), 1090–1099 (2009)MathSciNetCrossRef

32.

Kolda, T.G., Mayo, J.R.: Shifted power method for computing tensor eigenpairs. SIAM J. Matrix Anal. Appl. 32(4), 1095–1124 (2011)MathSciNetCrossRef

33.

Cui, C.-F., Dai, Y.-H., Nie, J.-W.: All real eigenvalues of symmetric tensors. SIAM J. Matrix Anal. Appl. 35(4), 1582–1601 (2014)MathSciNetCrossRef

34.

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

35.

Grippo, L., Sciandrone, M.: On the convergence of the block nonlinear Gauss–Seidel method under convex constraints. Oper. Res. Lett. 26, 127–136 (2000)MathSciNetCrossRef

36.

Comon, P., Luciani, X., De Almeida, A.L.F.: Tensor decompositions, alternating least squares and other tales. J. Chemometrics 23, 393–405 (2009)CrossRef

37.

Aitken, A.C.: The evaluation of the latent roots and latent vectors of a matrix. Proc. R. Soc. Edinb. 57, 269–304 (1937)CrossRef

38.

Nesterov, Y.: A method of solving a convex programming problem with convergence rate O(\(1/k^2\)). Soviet. Math. Dokl. 27, 372–376 (1983)MATH

39.

Matsuno, Y.: Exact solutions for the nonlinear Klein–Gordon and Liouville equations in four-dimensional Euclidean space. J. Math. Phys. 28(10), 2317–2322 (1987)MathSciNetCrossRef

40.

Zwillinger, D.: Handbook of Differential Equations, 3rd edn. Academic Press Inc, Boston (1997)MATH

41.

Kofidis, E., Regalia, P.A.: On the best rank-1 approximation of higher-order supersymmetric tensors. SIAM J. Matrix Anal. Appl. 23, 863–884 (2002)MathSciNetCrossRef

Titel: A proximal point like method for solving tensor least-squares problems
verfasst von: Maolin Liang
Bing Zheng
Yutao Zheng
Publikationsdatum: 01.03.2022
Verlag: Springer International Publishing
Erschienen in: Calcolo / Ausgabe 1/2022
Print ISSN: 0008-0624
Elektronische ISSN: 1126-5434
DOI: https://doi.org/10.1007/s10092-021-00450-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1/2022

Correction to: Analysis of generalised alternating local discontinuous Galerkin method on layer-adapted mesh for singularly perturbed problems

Efficient and accurate computation for the -functions arising from exponential integrators

Rational interpolation operator with finite Lebesgue constant

PVTSI: A novel approach to computation of Hadamard finite parts of nonperiodic singular integrals

Low-rank tensor approximation of singularly perturbed boundary value problems in one dimension

Optimal three-stage implicit exponentially-fitted RKN methods for solving second-order ODEs