  By exploiting the random sampling techniques, this paper derives an efficient
randomized algorithm for computing a generalized CUR decomposition, which
provides low-rank approximations of both matrices simultaneously in terms of
some of their rows and columns. For large-scale data sets that are expensive to
store and manipulate, a new variant of the discrete empirical interpolation
method known as L-DEIM, which needs much lower cost and provides a significant
acceleration in practice, is also combined with the random sampling approach to
further improve the efficiency of our algorithm. Moreover, adopting the
randomized algorithm to implement the truncation process of restricted singular
value decomposition (RSVD), combined with the L-DEIM procedure, we propose a
fast algorithm for computing an RSVD based CUR decomposition, which provides a
coordinated low-rank approximation of the three matrices in a CUR-type format
simultaneously and provides advantages over the standard CUR approximation for
some applications. We establish detailed probabilistic error analysis for the
algorithms and provide numerical results that show the promise of our
approaches.
