  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.
