Fast randomized matrix and tensor interpolative decomposition using countsketch

DOI10.1007/s10444-020-09816-9zbMath1469.65089arXiv1901.10559OpenAlexW3097522760MaRDI QIDQ2025436

Osman Asif Malik, Stephen R. Becker

Publication date: 14 May 2021

Published in: Advances in Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

sketchingmatrix decompositiontensor decomposition

Mathematics Subject Classification ID

Factorization of matrices (15A23) Numerical linear algebra (65F99)

Related Items (2)

An efficient algorithm for computing the approximate t-URV and its applications ⋮ Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations

Uses Software

• Blendenpik

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Tensor Decompositions and Applications
• CUR matrix decompositions for improved data analysis
• A randomized algorithm for the decomposition of matrices
• Randomized interpolative decomposition of separated representations
• A randomized algorithm for a tensor-based generalization of the singular value decomposition
• A fast randomized algorithm for the approximation of matrices
• Generalizing the column-row matrix decomposition to multi-way arrays
• Pseudo-skeleton approximations by matrices of maximal volume
• A theory of pseudoskeleton approximations
• Incomplete cross approximation in the mosaic-skeleton method
• Optimization via separated representations and the canonical tensor decomposition
• Finding frequent items in data streams
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
• Efficient algorithms for CUR and interpolative matrix decompositions
• Randomized Alternating Least Squares for Canonical Tensor Decompositions: Application to A PDE With Random Data
• Optimal CUR Matrix Decompositions
• Randomized algorithms for the low-rank approximation of matrices
• Fast low rank approximations of matrices and tensors
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Low-Rank Approximation and Regression in Input Sparsity Time
• Matrix approximation and projective clustering via volume sampling
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• Relative-Error $CUR$ Matrix Decompositions
• Theoretical Numerical Analysis
• Numerical operator calculus in higher dimensions
• A randomized tensor singular value decomposition based on the t‐product
• A Practical Randomized CP Tensor Decomposition
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Fast Randomized Algorithms for t-Product Based Tensor Operations and Decompositions with Applications to Imaging Data
• On the Compression of Low Rank Matrices
• Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time
• Tensor-CUR Decompositions for Tensor-Based Data
• Fast monte-carlo algorithms for finding low-rank approximations
• Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
• Near-Optimal Column-Based Matrix Reconstruction
• Algorithms for Numerical Analysis in High Dimensions
• Optimal Column-Based Low-Rank Matrix Reconstruction
• Compressed matrix multiplication

This page was built for publication: Fast randomized matrix and tensor interpolative decomposition using countsketch