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

TitleSpectral Gap Error Bounds for Improving CUR Matrix Decomposition and the Nystrom Method
Publication TypeConference Paper
Year of Publication2015
AuthorsAndersen, D. G., Du S. S., Mahoney M. W., Melgaard C., Wu K., & Gu M.
Other Numbers3775

The CUR matrix decomposition and therelated Nystrom method build low-rank approximations of data matrices by selecting a small number of representative rowsand columns of the data. Here, we introduce novelspectral 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 aremuch tighter than existing ones for matrices with rapid spectrum decay, and theyjustify the use of a constant amount of over-sampling relative to the rank parameterk, i.e, when the number of columns/rows is l = k + O(1). We demonstrate ouranalysis on a novel deterministic algorithm,StableCUR, which additionally eliminatesa previously unrecognized source of potential instability in CUR decompositions.While our algorithm accepts any method ofrow and column selection, we implement itwith a recent column selection scheme withstrong singular value bounds. Empirical results on various classes of real world datamatrices demonstrate that our algorithm isas effcient as, and often outperforms, competing algorithms.

Bibliographic Notes

Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AI & Statistics 2015), San Diego, California

Abbreviated Authors

D. G. Anderson, S. S. Du, M. W. Mahoney, C. Melgaard, K. Wu, and M. Gu

ICSI Research Group

Big Data

ICSI Publication Type

Article in conference proceedings