Perturbations of CUR Decompositions

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.

References in corpus (9)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Sparsity and Incoherence in Compressive Sampling
• Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
• Rectangular maximum-volume submatrices and their applications
• Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
• Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
• Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data
• Rectangular maximum volume and projective volume search algorithms
• CUR Low Rank Approximation of a Matrix at Sublinear Cost

Cited by in corpus (3)

• Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
• A literature survey of matrix methods for data science
• Stability of Sampling for CUR Decompositions