Spectral Gap Error Bounds for Improving CUR Matrix Decomposition and the Nyström Method

David G. Anderson, Simon Du, Michael W. Mahoney, Christopher Melgaard, Kunming Wu, Ming GuAISTATS 2015 · OpenReview

Abstract

The CUR matrix decomposition and the related Nyström method build low-rank approximations of data matrices by selecting a small number of representative rows and columns of the data. Here, we introduce novel spectral gap error bounds that judiciously exploit the potentially rapid spectrum decay in the input matrix, a most common occurrence in machine learning and data analysis. Our error bounds are much tighter than existing ones for matrices with rapid spectrum decay, and they justify the use of a constant amount of oversampling relative to the rank parameter k, i.e, when the number of columns/rows is $\ell=k+ O(1)$. We demonstrate our analysis on a novel deterministic algorithm, StableCUR, which additionally eliminates a previously unrecognized source of potential instability in CUR decompositions. While our algorithm accepts any method of row and column selection, we implement it with a recent column selection scheme with strong singular value bounds. Empirical results on various classes of real world data matrices demonstrate that our algorithm is as efficient as and often outperforms competing algorithms.

Introduction

In modern data science, low-rank approximations are essential for managing massive datasets. While Principal Component Analysis (PCA) is the standard approach, it produces "principal components" that are dense linear combinations of all original features, often making them difficult to interpret and expensive to store.

CUR decomposition offers a compelling alternative by approximating a matrix using a small subset of its actual rows and columns. This approach preserves the sparsity of the original data and ensures that the resulting components are physically meaningful (e.g., specific genes in a genomic study). Despite these advantages, CUR decomposition has historically faced two significant challenges: the theoretical requirement for substantial "oversampling" to achieve accuracy, and inherent numerical instability in standard computation methods.

The Spectral Gap and Constant Oversampling

A major contribution of this work is the derivation of new "spectral gap" error bounds. Previous theoretical frameworks suggested that to achieve a target rank $k$, one needed to sample significantly more than $k$ rows or columns. However, empirical practice often showed that sampling just a few more than $k$ (constant oversampling) worked surprisingly well.

Singular value decay profiles: Fast decay (blue) vs Slow decay (red).

By incorporating the rate of decay of a matrix's singular values into the error analysis, we demonstrate that a significant "gap" between the $k$-th and $(p+1)$-th singular values drastically reduces approximation error. As shown in Figure 1, real-world data often exhibits rapid singular value decay. Our bounds mathematically justify why constant oversampling is highly effective for such structured data, bridging the gap between theory and practice.

Addressing Numerical Instability: The StableCUR Algorithm

Beyond theoretical bounds, we identify and solve a critical numerical issue in CUR implementations. The standard "naive" method for calculating the middle matrix ($U$) in a CUR decomposition involves pseudo-inverses that can become ill-conditioned as more samples are added, leading to explosive error growth.

Numerical stability comparison: Naive CUR vs StableCUR.

To resolve this, we propose the StableCUR algorithm. Instead of the naive approach, StableCUR utilizes QR factorizations of the sampled column ($C$) and row ($R$) matrices. By projecting the original matrix into the orthogonal spaces defined by these factors and performing an SVD on a smaller core matrix, we ensure numerical robustness. Figure 2 illustrates this contrast: while the error of Naive CUR explodes as the number of columns increases, StableCUR remains stable and accurate.

Experimental Evaluation

We evaluated StableCUR across diverse datasets, including Gaussian RBF Kernel matrices derived from the Abalone dataset and sparse "bag-of-words" data from the Dexter text classification set.

Key results include:

  • Near-Optimality: For matrices with rapid decay, StableCUR's error is nearly identical to the best possible theoretical low-rank approximation (the truncated SVD), even with minimal oversampling.
  • Efficiency: When combined with deterministic Unweighted Column Selection (UCS), StableCUR matches the efficiency of state-of-the-art randomized algorithms while often providing superior accuracy.

Conclusion

This research provides a more robust theoretical and practical foundation for CUR decompositions. By leveraging spectral gaps, we justify the efficiency of constant oversampling, and through the StableCUR algorithm, we provide a numerically sound method for large-scale data analysis. Future work may involve extending these gap-dependent bounds to higher-dimensional tensors and further optimizing selection complexity for massive-scale matrices.

Summary updated

Abstract

The CUR matrix decomposition and the related Nyström method build low-rank approximations of data matrices by selecting a small number of representative rows and columns of the data. Here, we introduce novel \emphspectral gap error bounds that judiciously exploit the potentially rapid spectrum decay in the input matrix, a most common occurrence in machine learning and data analysis. Our error bounds are much tighter than existing ones for matrices with rapid spectrum decay, and they justify the use of a constant amount of oversampling relative to the rank parameter k, i.e, when the number of columns/rows is \ell=k+ O(1). We demonstrate our analysis on a novel deterministic algorithm, \emphStableCUR, which additionally eliminates a previously unrecognized source of potential instability in CUR decompositions. While our algorithm accepts any method of row and column selection, we implement it with a recent column selection scheme with strong singular value bounds. Empirical results on various classes of real world data matrices demonstrate that our algorithm is as efficient as and often outperforms competing algorithms.
BibTeX
@inproceedings{anderson2015spectral,
  author = {David G. Anderson and Simon Du and Michael W. Mahoney and Christopher Melgaard and Kunming Wu and Ming Gu},
  title = {{Spectral Gap Error Bounds for Improving CUR Matrix Decomposition and the Nyström Method}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
  url = {https://openreview.net/forum?id=XGnP_x93QRy},
}
Figure