We discuss a new class of efficient randomized algorithms for spectrum-revealing LU,Cholesky and QR factorizations.Our algorithms are much more efficient than other approaches for low-rank matrix approximation and we develop a new set of approximation error bounds that suggest that our matrix factorizations are also at least as effective as other low-rank approximation methods.