# Matrix Coherence And The Nystr¨Om Method

## Ameet Talwalkar

ameet@cims.nyu.edu Courant Institute of Mathematical Sciences New York, NY

## Abstract Afshin Rostamizadeh

rostami@cims.nyu.edu Courant Institute of Mathematical Sciences New York, NY
arXiv:1004.2008v1 [cs.AI] 12 Apr 2010 The Nystr¨om 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 Nystr¨om method. Making use of related work in the compressed sensing and the matrix completion literature, we derive novel coherence-based bounds for the Nystr¨om 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.

## 1 Introduction

Modern problems in computer vision, natural language processing, computational biology and other areas often involve datasets containing millions of training instances. However, several standard methods in machine learning, such as spectral clustering (Ng et al.**, 2001), manifold learning techniques**
(de Silva and Tenenbaum, 2003; Sch¨olkopf **et al.**, 1998), kernel ridge regression (Saunders et al.**, 1998)**
or other kernel-based algorithms do not scale to such orders of magnitude. In fact, even storage of the matrices associated with these datasets can be problematic since they are often not sparse and hence the number of entries is extremely large. As shown by Williams and Seeger (2000), the Nystr¨om method provides an attractive solution when working with large-scale datasets by operating on only a small part of the original matrix to generate a low-rank approximation. The Nystr¨om method has been shown to work well in practice for various applications ranging from manifold learning to image segmentation
(Fowlkes et al., 2004; Platt, 2004; Talwalkar **et al.**, 2008; Zhang et al.**, 2008).**
The effectiveness of the Nystr¨om method hinges on two key assumptions on the input matrix, G**. First,** we assume that a low-rank approximation to G **can be** effective for the task at hand. This assumption is often true empirically as evidenced by the widespread use of singular value decomposition (SVD) and principal component analysis (PCA) in practical applications. As expected, the Nystr¨om method is not appropriate in cases where this assumption does not hold, which explains its poor performance in the experimental results of Fergus et al. **(2009). Previous work analyzing the performance of the Nystr¨om method incorporates this low-rank assumption into theoretical guarantees by comparing the Nystr¨om approximation to the**
'best' low-rank approximation, i.e., the approximation constructed from the top singular values and singular vectors of G **(see Section 2 for further discussion)**
(Drineas and Mahoney, 2005; Kumar et al.**, 2009a).**
The second crucial assumption of the Nystr¨om method involves the sampling-based nature of the algorithm, namely that an accurate low-rank approximation can be generated exclusively from information extracted from a small subset of l ≪ n columns of G**. This**
assumption is not generally true for all matrices. For instance, consider the extreme case of the n×n **matrix**
described below:

G =    ~e1 . . . ~er~0 . . . ~0    , (1)