# Low rank Tucker-type tensor approximation to classical potentials

Open Mathematics (2007)

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

## Access Full Article

top## Abstract

top## How to cite

topB. 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] 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 Zbl1008.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 Zbl0202.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 Zbl0962.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 Zbl0958.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 Zbl1080.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 Zbl1126.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 Zbl1071.65032
- [11] G.H. Golub and C.F. Van Loan: Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 1996. Zbl0865.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 Zbl1087.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 Zbl1087.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 Zbl1081.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). Zbl1144.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. Zbl1113.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. Zbl1120.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 Zbl1005.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 Zbl0431.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 Zbl1059.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). Zbl1180.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 Zbl1120.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 Zbl1067.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 Zbl1001.65036

## NotesEmbed ?

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