  The Nystrom method is an efficient technique to speed up large-scale learning
applications by generating low-rank approximations. Crucial to the performance
of this technique is the assumption that a matrix can be well approximated by
working exclusively with a subset of its columns. In this work we relate this
assumption to the concept of matrix coherence and connect matrix coherence to
the performance of the Nystrom method. Making use of related work in the
compressed sensing and the matrix completion literature, we derive novel
coherence-based bounds for the Nystrom method in the low-rank setting. We then
present empirical results that corroborate these theoretical bounds. Finally,
we present more general empirical results for the full-rank setting that
convincingly demonstrate the ability of matrix coherence to measure the degree
to which information can be extracted from a subset of columns.
