Low rank Tucker-type tensor approximation to classical potentials

B. Khoromskij; V. Khoromskaia

Open Mathematics, Tome 5 (2007), p. 523-550 / Harvested from The Polish Digital Mathematics Library

Résumé

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 $\frac{1}{|x - y|}, e^{- α |x - y|}, \frac{e^{- |x - y|}}{|x - y|}$ and $\frac{e r f (| 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.

Publié le : 2007-01-01

Zbl 1130.65060

EUDML-ID : urn:eudml:doc:269053

@article{bwmeta1.element.doi-10_2478_s11533-007-0018-0,
     author = {B. Khoromskij and V. Khoromskaia},
     title = {Low rank Tucker-type tensor approximation to classical potentials},
     journal = {Open Mathematics},
     volume = {5},
     year = {2007},
     pages = {523-550},
     zbl = {1130.65060},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-007-0018-0}
}

B. Khoromskij; V. Khoromskaia. Low rank Tucker-type tensor approximation to classical potentials. Open Mathematics, Tome 5 (2007) pp. 523-550. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-007-0018-0/

Bibliographie

[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 | Zbl 1008.65026

[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 | Zbl 0202.19101

[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 | Zbl 0962.15005

[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 | Zbl 0958.15026

[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 | Zbl 1080.65031

[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 | Zbl 1126.15007

[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 | Zbl 1071.65032

[11] G.H. Golub and C.F. Van Loan: Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 1996. | Zbl 0865.65009

[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 | Zbl 1087.65049

[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 | Zbl 1087.65050

[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 | Zbl 1081.65035

[16] W. Hackbusch, B.N. Khoromskij and E.E. Tyrtyshnikov: “Approximate Iterations for Structured Matrices”, Preprint: 112, MPI MIS, Leipzig 2005 (Numer. Math., submitted). | Zbl 1144.65029

[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. | Zbl 1113.65040

[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. | Zbl 1120.65052

[21] T. Kolda: “Orthogonal tensor decompositions” SIAM J. Matrix Anal. Appl., Vol. 23, (2001), pp. 243–255. http://dx.doi.org/10.1137/S0895479800368354 | Zbl 1005.15020

[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 | Zbl 0431.62035

[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 | Zbl 1059.81188

[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). | Zbl 1180.15025

[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 | Zbl 1120.15002

[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 | Zbl 1067.65044

[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 | Zbl 1001.65036