Estimating a few extreme singular values and vectors for large-scale matrices in tensor train format
From MaRDI portal
Publication:5265006
matrix factorizationcomputational complexitycurse of dimensionalityrandom matrixsingular value decompositionalgorithmnumerical exampletridiagonal matrixHilbert matrixtensor networklow-rank tensor approximationHankel and Toeplitz matricesmatrix product operatorsymmetric eigenvalue decompositionalternating least squares methodtensor train decomposition
Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20) Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Toeplitz, Cauchy, and related matrices (15B05)
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.
Recommendations
- Computing low-rank approximations of large-scale matrices with the tensor network randomized SVD
- Tensor approximation approach to calculation of singular values and vectors for SVD problem
- Performance of the low-rank TT-SVD for large dense tensors on modern multicore CPUs
- Parallel Algorithms for Computing the Tensor-Train Decomposition
- Computation of extreme eigenvalues in higher dimensions using block tensor train format
Cites work
- scientific article; zbMATH DE number 758728 (Why is no real title available?)
- scientific article; zbMATH DE number 3061616 (Why is no real title available?)
- A literature survey of low-rank tensor approximation techniques
- A new scheme for the tensor representation
- ARPACK Users' Guide
- Alternating minimal energy methods for linear systems in higher dimensions
- Black box approximation of tensors in hierarchical Tucker format
- Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions
- Computation of extreme eigenvalues in higher dimensions using block tensor train format
- Computing inner eigenvalues of matrices in tensor train matrix format
- Fast monte-carlo algorithms for finding low-rank approximations
- Fast solution of parabolic problems in the tensor train/quantized tensor train format with initial application to the Fokker-Planck equation
- Fundamental tensor operations for large-scale data analysis using tensor network formats
- Limited memory block Krylov subspace optimization for computing dominant singular value decompositions
- Low-rank tensor methods with subspace correction for symmetric eigenvalue problems
- Multilevel Toeplitz matrices generated by tensor-structured vectors and convolution with logarithmic complexity
- Numerical methods for large eigenvalue problems
- On manifolds of tensors of fixed TT-rank
- On minimal subspaces in tensor representations
- Optimization problems in contracted tensor networks
- TT-cross approximation for multidimensional arrays
- Tensor Decompositions and Applications
- Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
- Tensor conjugate-gradient-type method for Rayleigh quotient minimization in block QTT-format
- Tensor-train decomposition
- The alternating linear scheme for tensor optimization in the tensor train format
- The density-matrix renormalization group in the age of matrix product states
- Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method
Cited in
(7)- Computing low-rank approximations of large-scale matrices with the tensor network randomized SVD
- Fundamental tensor operations for large-scale data analysis using tensor network formats
- Regularized computation of approximate pseudoinverse of large matrices using low-rank tensor train decompositions
- Low-rank tensor train for tensor robust principal component analysis
- Randomized algorithms for the approximations of Tucker and the tensor train decompositions
- Error Analysis of TT-Format Tensor Algorithms
- Block tensor train decomposition for missing data estimation
This page was built for publication: Estimating a few extreme singular values and vectors for large-scale matrices in tensor train format
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5265006)
