Randomized interpolative decomposition of separated representations
From MaRDI portal
Abstract: We introduce tensor Interpolative Decomposition (tensor ID) for the reduction of the separation rank of Canonical Tensor Decompositions (CTDs). Tensor ID selects, for a user-defined accuracy epsilon, a near optimal subset of terms of a CTD to represent the remaining terms via a linear combination of the selected terms. Tensor ID can be used as an alternative to or a step of the Alternating Least Squares (ALS) algorithm. In addition, we briefly discuss Q-factorization to reduce the size of components within an ALS iteration. Combined, tensor ID and Q-factorization lead to a new paradigm for the reduction of the separation rank of CTDs. In this context, we also discuss the spectral norm as a computational alternative to the Frobenius norm. We reduce the problem of finding tensor IDs to that of constructing Interpolative Decompositions of certain matrices. These matrices are generated via either randomized projection or randomized sampling of the given tensor. We provide cost estimates and several examples of the new approach to the reduction of separation rank.
Recommendations
- Fast randomized matrix and tensor interpolative decomposition using countsketch
- Random Projections for Low Multilinear Rank Tensors
- An adaptive algebraic multigrid algorithm for low-rank canonical tensor decomposition
- A regularized Newton method for the efficient approximation of tensors represented in the canonical tensor format
- Randomized algorithms for the approximations of Tucker and the tensor train decompositions
Cites work
- A comparison of algorithms for fitting the PARAFAC model
- A fast algorithm for the inversion of general Toeplitz matrices
- A fast randomized algorithm for the approximation of matrices
- A literature survey of low-rank tensor approximation techniques
- A randomized algorithm for a tensor-based generalization of the singular value decomposition
- A randomized algorithm for the decomposition of matrices
- A theory of pseudoskeleton approximations
- Accurate Singular Value Decompositions of Structured Matrices
- Algorithms for Numerical Analysis in High Dimensions
- Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
- Approximating a wavefunction as an unconstrained sum of Slater determinants
- Black box approximation of tensors in hierarchical Tucker format
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Extensions of Lipschitz mappings into a Hilbert space
- Fast computation of low-rank matrix approximations
- Fast monte-carlo algorithms for finding low-rank approximations
- Fast wavelet transforms and numerical algorithms I
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- scientific article; zbMATH DE number 554500 (Why is no real title available?)
- scientific article; zbMATH DE number 637070 (Why is no real title available?)
- scientific article; zbMATH DE number 1082094 (Why is no real title available?)
- scientific article; zbMATH DE number 2079343 (Why is no real title available?)
- Incomplete cross approximation in the mosaic-skeleton method
- Low rank tensor recovery via iterative hard thresholding
- Mosaic-skeleton approximations
- Multiresolution representation of operators with boundary conditions on simple domains
- Multivariate regression and machine learning with sums of separable functions
- Musings on multilinear fitting
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Numerical operator calculus in higher dimensions
- On the Best Rank-1 and Rank-(R1 ,R2 ,. . .,RN) Approximation of Higher-Order Tensors
- On the best rank-1 approximation of higher-order supersymmetric tensors
- On the Compression of Low Rank Matrices
- On the Representation of Operators in Bases of Compactly Supported Wavelets
- Pseudo-skeleton approximations by matrices of maximal volume
- Randomized algorithms for the low-rank approximation of matrices
- Rank-one approximation to high order tensors
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sampling from large matrices
- Shifted power method for computing tensor eigenpairs
- Tensor decomposition and approximation schemes for constraint satisfaction problems
- Tensor Decompositions and Applications
- Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
- TT-cross approximation for multidimensional arrays
Cited in
(18)- Optimization via separated representations and the canonical tensor decomposition
- Fast randomized matrix and tensor interpolative decomposition using countsketch
- An efficient algorithm for computing the approximate t-URV and its applications
- Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
- Reduction of multivariate mixtures and its applications
- Randomized algorithms for the low multilinear rank approximations of tensors
- Numerical methods for high-dimensional probability density function equations
- Randomized alternating least squares for canonical tensor decompositions: application to a PDE with random data
- HOID: higher order interpolatory decomposition for tensors based on Tucker representation
- Recent advances on the use of separated representations
- Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Structured random sketching for PDE inverse problems
- Fiber sampling approach to canonical polyadic decomposition and application to tensor completion
- Sketch-based multiplicative updating algorithms for symmetric nonnegative tensor factorizations with applications to face image clustering
- Fast algorithms for least squares problems with Kronecker lower subsets
- Efficient randomized algorithms for computing an approximation of the tensor train decomposition
- Subspace embedding with random Khatri-Rao products and its application to eigensolvers
This page was built for publication: Randomized interpolative decomposition of separated representations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q728743)
