Randomized LU decomposition
From MaRDI portal
Abstract: We present a fast randomized algorithm that computes a low rank LU decomposition. Our algorithm uses random projections type techniques to efficiently compute a low rank approximation of large matrices. The randomized LU algorithm can be parallelized and further accelerated by using sparse random matrices in its projection step. Several different error bounds are proven for the algorithm approximations. To prove these bounds, recent results from random matrix theory related to subgaussian matrices are used. As an application, we also show how the algorithm can be utilized to solve problems such as the rank-deficient least squares problem. Numerical examples, which illustrate the performance of the algorithm and compare it to other decomposition methods, are presented.
Recommendations
Cites work
- 10.1162/1532443041827934
- A Supernodal Approach to Sparse Partial Pivoting
- A fast randomized algorithm for overdetermined linear least-squares regression
- A fast randomized algorithm for the approximation of matrices
- A randomized algorithm for the decomposition of matrices
- An Unsymmetric-Pattern Multifrontal Method for Sparse LU Factorization
- Average-Case Stability of Gaussian Elimination
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Compressed sensing
- Condition Numbers of Gaussian Random Matrices
- Diffusion maps
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Efficient sparse LU factorization with left-right looking strategy on shared memory multiprocessors
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Fast computation of low-rank matrix approximations
- Fast monte-carlo algorithms for finding low-rank approximations
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Improved analysis of the subsampled randomized Hadamard transform
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Low rank matrix-valued Chernoff bounds and approximate matrix multiplication
- Multiscale data sampling and function extension
- Numerical Inverting of Matrices of High Order. II
- Numerical linear algebra in the streaming model
- On the Compression of Low Rank Matrices
- On the existence and computation of rank-revealing LU factorizations
- Rang revealing QR factorizations
- Relative-Error $CUR$ Matrix Decompositions
- Smallest singular value of a random rectangular matrix
- Smallest singular value of random matrices and geometry of random polytopes
- Smallest singular value of sparse random matrices
- Spectral regularization algorithms for learning large incomplete matrices
- Strong rank revealing LU factorizations
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
Cited in
(18)- Randomized algorithms for the low-rank approximation of matrices
- Single-pass randomized QLP decomposition for low-rank approximation
- Matrix decompositions using sub-Gaussian random matrices
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- A randomized singular value decomposition for third-order oriented tensors
- Randomized LU decomposition using sparse projections
- An efficient implementation of LU decomposition in C
- Sketch-based multiplicative updating algorithms for symmetric nonnegative tensor factorizations with applications to face image clustering
- Pass-efficient randomized LU algorithms for computing low-rank matrix approximation
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
- Randomized quaternion QLP decomposition for low-rank approximation
- Randomized generalized singular value decomposition
- Single-pass randomized algorithms for LU decomposition
- The \(\mathcal{L_C}\)-structure-preserving algorithms of quaternion \(LDL^H\) decomposition and Cholesky decomposition
- An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
- Randomized algorithms for the low multilinear rank approximations of tensors
- Pass-efficient truncated UTV for low-rank approximations
This page was built for publication: Randomized LU decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1690696)
