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

The CUR matrix decomposition and the related Nystrom 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 ecient as, and often outperforms, com- peting algorithms.