Low rank Tucker-type tensor approximation to classical potentials

B. Khoromskij; V. Khoromskaia

Open Mathematics (2007)

  • Volume: 5, Issue: 3, page 523-550
  • ISSN: 2391-5455

Abstract

top
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 1 x - y , e - α x - y , e - x - y x - y and 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.

How to cite

top

B. Khoromskij, and V. Khoromskaia. "Low rank Tucker-type tensor approximation to classical potentials." Open Mathematics 5.3 (2007): 523-550. <http://eudml.org/doc/269053>.

@article{B2007,
abstract = {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.},
author = {B. Khoromskij, V. Khoromskaia},
journal = {Open Mathematics},
keywords = {Kronecker products; Tucker decomposition; multi-dimensional integral operators; multivariate functions; classical potentials; convolution products; tensors; least-squares algorithm; super-convergence; numerical results},
language = {eng},
number = {3},
pages = {523-550},
title = {Low rank Tucker-type tensor approximation to classical potentials},
url = {http://eudml.org/doc/269053},
volume = {5},
year = {2007},
}

TY - JOUR
AU - B. Khoromskij
AU - V. Khoromskaia
TI - Low rank Tucker-type tensor approximation to classical potentials
JO - Open Mathematics
PY - 2007
VL - 5
IS - 3
SP - 523
EP - 550
AB - 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.
LA - eng
KW - Kronecker products; Tucker decomposition; multi-dimensional integral operators; multivariate functions; classical potentials; convolution products; tensors; least-squares algorithm; super-convergence; numerical results
UR - http://eudml.org/doc/269053
ER -

References

top
  1. [1] B.W. Bader and T.G. Kolda: MATLAB tensor classes for fast algorithm prototyping. SANDIA Report, SAND2004-5187, Sandia National Laboratories, 2004. 
  2. [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 Zbl1008.65026
  3. [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 Zbl0202.19101
  4. [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 Zbl0962.15005
  5. [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 Zbl0958.15026
  6. [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 Zbl1080.65031
  7. [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 Zbl1126.15007
  8. [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. [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. [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 Zbl1071.65032
  11. [11] G.H. Golub and C.F. Van Loan: Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 1996. Zbl0865.65009
  12. [12] W. Hackbusch: “Fast and exact projected convolution for non-equidistant grids”, Preprint: 102, MPI MIS, Leipzig 2006. 
  13. [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 Zbl1087.65049
  14. [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 Zbl1087.65050
  15. [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 Zbl1081.65035
  16. [16] W. Hackbusch, B.N. Khoromskij and E.E. Tyrtyshnikov: “Approximate Iterations for Structured Matrices”, Preprint: 112, MPI MIS, Leipzig 2005 (Numer. Math., submitted). Zbl1144.65029
  17. [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. [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. Zbl1113.65040
  19. [19] B.N. Khoromskij: “An introduction to structured tensor-product representation of discrete nonlocal operators”, Lecture Notes MPI MIS Leipzig, Vol. 27, (2005). 
  20. [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. Zbl1120.65052
  21. [21] T. Kolda: “Orthogonal tensor decompositions” SIAM J. Matrix Anal. Appl., Vol. 23, (2001), pp. 243–255. http://dx.doi.org/10.1137/S0895479800368354 Zbl1005.15020
  22. [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. [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 Zbl0431.62035
  24. [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 Zbl1059.81188
  25. [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). Zbl1180.15025
  26. [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. [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 Zbl1120.15002
  28. [28] A. Smilde, R. Broa and P. Geladi: Multi-way Analysis, Wiley, 2004. 
  29. [29] J. Strang and G.J. Fix: An Analysis of the Finite Element Method, Prentice-Hall, inc. N. J., 1973. 
  30. [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. [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. [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 Zbl1067.65044
  33. [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 Zbl1001.65036

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.