Spectral Gap Error Bounds for Improving CUR Matrix Decomposition and the Nystrom Method
Title | Spectral Gap Error Bounds for Improving CUR Matrix Decomposition and the Nystrom Method |
Publication Type | Conference Paper |
Year of Publication | 2015 |
Authors | Andersen, D. G., Du S. S., Mahoney M., Melgaard C., Wu K., & Gu M. |
Other Numbers | 3775 |
Abstract | 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. |
URL | https://www.icsi.berkeley.edu/pubs/initiatives/spectralgap15.pdf |
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 |