2015/11/05 by Haishan Ye, Yujun Li, Ye, Haishan +3
Engineering · Earth and Planetary Sciences · #Sparse and Compressive Sensing Techniques #Seismic Imaging and Inversion Techniques #Geophysical Methods and Applications
paper · pdf · doi:10.48550/arxiv.1511.01598
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(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 O(n2) or O(\nnz(\A))