A randomized algorithm for a tensor-based generalization of the singular value decomposition

DOI10.1016/j.laa.2006.08.023zbMath1108.65032OpenAlexW1972547249MaRDI QIDQ861021

Michael W. Mahoney, Petros Drineas

Publication date: 9 January 2007

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2006.08.023

zbMATH Keywords

randomized algorithmstensor decompositionCUR decomposition

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Vector and tensor algebra, theory of invariants (15A72) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (22)

Randomized algorithms for the approximations of Tucker and the tensor train decompositions ⋮ Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format ⋮ Practical Leverage-Based Sampling for Low-Rank Tensor Decomposition ⋮ Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations ⋮ Low tubal rank tensor completion based on singular value factors ⋮ The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection ⋮ Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1. ⋮ A Riemannian Trust Region Method for the Canonical Tensor Rank Approximation Problem ⋮ Randomized algorithms for the low multilinear rank approximations of tensors ⋮ Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection ⋮ Greedy low-rank approximation in Tucker format of solutions of tensor linear systems ⋮ Randomized SVD methods in hyperspectral imaging ⋮ Fast randomized matrix and tensor interpolative decomposition using countsketch ⋮ Randomized interpolative decomposition of separated representations ⋮ Incremental learning of bidirectional principal components for face recognition ⋮ An efficient randomized algorithm for computing the approximate Tucker decomposition ⋮ Turbo‐SMT: Parallel coupled sparse matrix‐Tensor factorizations and applications ⋮ HOID: Higher Order Interpolatory Decomposition for Tensors Based on Tucker Representation ⋮ Fiber Sampling Approach to Canonical Polyadic Decomposition and Application to Tensor Completion ⋮ Coupled Canonical Polyadic Decompositions and (Coupled) Decompositions in Multilinear Rank- $(L_{r,n},L_{r,n},1)$ Terms---Part II: Algorithms ⋮ A literature survey of low-rank tensor approximation techniques ⋮ Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format

Uses Software

• Algorithm 844
• PARAFAC

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• PARAFAC: Parallel factor analysis
• Principal component analysis of three-mode data by means of alternating least squares algorithms
• On the complexity of computing bilinear forms with \(\{0,1\}\) constants
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• Global properties of tensor rank
• A theory of pseudoskeleton approximations
• A singular value decomposition of a \(k\)-way array for a principal component analysis of multiway data, \(\text{PTA-}k\)
• The ubiquitous Kronecker product
• Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
• Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
• Orthogonal Tensor Decompositions
• Rank-One Approximation to High Order Tensors
• Tensor rank is NP-complete
• Competitive recommendation systems
• Tensor decomposition and approximation schemes for constraint satisfaction problems
• Matrix approximation and projective clustering via volume sampling
• Sampling algorithms for l₂ regression and applications
• A Counterexample to the Possibility of an Extension of the Eckart--Young Low-Rank Approximation Theorem for the Orthogonal Rank Tensor Decomposition
• A Multilinear Singular Value Decomposition
• On the Best Rank-1 and Rank-(R₁ ,R₂ ,. . .,R_N) Approximation of Higher-Order Tensors
• Numerical operator calculus in higher dimensions
• Fast computation of low rank matrix approximations
• Tensor-CUR Decompositions for Tensor-Based Data
• Fast monte-carlo algorithms for finding low-rank approximations
• Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods
• Algorithm 844
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
• Learning Theory
• Multilinear Algebra

This page was built for publication: A randomized algorithm for a tensor-based generalization of the singular value decomposition