Low rank Tucker-type tensor approximation to classical potentials

• Autorzy: B. Khoromskij , V. Khoromskaia
• Języki publikacji: EN

Abstrakty

EN

This paper investigates best rank-(r 1,..., r d) Tucker tensor approximation of higher-order tensors arising from the discretization of linear operators and functions in ℝd. Super-convergence of the best rank-(r 1,..., r d) Tucker-type decomposition with respect to the relative Frobenius norm is proven. Dimensionality reduction by the two-level Tucker-to-canonical approximation is discussed. Tensor-product representation of basic multi-linear algebra operations is considered, including inner, outer and Hadamard products. Furthermore, we focus on fast convolution of higher-order tensors represented by the Tucker/canonical models. Optimized versions of the orthogonal alternating least-squares (ALS) algorithm is presented taking into account the different formats of input data. We propose and test numerically the mixed CT-model, which is based on the additive splitting of a tensor as a sum of canonical and Tucker-type representations. It allows to stabilize the ALS iteration in the case of “ill-conditioned” tensors. The best rank-(r 1,..., r d) Tucker decomposition is applied to 3D tensors generated by classical potentials, for example $$\tfrac{1}{{\left| {x - y} \right|}}, e^{ - \alpha \left| {x - y} \right|} , \tfrac{{e^{ - \left| {x - y} \right|} }}{{\left| {x - y} \right|}}$$ and $$\tfrac{{erf(|x|)}}{{|x|}}$$ with x, y ∈ ℝd. Numerical results for tri-linear decompositions illustrate exponential convergence in the Tucker rank, and robustness of the orthogonal ALS iteration.

Słowa kluczowe

EN

Kronecker products; Tucker decomposition; multi-dimensional integral operators; multivariate functions; classical potentials

Kategorie tematyczne

• 65F10: Iterative methods for linear systems
• 65N35: Spectral, collocation and related methods
• 65F50: Sparse matrices
• 65F30: Other matrix algorithms

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2007
• Tom: 5
• Numer: 3
• Strony: 523-550

Daty

wydano

2007-09-01

online

2007-09-01

Twórcy

autor

B. Khoromskij

• Max-Planck-Institute for Mathematics in the Sciences

autor

V. Khoromskaia

• Max-Planck-Institute for Mathematics in the Sciences

Bibliografia

