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

Namgil Lee, Andrzej Cichocki

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

Abstract

We propose new algorithms for singular value decomposition (SVD) of large-scale matrices based on a low-rank tensor approximation technique called the tensor train (TT) format. The proposed algorithms can compute a few extreme (i.e., largest or smallest) 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 approximate low-rank TT decompositions. The proposed methods, which are called the alternating least squares SVD (ALS-SVD) and modified alternating least squares SVD (MALS-SVD), compute the left and right singular vectors approximately through block TT decompositions. A 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 SVD method. The optimal ranks of the block TT decompositions are determined adaptively during the iteration process, so that we can achieve high approximation accuracy. Extensive numerical simulations are conducted for several types of TTstructured matrices such as the Hilbert matrix, a random matrix with prescribed singular values, Hankel and Toeplitz matrices, and tridiagonal matrices. The proposed methods are also applied for computing stationary solutions of a partial differential equation. The experimental results demonstrate the effectiveness of the proposed methods in estimating a few extreme singular values and vectors, compared with the performance of standard SVD algorithms and TT-based algorithms developed for symmetric eigenvalue decomposition.

Original languageEnglish
Pages (from-to)994-1014
Number of pages21
JournalSIAM Journal on Matrix Analysis and Applications
Volume36
Issue number3
DOIs
Publication statusPublished - 2015
Externally publishedYes

Keywords

  • (Modified) alternating least squares ((M)ALS)
  • Curse of dimensionality
  • Low-rank tensor approximation
  • Matrix factorization
  • Matrix product operator
  • Singular value decomposition (SVD)
  • Symmetric eigenvalue decomposition (EVD)
  • Tensor network
  • Tensor train (TT) decomposition

Fingerprint

Dive into the research topics of 'Estimating a few extreme singular values and vectors for large-scale matrices in tensor train format'. Together they form a unique fingerprint.

Cite this