Randomized LU decomposition using sparse projections

DOI10.1016/j.camwa.2016.09.014zbMath1368.65068arXiv1601.04280OpenAlexW2962849440MaRDI QIDQ2012724

Yariv Aizenbud, Gil Shabat, Amir Z. Averbuch

Publication date: 3 August 2017

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

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

zbMATH Keywords

random matricessparse matricesLU decompositionsparse Johnson-Lindenstrauss transform

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Canonical forms, reductions, classification (15A21)

Related Items (7)

Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions ⋮ Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations ⋮ Randomized block Krylov subspace methods for trace and log-determinant estimators ⋮ An efficient randomized algorithm for computing the approximate Tucker decomposition ⋮ Single-pass randomized algorithms for LU decomposition ⋮ Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning ⋮ Single-pass randomized QLP decomposition for low-rank approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• A randomized algorithm for the decomposition of matrices
• A fast randomized algorithm for the approximation of matrices
• On the existence and computation of rank-revealing LU factorizations
• Strong rank revealing LU factorizations
• IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
• An Algorithm for the Principal Component Analysis of Large Data Sets
• Algorithm 971
• Low-Rank Approximation and Regression in Input Sparsity Time
• Sparser Johnson-Lindenstrauss Transforms
• Fast computation of low-rank matrix approximations
• Relative-Error $CUR$ Matrix Decompositions
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Lower Bounds for Oblivious Subspace Embeddings
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Sparsity lower bounds for dimensionality reducing maps

This page was built for publication: Randomized LU decomposition using sparse projections