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 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
- A Supernodal Approach to Sparse Partial Pivoting
- 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 computation of low-rank matrix approximations
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- 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
(25)- Randomized LU decomposition using sparse projections
- Single-pass randomized QLP decomposition for low-rank approximation
- Randomized quaternion QLP decomposition for low-rank approximation
- Randomized algorithms for the low multilinear rank approximations of tensors
- Single-pass randomized algorithms for LU decomposition
- Randomized generalized singular value decomposition
- A randomized singular value decomposition for third-order oriented tensors
- Randomized algorithms for the low-rank approximation of matrices
- An efficient implementation of LU decomposition in C
- Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
- Matrix decompositions using sub-Gaussian random matrices
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Pass-efficient randomized LU algorithms for computing low-rank matrix approximation
- 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
- Pass-efficient truncated UTV for low-rank approximations
- Sketch-based multiplicative updating algorithms for symmetric nonnegative tensor factorizations with applications to face image clustering
- 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
- LU decomposition and generalized Autoone-Takagi decomposition of dual matrices and their applications
- Efficient algorithms for Tucker decomposition via approximate matrix multiplication
- Low-rank approximation algorithm using sparse projection and its applications
- Efficient randomized algorithms for fixed precision problem of approximate Tucker decomposition
- Randomized structured total-least-squares-based higher-order extended dynamic mode decomposition
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)
