Abstract
In this article we introduce a calculus of variations for sums of elementary tensors and apply it to functionals of practical interest. The survey provides all necessary ingredients for applying minimization methods in a general setting. The important cases of target functionals which are linear and quadratic with respect to the tensor product are discussed, and combinations of these functionals are presented in detail. As an example, we consider the solution of a linear system in structured tensor format. Moreover, we discuss the solution of an eigenvalue problem with sums of elementary tensors. This example can be viewed as a prototype of a constrained minimization problem. For the numerical treatment, we suggest a method which has the same order of complexity as the popular alternating least square algorithm and demonstrate the rate of convergence in numerical tests.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Beylkin G., Mohlenkamp M.J.: Numerical operator calculus in higher dimensions. Proc. Natl. Acad. Sci. USA 99(16), 10246–10251 (2002)
Beylkin G., Mohlenkamp M.J.: Algorithms for numerical analysis in high dimensions. SIAM J. Sci. Comput. 26(6), 2133–2159 (2005)
Beylkin, G., Mohlenkamp, M.J., Pérez, F.: Approximating a wavefunction as an unconstrained sum of Slater determinants. J. Math. Phys. 49(3):032107 (2008)
Braess D., Hackbusch W.: Approximation of 1/x by exponential sums in [1,∞). IMA Numer. Anal. 25, 685–697 (2005)
de Silva, V., Lim, L.-H.: Tensor rank and the ill-posedness of the best low-rank approximation problem. Technical Report SCCM-06-06, Stanford University (2006)
Eldén, L., Savas, B.: A Newton–Grassmann method for computing the best multi-linear (r 1, r 2, r 3) approximation of a tensor. SIAM J. Mat. Anal. Appl. 31, 248–271 (2009)
Espig, M.: Effiziente Bestapproximation mittels Summen von Elementartensoren in hohen Dimensionen. PhD thesis, Universität Leipzig (2008)
Espig, M., Grasedyck, L., Hackbusch, W.: Black box low tensor rank approximation using fibre-crosses. Const. Approx. 30, 557–597 (2009)
Espig, M., Hackbusch, W.: A regularized newton method for the efficient approximation of tensors represented in the canonical tensor format. Submitted to Num. Math. (2010)
Falcó, A., Hackbusch, W.: On minimal subspaces in tensor representations. MIS Preprint 70 (2010)
Gavrilyuk I.P., Hackbusch W., Khoromskij B.N.: Hierarchical tensor-product approximation to the inverse and related operators for high-dimensional elliptic problems. Computing 74(2), 131–157 (2005)
Grasedyck L.: Existence and computation of low Kronecker-rank approximations for large linear systems of tensor product structure. Computing 72, 247–265 (2004)
Greub W.H.: Multilinear Algebra. Springer, Berlin (1967)
Hackbusch W., Khoromskij B.N.: Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators. Part I. Separable approximation of multi-variate functions. Computing 76(3–4), 177–202 (2006)
Hackbusch W., Khoromskij B.N.: Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators. Part II. HKT representation of certain operators. Computing 76(3–4), 203–225 (2006)
Hackbusch W., Khoromskij B.N., Tyrtyshnikov E.E.: Approximate iterations for structured matrices. Numer. Math. 109(3), 365–383 (2008)
Hackbusch W., Kühn S.: A new scheme for the tensor representation. J. Fourier Anal. 15, 706–722 (2009)
Holtz, S., Rohwedder, T., Schneider, R.: The alternating linear scheme for tensor optimisation in the tt format. SISC (2010)
Holtz, S., Rohwedder, T., Schneider, R.: On manifolds of tensors of fixed tt rank. Numer. Math 120, 701–731 (2012)
Ishteva M., Absil P.-A., van Huffel S., de Lathauwer L.: Best low multilinear rank approximation of higher-order tensors based on the riemannian trust region scheme. SIAM J. Matrix Anal. Appl. 32, 115–135 (2011)
Kapteyn A., Neudecker H., Wansbeek T.: An approach to n-mode components analysis. Psychometrika 51, 269 (1986)
Koch O., Lubich C.: Dynamical low-rank approximation of tensors. SIAM J. Matrix Anal. 31, 2360 (2010)
Kosmol, P.: A new class of derivative-free procedures for finding zeros of a function. Computing (1993)
Kroonenberg P.M., De Leeuw J.: Principal component analysis of three-mode data by means of alternating least squares algorithms. Psychometrika 45, 69 (1980)
Max-Planck-Institut für Mathematik in den Naturwissenschaften Leipzig. http://www.mis.mpg.de/scicomp/exp_sum
Oseledets, I.: Tensor-train decomposition. SIAM J. Sci. Comput. 33(5), 2295–2317 (2011)
Oseledets I.V.: On a new tensor decomposition. Doklady Math. 427, 2 (2009)
Oseledets, I. V., Tyrtyshnikov, E. E.: Tensor tree decomposition does not need a tree. Institute of Numerical Mathematics RAS (2009, preprint)
Savas B., Lim L.-H.: Quasi-newton methods on grassmannians and multilinear approximations of tensors. SIAM J. Sci. Comput. 32, 3352–3393 (2010)
Tucker L.R.: Some mathematical notes on three-mode factor analysis. Psychometrica 31, 279–311 (1966)
Uschmajew, A.: Well-posedness of convex maximization problems on stiefel manifolds and orthogonal tensor product approximations. Numer. Math 115, 309–331 (2010)
Yokonuma T.: Tensor Spaces and Exterior Algebra. American Mathematical Society, Providence, R.I. (1991)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Espig, M., Hackbusch, W., Rohwedder, T. et al. Variational calculus with sums of elementary tensors of fixed rank. Numer. Math. 122, 469–488 (2012). https://doi.org/10.1007/s00211-012-0464-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-012-0464-x