WITHDRAWN: A Simple Approach to Optimal CUR Decomposition

MaRDI QIDQ6511767arXivFDO

Authors Haishan Ye, Yujun Li, Zhihua Zhang

Published in arXiv

Abstract: 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(mathrmnnz(A))$ optimal CUR algorithm where $A$ is a data matrix in question. We also extend our approach to the Nystr{"o}m method, obtaining a fast algorithm which runs $ildeO(n^2)$ or $O(mathrmnz(A))$

This page was built for publication: WITHDRAWN: A Simple Approach to Optimal CUR Decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6511767)