Estimating a few extreme singular values and vectors for large-scale matrices in tensor train format

DOI10.1137/140983410zbMATH Open1319.65029arXiv1410.6895OpenAlexW3105925603WikidataQ60486500 ScholiaQ60486500MaRDI QIDQ5265006FDOQ5265006

Authors: Namgil Lee, Andrzej Cichocki 

Publication date: 21 July 2015

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1410.6895

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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)

Cites Work

• ARPACK Users' Guide
• Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method
• Tensor Decompositions and Applications
• Tensor-train decomposition
• TT-cross approximation for multidimensional arrays
• Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Fast monte-carlo algorithms for finding low-rank approximations
• Numerical methods for large eigenvalue problems
• Title not available (Why is that?)
• A literature survey of low-rank tensor approximation techniques
• Fast solution of parabolic problems in the tensor train/quantized tensor train format with initial application to the Fokker-Planck equation
• Alternating Minimal Energy Methods for Linear Systems in Higher Dimensions
• The density-matrix renormalization group in the age of matrix product states
• Optimization problems in contracted tensor networks
• A new scheme for the tensor representation
• Multilevel Toeplitz matrices generated by tensor-structured vectors and convolution with logarithmic complexity
• The alternating linear scheme for tensor optimization in the tensor train format
• Tensor conjugate-gradient-type method for Rayleigh quotient minimization in block QTT-format
• Computation of extreme eigenvalues in higher dimensions using block tensor train format
• Limited memory block Krylov subspace optimization for computing dominant singular value decompositions
• On manifolds of tensors of fixed TT-rank
• On minimal subspaces in tensor representations
• Black box approximation of tensors in hierarchical Tucker format
• Low-Rank Tensor Methods with Subspace Correction for Symmetric Eigenvalue Problems
• Fundamental tensor operations for large-scale data analysis using tensor network formats
• Computing Inner Eigenvalues of Matrices in Tensor Train Matrix Format
• Title not available (Why is that?)

Cited In (7)

• 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
• Low-rank tensor train for tensor robust principal component analysis
• Error Analysis of TT-Format Tensor Algorithms
• Fundamental tensor operations for large-scale data analysis using tensor network formats
• Computing Low-Rank Approximations of Large-Scale Matrices with the Tensor Network Randomized SVD
• 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)