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 nonuniquely 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.
Topics & Concepts
MathematicsFactorizationMatrix decompositionRowBlock matrixRow and column spacesRank (graph theory)Perturbation (astronomy)Column (typography)Matrix (chemical analysis)Applied mathematicsPure mathematicsAlgebra over a fieldCombinatoricsAlgorithmEigenvalues and eigenvectorsComputer scienceGeometryComposite materialQuantum mechanicsDatabaseMaterials scienceConnection (principal bundle)PhysicsSparse and Compressive Sensing TechniquesTensor decomposition and applicationsBlind Source Separation Techniques