• [1] B.W. Bader and T.G. Kolda: MATLAB tensor classes for fast algorithm prototyping. SANDIA Report, SAND2004-5187, Sandia National Laboratories, 2004.
• [2] G. Beylkin and M. M. Mohlenkamp: “Numerical operator calculus in higher dimensions”, PNAS, Vol. 99, (2002), pp. 10246–10251. http://dx.doi.org/10.1073/pnas.112329799
• [3] J.D. Carrol and J. Chang: “Analysis of individual differences in multidimensional scaling via an N-way generalization of ‘Eckart-Young’ decomposition”, Psychometrika, Vol. 35, (1970), pp. 283–319. http://dx.doi.org/10.1007/BF02310791
• [4] L. De Lathauwer, B. De Moorand J. Vandewalle: “A multilinear singular value decomposition”, SIAM J. Matrix Anal. Appl., Vol. 21, (2000), pp. 1253–1278. http://dx.doi.org/10.1137/S0895479896305696
• [5] L. De Lathauwer, B. De Moor and J. Vandewalle: “On the best rank-1 and rank-(R 1, ..., R N) approximation of higher-order tensors”, SIAM J. Matrix Anal. Appl., Vol. 21, (2000) pp. 1324–1342. http://dx.doi.org/10.1137/S0895479898346995
• [6] L. De Lathauwer, B. De Moor and J. Vandewalle: “Computation of the canonical decomposition by means of a simultaneous generalised Schur decomposition”, SIAM J. Matrix Anal. Appl., Vol. 26, (2004) pp. 295–327. http://dx.doi.org/10.1137/S089547980139786X
• [7] L. De Lathauwer: “A link between the canonical decomposition in multilinear algebra and simultaneous matrix diagonalisation”, SIAM J. Matrix Anal. Appl., Vol. 28, (2006), pp. 642–666. http://dx.doi.org/10.1137/040608830
• [8] L. De Lathauwer: Decomposition of a higher-order tensor in block terms. Part II: Definitions and uniqueness. Tech. Report no. 07-81, ESAT/SCD/SISTA, K.U. Leuven, Belgium, 2007.
• [9] H.-J. Flad, W. Hackbusch, B.N. Khoromskij and R. Schneider: Concept of datasparse tensor-product approximation in many-particle models, Leipzig-Kiel, 2006 (in preparation).
• [10] I.P. Gavrilyuk, W. Hackbusch and B.N. Khoromskij: “Tensor-product approximation to elliptic and parabolic solution operators in higher dimensions”, Computing, Vol. 74, (2005), pp. 131–157. http://dx.doi.org/10.1007/s00607-004-0086-y
• [11] G.H. Golub and C.F. Van Loan: Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 1996.
• [12] W. Hackbusch: “Fast and exact projected convolution for non-equidistant grids”, Preprint: 102, MPI MIS, Leipzig 2006.
• [13] W. Hackbusch and B.N. Khoromskij: “Low-rank Kronecker product approximation to multi-dimensional nonlocal operators. Part I. Separable approximation of multivariate functions”, Computing, Vol. 76, (2006), pp. 177–202. http://dx.doi.org/10.1007/s00607-005-0144-0
• [14] W. Hackbusch and B.N. Khoromskij: “Low-rank Kronecker product approximation to multi-dimensional nonlocal operators. Part II. HKT representations of certain operators”, Computing, Vol. 76, (2006), pp. 203–225. http://dx.doi.org/10.1007/s00607-005-0145-z
• [15] W. Hackbusch, B.N. Khoromskij and E.E. Tyrtyshnikov: “Hierarchical Kronecker tensor-product approximations”, J. Numer. Math., Vol. 13, (2005), pp. 119–156. http://dx.doi.org/10.1515/1569395054012767
• [16] W. Hackbusch, B.N. Khoromskij and E.E. Tyrtyshnikov: “Approximate Iterations for Structured Matrices”, Preprint: 112, MPI MIS, Leipzig 2005 (Numer. Math., submitted).
• [17] R. Harshman: “Foundation of the PARAFAC procedure: Model and conditions for an “explanatory” multi-mode factor analysis”, UCLA Working Papers in Phonetics, Vol. 16, (1970), pp. 1–84.
• [18] B.N. Khoromskij: “Structured data-sparse approximation to high order tensors arising from the deterministic Boltzmann equation”, Math. Comp., Vol. 76, (2007), pp. 1275–1290.
• [19] B.N. Khoromskij: “An introduction to structured tensor-product representation of discrete nonlocal operators”, Lecture Notes MPI MIS Leipzig, Vol. 27, (2005).
• [20] B.N. Khoromskij: “Structured rank-(r 1, ... r d ) decomposition of function-related tensors in ℝd ”, Comp. Meth. in Applied Math., Vol. 6, (2006), pp. 194–220.
• [21] T. Kolda: “Orthogonal tensor decompositions” SIAM J. Matrix Anal. Appl., Vol. 23, (2001), pp. 243–255. http://dx.doi.org/10.1137/S0895479800368354
• [22] J.B. Kruskal: “Three-way arrays: rank and uniqueness of trilinear decompositions, with applications to arithmetic complexity and statistics”, Linear Algebra Appl., Vol. 18, (1977), pp. 95–138. http://dx.doi.org/10.1016/0024-3795(77)90069-6
• [23] P.M. Kroonenberg and J. De Leeuw: “Principal component analysis of three-mode data by means of alternating least squares algorithms”, Psychometrika, Vol. 45, (1980), pp. 69–97. http://dx.doi.org/10.1007/BF02293599
• [24] Ch. Lubich: “On variational approximations in quantum molecular dynamics”, Math. Comp. Vol. 74, (2005), pp. 765–779. http://dx.doi.org/10.1090/S0025-5718-04-01685-0
• [25] I.V. Oseledets, D.V. Savostianov, and E.E. Tyrtyshnikov: “Tucker dimensionality reduction of three-dimensional arrays in linear time”, SIAM J. Matrix Anal. Appl., 2007 (to appear).
• [26] N.D. Sidiropoulos and R. Bro: “On the uniqueness of multilinear decomposition of N-way arrays”, Journal of Chemometrics, Vol. 14, (2000), 229–239. http://dx.doi.org/10.1002/1099-128X(200005/06)14:3<229::AID-CEM587>3.0.CO;2-N
• [27] A. Stegeman and N.D. Sidiropoulos: “On Kruskal’s uniqueness condition for the Candecomp/Parafac decomposition”, Lin. Alg. Appl., Vol. 420, (2007), pp. 540–552. http://dx.doi.org/10.1016/j.laa.2006.08.010
• [28] A. Smilde, R. Broa and P. Geladi: Multi-way Analysis, Wiley, 2004.
• [29] J. Strang and G.J. Fix: An Analysis of the Finite Element Method, Prentice-Hall, inc. N. J., 1973.
• [30] V.N. Temlyakov: “Greedy Algorithms and M-Term Approximation with Regard to Redundant Dictionaries”, J. of Approx. Theory, Vol. 98, (1999), pp. 117–145. http://dx.doi.org/10.1006/jath.1998.3265
• [31] L.R. Tucker: “Some mathematical notes on three-mode factor analysis”, Psychometrika, Vol. 31, (1966), pp. 279–311. http://dx.doi.org/10.1007/BF02289464
• [32] E.E. Tyrtyshnikov: “Tensor approximations of matrices generated by asymptotically smooth functions”, Sb. Math+., Vol. 194, (2003), pp. 941–954 (translated from Mat. Sb., Vol. 194, (2003), pp. 146–160). http://dx.doi.org/10.1070/SM2003v194n06ABEH000747
• [33] T. Zang and G. Golub: “Rank-0ne approximation to high order tensors”, SIAM J. Matrix Anal. Appl., Vol. 23, (2001), pp. 534–550. http://dx.doi.org/10.1137/S0895479899352045

Identyfikatory

DOI

10.2478/s11533-007-0018-0