  Selecting a good column (or row) subset of massive data matrices has found
many applications in data analysis and machine learning. We propose a new
adaptive sampling algorithm that can be used to improve any relative-error
column selection algorithm. Our algorithm delivers a tighter theoretical bound
on the approximation error which we also demonstrate empirically using two well
known relative-error column subset selection algorithms. Our experimental
results on synthetic and real-world data show that our algorithm outperforms
non-adaptive sampling as well as prior adaptive sampling approaches.
