A Scalable CUR Matrix Decomposition Algorithm: Lower Time Complexity and Tighter Bound
This work provides an incremental advancement in matrix approximation techniques, benefiting researchers and practitioners in data analysis and machine learning by offering more efficient and accurate decomposition methods.
The authors tackled the problem of improving CUR matrix decomposition by developing a randomized algorithm that achieves a tighter theoretical bound and lower time complexity, with experiments on real-world datasets showing significant improvements over existing methods.
The CUR matrix decomposition is an important extension of Nyström approximation to a general matrix. It approximates any data matrix in terms of a small number of its columns and rows. In this paper we propose a novel randomized CUR algorithm with an expected relative-error bound. The proposed algorithm has the advantages over the existing relative-error CUR algorithms that it possesses tighter theoretical bound and lower time complexity, and that it can avoid maintaining the whole data matrix in main memory. Finally, experiments on several real-world datasets demonstrate significant improvement over the existing relative-error algorithms.