Revisiting CUR Perturbation Analysis: A Local Tangent-Space Expansion
Provides a theoretical understanding of CUR perturbation behavior for matrix approximation, relevant to practitioners using CUR decompositions in large-scale data analysis.
This work develops a local tangent-space expansion for rank-truncated CUR decompositions, showing that the local recovery error depends on a sampling-induced oblique tangent projector rather than the full perturbation norm. Numerical experiments confirm predicted first- and second-order local rates.
CUR decompositions approximate a matrix using selected columns, rows, and their intersection. Classical CUR theory provides exactness results for low-rank matrices and perturbation bounds controlled by the size of the noise. In this work we develop a local perturbation expansion for a fixed-index rank-truncated CUR map near an admissible rank-\(r\) matrix. We show that the Fréchet derivative of the rank-truncated CUR map is a sampling-induced oblique tangent-space projector determined by the selected rows and columns. Consequently, the local recovery error for an underlying low-rank matrix is governed not by the full perturbation norm alone, but by the image of the perturbation under this sampling-induced tangent projector. In particular, perturbations that are invisible to the selected rows and columns are removed to first order. We compare this behavior with the classical local expansion of the rank-\(r\) SVD truncation. SVD removes orthogonal-normal perturbations to first order, whereas rank-truncated CUR removes perturbations in the kernel of the sampling-induced oblique tangent projector. Numerical experiments illustrate these regimes and confirm the predicted first- and second-order local rates.