Matrix Coherence and the Nystrom Method

Details Matrix Coherence and the Nystrom Method Matrix Coherence and the Nystrom Method

2010-04-12

arxiv.org/abs/1004.2008v1

Computer Science

Artificial Intelligence

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Matrix Coherence and the Nystrom Method does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Matrix Coherence and the Nystrom Method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matrix Coherence and the Nystrom Method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-263147