Randomized LU decomposition using sparse projections
From MaRDI portal
Publication:2012724
Abstract: A fast algorithm for the approximation of a low rank LU decomposition is presented. In order to achieve a low complexity, the algorithm uses sparse random projections combined with FFT-based random projections. The asymptotic approximation error of the algorithm is analyzed and a theoretical error bound is presented. Finally, numerical examples illustrate that for a similar approximation error, the sparse LU algorithm is faster than recent state-of-the-art methods. The algorithm is completely parallelizable that enables to run on a GPU. The performance is tested on a GPU card, showing a significant improvement in the running time in comparison to sequential execution.
Recommendations
- Randomized LU decomposition
- Matrix decompositions using sub-Gaussian random matrices
- Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
- Single-pass randomized algorithms for LU decomposition
- A randomized algorithm for the decomposition of matrices
Cites work
- A fast randomized algorithm for the approximation of matrices
- A randomized algorithm for the decomposition of matrices
- Algorithm 971
- An algorithm for the principal component analysis of large data sets
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Fast computation of low-rank matrix approximations
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- scientific article; zbMATH DE number 1301967 (Why is no real title available?)
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- Improved analysis of the subsampled randomized Hadamard transform
- Lower bounds for oblivious subspace embeddings
- On the existence and computation of rank-revealing LU factorizations
- Relative-Error CUR Matrix Decompositions
- Sparser Johnson-Lindenstrauss transforms
- Sparsity lower bounds for dimensionality reducing maps
- Strong rank revealing LU factorizations
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
Cited in
(14)- Randomized LU decomposition
- Randomized block Krylov subspace methods for trace and log-determinant estimators
- An efficient randomized algorithm for computing the approximate Tucker decomposition
- Single-pass randomized QLP decomposition for low-rank approximation
- Single-pass randomized algorithms for LU decomposition
- Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Randomized algorithms for the computation of multilinear rank-(_1,_2,_3) approximations
- Efficient randomized algorithms for computing an approximation of the tensor train decomposition
- Low-rank approximation: randomized QR with column pivoting and related methods using sparse projection and pass-efficient techniques
- Efficient algorithms for Tucker decomposition via approximate matrix multiplication
- Low-rank approximation algorithm using sparse projection and its applications
- Randomized structured total-least-squares-based higher-order extended dynamic mode decomposition
This page was built for publication: Randomized LU decomposition using sparse projections
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012724)
