Timezone: »

A Scalable CUR Matrix Decomposition Algorithm: Lower Time Complexity and Tighter Bound
Shusen Wang · Zhihua Zhang

Mon Dec 03 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor

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.

Author Information

Shusen Wang (UC Berkeley)
Zhihua Zhang (Shanghai Jiao Tong University)

More from the Same Authors