Randomized LU Decomposition

2013/10/27 by Gil Shabat, Shabat, Gil, Yaniv Shmueli +5 · 1 citation
Computer Science · Engineering · #Blind Source Separation Techniques #FOS: Mathematics #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1310.7202

openalex publication_date 2013/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries

Cited by

• Algorithm 971

Related

• Pass-Efficient Randomized LU Algorithms for Computing Low-Rank Matrix Approximation
• Randomized LU Decomposition Using Sparse Projections
• An improved analysis and unified perspective on deterministic and randomized low rank matrix approximations
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Randomized methods for matrix computations