  The CUR matrix decomposition is an important extension of Nystr\"{o}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.
