  Interpolative and CUR decompositions involve "natural bases" of row and
column subsets, or skeletons, of a given matrix that approximately span its row
and column spaces. These low-rank decompositions preserve properties such as
sparsity or non-negativity, and are easily interpretable in the context of the
original data. For large-scale problems, randomized sketching to sample the row
or column spaces with a random matrix can serve as an effective initial step in
skeleton selection to reduce computational cost. A by now well-established
approach has been to extract a randomized sketch, followed by column-pivoted QR
CPQR) on the sketch matrix. This manuscript describes an alternative approach
where CPQR is replaced by LU with partial pivoting (LUPP). While LUPP by itself
is not rank-revealing, it is demonstrated that when used in a randomized
setting, LUPP not only reveals the numerical rank, but also allows the
estimation of the residual error as the factorization is built. The resulting
algorithm is both adaptive and parallelizable, and attains much higher
practical speed due to the lower communication requirements of LUPP over CPQR.
The method has been implemented for both CPUs and GPUs, and the resulting
software has been made publicly available.
