Spectral Gap Error Bounds for Improving CUR Matrix Decomposition and the Nystrom Method

Abstract

The CUR matrix decomposition and the related Nyström method build low-rank approximations of data matrices by select-ing a small number of representative rows and columns of the data. Here, we intro-duce 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 matri-ces with rapid spectrum decay, and they justify the use of a constant amount of over-sampling relative to the rank parameter k, i.e, when the number of columns/rows is ` = k + O(1). We demonstrate our analysis on a novel deterministic algorithm, StableCUR, which additionally eliminates a previously unrecognized source of po-tential 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 re-sults on various classes of real world data matrices demonstrate that our algorithm is as efficient as, and often outperforms, com-peting algorithms.