Very Large-Scale Singular Value Decomposition Using Tensor Train Networks

Abstract

We propose new algorithms for singular value decomposition (SVD) of very large-scale matrices based on a low-rank tensor approximation technique called the tensor train (TT) format. The proposed algorithms can compute several dominant singular values and corresponding singular vectors for large-scale structured matrices given in a TT format. The computational complexity of the proposed methods scales logarithmically with the matrix size under the assumption that both the matrix and the singular vectors admit low-rank TT decompositions. The proposed methods, which are called the alternating least squares for SVD (ALS-SVD) and modified alternating least squares for SVD (MALS-SVD), compute the left and right singular vectors approximately through block TT decompositions. The very large-scale optimization problem is reduced to sequential small-scale optimization problems, and each core tensor of the block TT decompositions can be updated by applying any standard optimization methods. The optimal ranks of the block TT decompositions are determined adaptively during iteration process, so that we can achieve high approximation accuracy. Extensive numerical simulations are conducted for several types of TT-structured matrices such as Hilbert matrix, Toeplitz matrix, random matrix with prescribed singular values, and tridiagonal matrix. The simulation results demonstrate the effectiveness of the proposed methods compared with standard SVD algorithms and TT-based algorithms developed for symmetric eigenvalue decomposition.

References in corpus (5)

• The density-matrix renormalization group in the age of matrix product states
• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Singular Value Decomposition and Principal Component Analysis
• Fundamental Tensor Operations for Large-Scale Data Analysis in Tensor Train Formats

Cited by in corpus (12)

• Efficient tensor completion for color image and video recovery: Low-rank tensor train
• Tensor Ring Decomposition
• Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives
• Tensor Train Factorization and Completion under Noisy Data with Prior Analysis and Rank Estimation
• Fundamental Tensor Operations for Large-Scale Data Analysis in Tensor Train Formats
• Regularized Computation of Approximate Pseudoinverse of Large Matrices Using Low-Rank Tensor Train Decompositions
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers
• Efficient Quantum Circuits for Accurate State Preparation of Smooth, Differentiable Functions
• The trouble with tensor ring decompositions
• Computing low-rank approximations of large-scale matrices with the Tensor Network randomized SVD
• Too many secants: a hierarchical approach to secant-based dimensionality reduction on large data sets
• Tensor Train Quantum State Tomography using Compressed Sensing