Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2007 | 5 | 3 | 523-550
Tytuł artykułu

Low rank Tucker-type tensor approximation to classical potentials

Treść / Zawartość
Warianty tytułu
Języki publikacji
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.
Opis fizyczny
  • [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.
  • [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.
  • [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.
  • [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.
  • [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.
  • [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.
  • [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.
  • [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.
  • [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.
  • [15] W. Hackbusch, B.N. Khoromskij and E.E. Tyrtyshnikov: “Hierarchical Kronecker tensor-product approximations”, J. Numer. Math., Vol. 13, (2005), pp. 119–156.
  • [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.
  • [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.
  • [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.
  • [24] Ch. Lubich: “On variational approximations in quantum molecular dynamics”, Math. Comp. Vol. 74, (2005), pp. 765–779.
  • [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.<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.
  • [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.
  • [31] L.R. Tucker: “Some mathematical notes on three-mode factor analysis”, Psychometrika, Vol. 31, (1966), pp. 279–311.
  • [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).
  • [33] T. Zang and G. Golub: “Rank-0ne approximation to high order tensors”, SIAM J. Matrix Anal. Appl., Vol. 23, (2001), pp. 534–550.
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.