Source-linked AI summary
A projector-splitting integrator for dynamical low-rank approximation
Christian Lubich, Ivan Oseledets
TL;DR
Dynamical low-rank approximation requires numerical integration of factor equations for time-dependent matrices, but standard integrators can encounter ill-conditioning. The paper introduces a fully explicit projector-splitting integrator and shows robustness under over-approximation, while noting extensions beyond matrices remain future work.
Problem
Standard numerical integrators for the dynamical low-rank factor equations can suffer stability and accuracy problems when the core factor is ill-conditioned or singular.
Method
The paper develops a fully explicit, computationally inexpensive integrator based on splitting the orthogonal projector onto the tangent space of the low-rank manifold.
Results
The proposed integrator remains robust under over-approximation, whereas standard explicit and implicit integrators break down in that situation.
Takeaways & Limitations
The robustness supports adaptive rank changes and efficient truncation in low-rank optimization algorithms.
Takeaways & Limitations
Extensions to tensor train and hierarchical Tucker formats are identified as forthcoming work.
Abstract
from arXiv · showhide
The dynamical low-rank approximation of time-dependent matrices is a low-rank factorization updating technique. It leads to differential equations for factors of the matrices, which need to be solved numerically. We propose and analyze a fully ex- plicit, computationally inexpensive integrator that is based on splitting the orthogonal projector onto the tangent space of the low-rank manifold. As is shown by theory and illustrated by numerical experiments, the integrator enjoys robustness properties that are not shared by any standard numerical integrator. This robustness can be exploited to change the rank adaptively. Another application is in optimization algorithms for low-rank matrices where truncation back to the given low rank can be done efficiently by applying a step of the integrator proposed here.
1 Introduction
The paper studies dynamical low-rank approximation for time-dependent matrices and develops an explicit projector-splitting integrator to update low-rank factors efficiently. Its motivation is to avoid large decompositions and ill-conditioning in standard numerical integration.
- The desired updating procedure should use increments of A and avoid repeated decompositions of large matrices.
- Time-dependent matrices can be approximated by fixed-rank matrices whose evolution is governed by differential equations on a fixed-rank manifold.
- The proposed integrator is fully explicit and computationally inexpensive, based on splitting the tangent-space projector.
- Unlike standard explicit or implicit Runge–Kutta methods, it avoids ill-conditioning in matrices arising from the dynamical low-rank equations.
- The paper analyzes the method's robustness under over-approximation, presents numerical experiments, and discusses extensions and applications.
2 Dynamical low-rank approximation of matrices
Dynamical low-rank approximation represents a time-dependent matrix on the rank-r manifold and projects its evolution onto the tangent space. The resulting factor equations become problematic when the core factor is nearly singular.
- The rank-r manifold M_r contains real m×n matrices of rank r, typically with r much smaller than m and n.
- The approximation uses Y(t)=U(t)S(t)V(t)^⊤, with orthonormal U and V and an invertible, not necessarily diagonal, S.
- The factor dynamics contain S(t)^−1 and S(t)^−⊤, making standard numerical integration cumbersome when S is nearly singular.
- Over-approximation occurs when the chosen rank exceeds the true or effective rank, a realistic situation when that rank is unknown.
- The time derivative is obtained by orthogonally projecting A(t) onto the tangent space of M_r at Y(t).
3 The integrator
The integrator splits the tangent-space projector into sequential subproblems that preserve rank and can be solved explicitly using low-rank factors. Symmetric composition yields a second-order method, with extensions to matrix differential equations.
- First-order splitting method: A first-order Lie–Trotter step advances three split differential equations sequentially from t0 to t1=t0+h.
- First-order splitting method: Each split equation can be solved exactly in a trivial way, and the resulting Y1 is first-order accurate.
- First-order splitting method: The split flows remain rank r because their right-hand sides lie in the tangent space, allowing factorization with orthonormal factors and an invertible core.
- Factorized algorithm: The practical algorithm updates low-rank factors using the increment ΔA and QR or SVD factorizations, without further approximation of the abstract split result.
- Higher-order schemes: The symmetrized splitting is a second-order scheme, and higher-order methods follow from suitable compositions.
- Matrix differential equations: For matrix differential equations, the method replaces the unknown increment with an explicit-Euler-like evaluation of the right-hand side.
4 Robustness under over-approximation
The splitting integrator remains robust under rank over-approximation, where standard factor-based integrators suffer from singular or ill-conditioned matrices. Its ordered splitting is exact for solutions of rank at most r and stays close to the corresponding lower-rank computation under small perturbations.
- Standard integrators encounter stability and accuracy problems when the factor matrix S becomes singular or ill-conditioned under rank over-approximation.This occurs when the approximated matrix has rank less than, or close to less than, the chosen rank r.
- The proposed algorithm avoids these difficulties because it contains no matrix inversion.
- The splitting order K = US, then S, then L = VS⊤ is essential for the stated exactness result.A different ordering, such as computing K, L, and S successively, does not preserve this exactness property.
- If A(t) has rank at most r and Y0 = A(t0), one splitting step is exact: Y1 = A(t1).
- Theorem 4.2 bounds the difference between rank-r and rank-q splitting results uniformly in n, h, and ε over a fixed time interval.The constant C is independent of n, h, and ε, but depends on T − t0.
- For a rank-r approximation of a perturbed rank-q matrix, the rank-r and rank-q algorithms differ by a bound controlled by the perturbation and splitting errors.The rank-q integration error is O(h^p) uniformly in ε, while the exact-solution difference is O(ε).
III, . S
The robustness proof compares the rank-r splitting computation with a rank-q computation and uses uniformly stable error propagation to establish the theorem.
- Uniform Lipschitz continuity of the rank-q differential equation's right-hand side yields stable error propagation and completes the theorem.
- The proof compares the rank-r and rank-q splitting methods through corresponding factorizations and their evolution over one step.
5 Numerical experiments
Numerical experiments compare KLS and KSL splitting variants with the implicit midpoint rule across ranks, perturbation levels, and step sizes. KSL schemes are especially robust under overapproximation and large step sizes, while KLS variants and midpoint can perform substantially worse or become unstable.
- Approximation errors: KSL schemes perform remarkably better in the overapproximation case, whereas midpoint is unstable and KLS has significantly higher error.Errors are measured against A(t), with constant step size h = 10^-3; the best rank-r SVD approximation is also plotted.
- Convergence comparisons: Both KLS schemes perform much worse in the reported comparison, and symmetrization loses its second-order behavior.The KSL scheme and its symmetrized version clearly outperform the other methods.
- Stepsize stability: For r = 20 and ε = 10^-3, midpoint becomes unstable for large h, whereas both KSL schemes give good results across h from 10^-1 to 10^-3.At t = 1, the best rank-10 and rank-20 approximations have errors approximately 10^-2 and 3 · 10^-3, respectively.
6 Conclusion and perspectives
The proposed integrator is fully explicit, computationally inexpensive, and robust under over-approximation, enabling adaptive rank control and efficient low-rank optimization updates.
- Its robustness under over-approximation avoids the ill-conditioning or singularity of the small matrix factor that can break down standard integrators.The method remains usable when the chosen rank is too high.
- Adaptive rank control can lower the rank trivially and raise it naturally by continuing from a lower-rank computation.Standard higher-rank integrators cannot generally start from the resulting singular matrix factor.
- The integrator supports optimization methods on low-rank manifolds, including conjugate-gradient and Newton methods.It provides an application for updates that must remain at the prescribed low rank.
- Low-rank truncation of an update can be performed efficiently by applying one integrator step to A+t∆A at t = 1.
- Extensions to tensor train and hierarchical Tucker formats are identified as forthcoming work.