  The CUR decomposition is a technique for low-rank approximation that selects
small subsets of the columns and rows of a given matrix to use as bases for its
column and rowspaces. It has recently attracted much interest, as it has
several advantages over traditional low rank decompositions based on
orthonormal bases. These include the preservation of properties such as
sparsity or non-negativity, the ability to interpret data, and reduced storage
requirements. The problem of finding the skeleton sets that minimize the norm
of the residual error is known to be NP-hard, but classical pivoting schemes
such as column pivoted QR work tend to work well in practice. When combined
with randomized dimension reduction techniques, classical pivoting based
methods become particularly effective, and have proven capable of very rapidly
computing approximate CUR decompositions of large, potentially sparse,
matrices. Another class of popular algorithms for computing CUR de-compositions
are based on drawing the columns and rows randomly from the full index sets,
using specialized probability distributions based on leverage scores. Such
sampling based techniques are particularly appealing for very large scale
problems, and are well supported by theoretical performance guarantees. This
manuscript provides a comparative study of the various randomized algorithms
for computing CUR decompositions that have recently been proposed.
Additionally, it proposes some modifications and simplifications to the
existing algorithms that leads to faster execution times.
