Source-linked AI summary
Time integration of tensor trains
Christian Lubich, Ivan Oseledets, Bart Vandereycken
TL;DR
The paper addresses efficient approximation of time-dependent large tensors and tensor differential equations in fixed-rank TT/MPS format. It extends matrix projector splitting by decomposing the TT/MPS tangent-space projector and obtains closed-form, efficiently sweepable substeps. The resulting first- and second-order integrators are exact for sufficiently short intervals when the exact solution remains on the manifold, and are tested in quantum dynamics and approximate matrix inversion.
Problem
The paper seeks efficient fixed-rank TT/MPS approximations for explicitly given time-dependent tensors and solutions of tensor differential equations.
Method
The method splits the tangent-space projector into orthogonal components whose differential subproblems have closed-form solutions and can be implemented by forward or backward sweeps.
Results
The first- and second-order splitting integrators are exact for sufficiently small time intervals when A(t) remains on the fixed-rank manifold and the method starts from A(t0).
Takeaways & Limitations
The integrator supports dynamical TT/MPS approximation, quantum molecular dynamics, and iterative processes such as approximate matrix inversion.
Takeaways & Limitations
In approximate matrix inversion, the residual may stabilize or diverge once the manifold cannot represent a sufficiently good inverse; explaining this behavior is outside the paper’s scope.
Abstract
from arXiv · showhide
A robust and efficient time integrator for dynamical tensor approximation in the tensor train or matrix product state format is presented. The method is based on splitting the projector onto the tangent space of the tensor manifold. The algorithm can be used for updating time-dependent tensors in the given data-sparse tensor train / matrix product state format and for computing an approximate solution to high-dimensional tensor differential equations within this data-sparse format. The formulation, implementation and theoretical properties of the proposed integrator are studied, and numerical experiments with problems from quantum molecular dynamics and with iterative processes in the tensor train format are included.
1. Introduction.
The paper develops a dynamical low-rank approach for approximating time-dependent large tensors in fixed-rank TT/MPS format. It extends the matrix projector-splitting integrator by decomposing the TT/MPS tangent-space projector.
- Motivation: The target is a lower-complexity TT/MPS approximation of an explicitly known tensor or a tensor differential-equation solution.The setting includes high-dimensional evolutionary partial differential equations.
- Dynamical low-rank formulation: Dynamical low-rank approximation evolves Y(t) on a fixed-rank manifold using the orthogonal projection of the driving term onto its tangent space.This is formulated through the Dirac–Frenkel time-dependent variational principle.
- Contribution: The paper extends the matrix projector-splitting integrator to time-dependent TT/MPS approximation.The extension addresses the TT/MPS version of the time-dependent approximation problem.
- Contribution: The tangent-space projector is studied through an additive decomposition, which yields the basis for the proposed splitting integrator.The paper also studies implementation, theoretical properties, quantum dynamics, and iterative TT/MPS processes.
2. Tensor trains / matrix product states: prerequisites.
This section introduces TT/MPS tensors as low-complexity representations built from core tensors, unfoldings, and partial products. Recursive orthogonalizations and SVDs organize these representations for later tangent-space and integrator constructions.
- TT/MPS format: A TT/MPS tensor is represented by core tensors Ci ∈ R^{r_i−1×n_i×r_i} with boundary ranks r0 = rd = 1.Each tensor entry is formed by multiplying the corresponding matrix slices of the cores.
- TT/MPS format: TT/MPS representations use at most dNR^2 degrees of freedom, versus N^d entries for a general tensor when dimensions and ranks are bounded.Here N = max{ni} and R = max{ri}.
- Partial products and orthogonalization: Left and right partial products form the factors associated with tensor unfoldings and can be recursively orthogonalized.Left orthogonalization proceeds through a forward sweep, while right orthogonalization proceeds through a backward sweep.
- Partial products and orthogonalization: QR decompositions of partial products can be computed efficiently using recursive relations between neighboring unfoldings.These decompositions provide the orthonormal factors used in subsequent constructions.
- Recursive SVD: Recursive SVDs combine left and right orthogonalized factors with a central matrix and can be propagated from one unfolding to the next.The central matrix Si may be chosen diagonal, and the construction is illustrated for the third recursive SVD.
3. Orthogonal projection onto the tangent space.
The paper derives an explicit orthogonal projector onto the tangent space of the fixed-rank TT/MPS manifold. Its orthogonal decomposition into local variation spaces enables the later projector-splitting integrator.
- Projector construction: For a tensor X on the fixed-rank TT/MPS manifold, the tangent-space projector PX(Z) is characterized variationally for arbitrary tensor Z.The projector uses the ranges of left and right partial products.
- Tangent-space decomposition: The tangent space decomposes uniquely into mutually orthogonal subspaces Vi representing first-order variations of individual cores under gauge conditions.The decomposition is written as δX = Σi δXi with δXi ∈ Vi.
- Tangent-space decomposition: The orthogonality of the variation spaces follows from left orthogonalization and the imposed gauge conditions.This orthogonality is noted as implicit in the cited tangent-space parametrization and proved explicitly here.
- Projector construction: QR decompositions of left and right partial products produce orthogonal projectors P≤i and P≥i onto their respective ranges.Boundary projectors are set as P≤0 = 1 and P≥d+1 = 1.
- Additive projector formula: The projector admits a simpler additive representation using commuting left and right range projectors.The commutation holds for P≤i and P≥j when i < j.
4. Projector-splitting integrator.
The integrator splits the tangent-space projected dynamics into solvable substeps and implements them as efficient forward and backward sweeps. The resulting scheme supports first- and second-order time stepping and is exact for constant-rank tensor trains, even with arbitrarily small positive unfolding singular values.
- Abstract formulation: The tensor-train dynamics are defined by projecting the differential equation onto the tangent space of the fixed-rank manifold.The projected equation evolves an approximation Y(t) from an initial value Y0 in the manifold.
- Abstract formulation: The tangent-space projector has an additive decomposition that yields a Lie–Trotter splitting into consecutive differential-equation substeps.The split terms use orthogonal projectors associated with the tensor-train representation.
- Closed-form substeps: Each split differential equation has a closed-form solution, and left-to-right or right-to-left ordering enables efficient implementation.The method updates tensor-train cores and maintains orthogonalized factorizations during the sweep.
- Efficient implementation: The sweeping implementation selectively updates cores and uses QR factorizations and orthogonalization to prepare and continue successive time steps.Forward and backward sweeps preserve recursive SVD structures while updating only the necessary cores.
- Exactness and robustness: The splitting integrator is exact when the target tensor has constant TT/MPS rank r, even if unfolding singular values are arbitrarily small.Unlike the matrix analogue, the stated tensor result requires the rank to be exactly r rather than merely bounded by r.
5. Exactness property of the integrator.
The splitting integrator is exact for tensor trajectories that remain on the fixed-rank TT/MPS manifold, under a sufficiently small time interval. This property extends to both first- and second-order schemes despite arbitrarily small positive unfolding singular values.
- Exactness theorem: For sufficiently small t1 − t0, first- and second-order splitting integrators exactly reproduce A(t1) when initialized at Y0 = A(t0) and A(t) remains on the manifold.The proof relies on invertibility of certain overlap matrices over sufficiently short intervals.
- Proof structure: The proof proceeds inductively from left to right, using full-rank overlap conditions that are guaranteed for sufficiently small time intervals because the orthogonal factors vary continuously.The condition may also hold for larger intervals, but the theorem only guarantees the sufficiently-small case.
- Proof structure: The first-order scheme obtains exactness through a forward sweep, while the second-order scheme composes it with a backward sweep using the same substeps.The backward ordering yields the analogous lemma needed for second-order exactness.
6. Numerical implementation and experiments.
The implementation uses efficient forward and backward sweeps to update TT/MPS cores, with closed-form or Krylov-based substeps for relevant linear problems. Experiments demonstrate accurate quantum spectra, faster approximate inversion, and applications to tensor optimization.
- Implementation: The integrator updates TT/MPS cores through forward and backward sweeps, avoiding explicit construction of the large Q≤i and Q≥i matrices.The computationally intensive updates are formed through tensor contractions that exploit TT/MPS structure.
- Implementation: For autonomous linear differential equations, the core and interface updates become constant-coefficient problems solvable with Krylov iterations for operator exponentials.More general differential equations can be integrated numerically, using Runge–Kutta methods of order at least two for the second-order scheme.
- Quantum dynamics: In the Henon–Heiles experiment, the splitting integrator used Expokit with relative accuracy 10^-8 for the local linear problems.The model uses a time-dependent Schrödinger equation with a Henon–Heiles potential and complex absorbing boundary potentials.
- Quantum dynamics: The computed spectra were very similar, while MCTDH required 54 354 seconds and the splitting scheme required 4 425 seconds.The comparison used a 10-dimensional Henon–Heiles problem and evaluated spectra through Fourier transforms of autocorrelation functions.
- Tensor optimization: One splitting-integrator step is proposed as a cheaper TT/MPS retraction alternative to the quasi-optimal TT-SVD projection in iterative tensor processes.The update can be computed without explicitly forming the increment when it has exploitable low-rank TT/MPS structure.
- Approximate matrix inversion: Residuals decrease until the chosen manifold cannot represent a sufficiently good inverse, after which they may stabilize or diverge.The paper identifies line search on the manifold as a possible way to address this behavior.
- Conclusion: The paper concludes that the integrator is robust and computationally efficient for TT/MPS tensor updates and approximate tensor differential equations.Quantum dynamics and tensor optimization are identified as promising application areas.
7. Conclusion.
The paper identifies possible extensions to fixed-rank hierarchical Tucker tensors and notes a close resemblance to ALS or one-site DMRG in the infinite-step limit.
- The approach appears extendable to fixed-rank hierarchical Tucker tensors and their dynamical approximation.
- As the time step tends to infinity, the integrator resembles alternating least squares or one-site DMRG, motivating further investigation.