Estimating a few extreme singular values and vectors for large-scale matrices in tensor train format
From MaRDI portal
(Redirected from Publication:5265006)
algorithmalternating least squares methodcomputational complexitycurse of dimensionalityHankel and Toeplitz matricesHilbert matrixlow-rank tensor approximationmatrix factorizationmatrix product operatornumerical examplerandom matrixsingular value decompositionsymmetric eigenvalue decompositiontensor networktensor train decompositiontridiagonal matrix
Eigenvalues, singular values, and eigenvectors (15A18) Toeplitz, Cauchy, and related matrices (15B05) Random matrices (algebraic aspects) (15B52) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20)
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
- A literature survey of low-rank tensor approximation techniques
- A new scheme for the tensor representation
- Alternating minimal energy methods for linear systems in higher dimensions
- ARPACK Users' Guide
- 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
- scientific article; zbMATH DE number 758728 (Why is no real title available?)
- scientific article; zbMATH DE number 3061616 (Why is no real title available?)
- 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
- Tensor conjugate-gradient-type method for Rayleigh quotient minimization in block QTT-format
- Tensor Decompositions and Applications
- Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
- 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
- TT-cross approximation for multidimensional arrays
Cited in
(8)- Block tensor train decomposition for missing data estimation
- Low-rank tensor train for tensor robust principal component analysis
- Randomized algorithms for the approximations of Tucker and the tensor train decompositions
- Regularized computation of approximate pseudoinverse of large matrices using low-rank tensor train decompositions
- Error Analysis of TT-Format Tensor Algorithms
- Computing low-rank approximations of large-scale matrices with the tensor network randomized SVD
- Efficient randomized algorithms for computing an approximation of the tensor train decomposition
- Fundamental tensor operations for large-scale data analysis using tensor network formats
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)
