  The CUR decomposition is a factorization of a low-rank matrix obtained by
selecting certain column and row submatrices of it. We perform a thorough
investigation of what happens to such decompositions in the presence of noise.
Since CUR decompositions are non-uniquely formed, we investigate several
variants and give perturbation estimates for each in terms of the magnitude of
the noise matrix in a broad class of norms which includes all Schatten
$p$--norms. The estimates given here are qualitative and illustrate how the
choice of columns and rows affects the quality of the approximation, and
additionally we obtain new state-of-the-art bounds for some variants of CUR
approximations.
