Perturbations of CUR Decompositions

Keaton Hamm, Longxiu Huang

Abstract

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.
BibTeX
@article{hamm2019perturbations,
  author = {Keaton Hamm and Longxiu Huang},
  title = {{Perturbations of CUR Decompositions}},
  journal = {SIAM J. Matrix Anal. Appl},
  year = {2019},
  doi = {10.1137/19m128394x},
}

Loading related content...

Figure