where ~eiis the ith column of the n dimensional identity matrix and ~0 is the n **dimensional zero vector.**
Although this matrix has rank r**, it nonetheless cannot be well approximated by a random subset of** l columns unless this subset includes e1, . . . , er**. In**
order to account for such pathological cases, previous theoretical bounds relied on sampling columns of G **from a non-uniform distribution weighted precisely by the magnitude of the diagonal elements of**
G **(Belabbas and Wolfe, 2009; Drineas and Mahoney,** 2005). Indeed, these bounds give better guarantees for pathological cases. However, in practice, when working with real-world datasets, uniform sampling is more commonly used, e.g., Fowlkes et al. **(2004); Platt** (2004); Talwalkar et al. **(2008); Williams and Seeger**
(2000), since diagonal sampling is more expensive and does not typically outperform uniform sampling
(Kumar et al.**, 2009c). Hence the diagonal sampling**
bounds are not applicable in this setting. Furthermore, these bounds are typically loose for matrices in which the diagonal entries of the matrix are roughly of the same magnitude, as in the case of all kernel matrices generated from RBF kernels, for which the Nystr¨om has been noted to work particularly well (Williams and Seeger, 2000). In this work, we propose to characterize the ability to extract information from a small subset of l **columns**
using the notion of matrix coherence**, an alternative**
data-dependent measurement which we believe to be intrinsically related to the algorithm's perform. Coherence measures the extent to which the singular vectors of a matrix are correlated with the standard basis.

Intuitively, if we work with sufficiently incoherent matrices, then we avoid pathological cases such as the one presented (1). Recent work on compressed sensing and matrix completion, which also involve sampling-based approximations, have relied heavily on coherence assumptions (Cand`es and Romberg, 2007; Cand`es **et al.**,
2006; Donoho, 2006).

The main contribution of this work is the connection that is made between matrix coherence and the Nystr¨om method. Making use of related work in the compressed sensing and the matrix completion literature, we give a more refined analysis of this algorithm as a function of matrix coherence, presenting a novel preliminary theoretical bound for the Nystr¨om method. We also present extensive empirical results that strongly relate coherence to the performance of the Nystr¨om method. The remainder of the paper is organized as follows. Section 2 introduces basic definitions of coherence and gives a brief presentation of the Nystr¨om method. In Section 3 we present our novel bound for the Nystr¨om method under low-rank, low-coherence assumptions.

Section 4 presents extensive empirical studies that support our bound and illustrate a similar connection between matrix coherence and the performance of the Nystr¨om method for full-rank matrices. Our empirical results also show that incoherence assumptions are valid for several datasets derived from real-world applications.

## 2 Preliminaries

Let G ∈ R
n×n **be a symmetric positive semidefinite**
(SPSD) matrix. SPSD matrices, such as Gram or kernel matrices, often appear in the context of machine learning. For any Gram matrix, there exists an N and X ∈ R
N×n such that G = X⊤X. We define X(j), j = 1 . . . n, as the j**th column vector of** X
and X(i), i = 1 . . . N, as the ith row vector of X**, and**
denote by k·k the ℓ2 **norm of a vector. Using singular value decomposition (SVD), the Gram matrix**
can be written as G = V ΣV
⊤, where V is orthonormal and Σ = diag(σ1, . . . , σn**) is a real diagonal matrix with diagonal entries sorted in decreasing order.**
For r = rank(G), the pseudo-inverse of G **is defined**
as G+ =Pr t=1 σ
−1 t V
(t)V
(t)⊤**. Further, for** k ≤ r, Gk =Pk t=1 σtV
(t)V
(t)⊤is the 'best' rank-k approximation to G, or the rank-k matrix with minimal k·kF
distance to G, where k·kF **denotes the Frobenius norm**
of a matrix.

## 2.1 Nystr¨Om Method

The Nystr¨om method was presented in Williams and Seeger (2000) to speed up the performance of kernel machines. This is done by generating low-rank approximations of G **using a**
subset of the columns of the matrix. Suppose we randomly sample l ≪ n columns of G **uniformly with** replacement, and let C be the n × l **matrix of these**
sampled columns. Then, without loss of generality, we can rearrange the columns and rows of G **based**
on this sampling and define X = [X1 X2**] where**
X1 ∈ R
N×l**, such that**

$$G=X^{\top}X=\left[\begin{array}{cc}W&X_{1}^{\top}X_{2}\\ X_{2}^{\top}X_{1}&X_{2}^{\top}X_{2}\end{array}\right]\tag{2}$$ $$\mbox{and}\quad C=\left[\begin{array}{cc}W\\ X_{2}^{\top}X_{1}\end{array}\right],\tag{3}$$  where $W=X_{1}^{\top}X_{1}$. The Nystrom approximation is 
(2)  $\binom{2}{3}$  . 
now defined as:
$$G\approx\tilde{G}=C W^{+}C^{\top}.$$
$$(4)$$

The Frobenius distance between G and Ge, kG − G˜kF ,
is one standard measurement of the accuracy of the