A Simple Approach to Optimal CUR Decomposition
This work provides a more efficient and simpler algorithm for optimal CUR decomposition, benefiting practitioners in matrix approximation and large-scale data analysis.
The paper proposes a simpler optimal CUR decomposition and near-optimal column reconstruction method using only leverage score sampling, eliminating the need for BSS and adaptive sampling. It achieves the first O(nnz(A)) optimal CUR algorithm and extends to the Nyström method with O(n^2) or O(nnz(A)) runtime.
Prior optimal CUR decomposition and near optimal column reconstruction methods have been established by combining BSS sampling and adaptive sampling. In this paper, we propose a new approach to the optimal CUR decomposition and near optimal column reconstruction by just using leverage score sampling. In our approach, both the BSS sampling and adaptive sampling are not needed. Moreover, our approach is the first $O(\mathrm{nnz}(\A))$ optimal CUR algorithm where $\A$ is a data matrix in question. We also extend our approach to the Nystr{ö}m method, obtaining a fast algorithm which runs $\tilde{O}(n^{2})$ or $O(\mathrm{\nnz}(\A))$