Matrix Coherence and the Nystrom Method

Understand

The Nystrom method is an efficient technique used 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, connecting 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.