The spectral norm error of the naive Nystrom extension

Introduction

Nyström extensions are a class of algorithms that quickly form low-rank approximations to positive semidefinite (PSD) matrices by sampling from their columns. We consider the naïve Nyström extension, a particular scheme in which the columns are sampled uniformly without replacement. By exploiting a natural connection between Nyström extensions and the column subset selection problem, we find the first relative-error spectral norm guarantees for the naïve Nyström extension.

Perhaps surprisingly, given that one uses no information about the matrix itself to make the column selections, the naïve Nyström extension is effective in practice. Because of its data agnosticism and empirical accuracy, the naïve Nyström extension is a natural choice for any application where one wishes to avoid the cost of examining (or even constructing) the entire dataset before approximation.

The naïve Nyström extension has proven to be particularly useful in image-processing applications, which typically involve computations with large dense matrices [FBCM04, WDT+09, BF]. In spectral image segmentation, for example, one constructs a matrix of pairwise pixel affinities by comparing neighborhoods of each pair of pixels. Several leading eigenvectors of this matrix are then used to segment the image. The affinity matrix of an $N\times N$ image has dimension $N^{2}\times N^{2},$ so it is challenging to construct and hold the affinity matrix in memory even for images of a moderate size. Similarly, the density and size of the affinity matrix makes it challenging to compute the leading eigenvectors. [FBCM04] proposes using the naïve Nyström extension to approximate the eigenvectors of the affinity matrix. Doing so allows one to work with much larger images, because it is only necessary to compute a fraction of the columns of the affinity matrix.

2. Structure of the Nyström extension

The manner in which the columns are sampled and $\bm{W}^{\dagger}$ is calculated or approximated determines the type of the Nyström extension. Various sampling schemes have been proposed, ranging from the fast and simple naïve scheme in which the columns are selected uniformly at random without replacement to more sophisticated and calculation-intensive schemes that involve sampling from a distribution determined by the determinants of principal submatrices of $\bm{A}$ [BW09]. In practice the naïve scheme represents a favorable trade-off between speed and accuracy [KMT09b].

3. Nyström approximation of invariant subspaces

In many applications, including the image-processing example taken from [FBCM04], the Nyström extension is used to obtain approximations to the dominant invariant subspace of a PSD matrix $\bm{A},$ rather than a low-rank approximation [HM]. Through the Davis–Kahan sin$\Theta$ theorem, the spectral norm approximation error provides information on the quality of the approximate invariant subspace obtained via Nyström extensions [Bha97, Section VII.3].

Assume that we have a relative-error spectral norm bound of the form

for some $j\geq k.$ Then equation (1) becomes

This paper presents a simple framework for the analysis of Nyström schemes that yields a state-of-the-art spectral norm error bound in the case of the naïve Nyström extension scheme. Specifically, it generalizes the coherence-based exact recovery result in [TR10] to also guarantee small relative error in the case of a matrix with a fast-decaying spectrum. This is the first truly relative-error spectral norm bound available for any Nyström extension method. When the eigengap $\lambda_{k}(\bm{A})-\lambda_{k+1}(\bm{A})$ is sufficiently large, our result sanctions the use of the naïve Nyström extension for the approximation of the dominant $k$-dimensional invariant subspace of $\bm{A}.$

4. Our relative-error spectral norm bound

Corollary 1 is a condensed version of our main result, Theorem 2, and uses the notion of coherence to provide a bound on the error of the naïve Nyström extension.

5. Relevant literature

Williams and Seeger introduce the Nyström extension in [WS01], based upon a similar method used in numerical integral equation solvers, as a heuristic method for efficiently approximating the eigendecomposition of kernel matrices. In this seminal work, only an empirical analysis of the approximation error is offered. Drineas and Mahoney provide the first rigorous analysis of a Nyström extension in [DM05]; in the scheme they consider, columns are sampled with probability proportional to the square of the diagonal entries of $\bm{A}$. In addition to probabilistic schemes, many adaptive sampling schemes have been proposed. These attempt to progressively choose the columns to decrease the approximation error. For an introduction to this body of literature, we refer the interested reader to the discussion in [FGK11].

Kumar, Mohri, and Talwalkar attempt the first analysis of the naïve Nyström extension in [KMT09b], resulting in bounds for the Frobenius norm error. Their analysis proceeds by bounding the expectation and variance of the error then applying a concentration of measure argument. A simplified yet representative statement of their bound is that

Of the works mentioned, only [LKL10] provides a bound on the spectral error of the Nyström method for $\bm{A}$ of arbitrary rank. Unfortunately, the quantity $\max_{i}(\bm{A})_{ii}$ is, for a general $\bm{A}\succeq 0,$ bounded only by $\lambda_{1}(\bm{A}).$ Thus equation (2) does not provide a relative-error bound. In fact, the spectral norm error bound provided in this paper is always tighter than the bound provided in [LKL10], for any choice of $p$ and $q.$

Our work presents an intuitive and simple approach to the analysis of Nyström extensions through their connection to the randomized column subset selection problem. This allows us to obtain the first truly relative-error guarantee on the spectral norm error. This paper analyzes the naïve sampling scheme but we believe that the framework given is flexible enough to be fruitfully applied to the analysis of other Nyström extension schemes including, in particular, the large-scale variant introduced in [LKL10].

6. Outline

In Section 2 we introduce our notation and review some algebraic preliminaries. In Section 3 we establish a connection between the Nyström extension procedure and the column subset selection problem. We exploit this connection and a result from [HMT11] to provide a general error bound for any Nyström extension scheme. In Section 4 we specialize this result to the case of the naïve Nyström extension.

Notation

We work exclusively with real matrices and order the eigenvalues of a PSD matrix $\bm{A}$ so that $\lambda_{1}(\bm{A})\geq\lambda_{2}(\bm{A})\geq\cdots\geq\lambda_{n}(\bm{A}).$ Each PSD matrix $\bm{A}$ has a unique square root $\bm{A}^{1/2}$ that is also positive-semidefinite, has the same eigenspaces as $\bm{A},$ and satisfies \bm{A}=\big{(}\bm{A}^{1/2}\big{)}^{2}.

The projection onto the column space of a matrix $\bm{M}$ is written $\bm{P}_{\bm{M}}$ and satisfies

The notation $(\bm{x})_{j}$ refers to the $j$th entry of the vector $\bm{x},$ and $(\bm{M})_{i}$ refers to the $i$th column of the matrix $\bm{M}.$ Likewise, $(\bm{M})_{ij}$ refers to the $(i,j)$ entry of $\bm{M}.$

From the last equality, we see that the coherence is in fact an intrinsic property of the subspace spanned by $\bm{U}.$ Thus we refer to the coherence of a subspace without first choosing a particular orthogonal basis $\bm{U}.$

The connection to the column subset selection problem

In this section we establish a fruitful connection between the performance of the Nyström extension and the performance of randomized column subset selection.

Given a matrix $\bm{M}$, the goal of column selection is to choose a small but informative subset $\bm{C}$ of the columns of $\bm{M}$ so that, after approximating $\bm{M}$ with the matrix obtained by projecting $\bm{M}$ onto the span of $\bm{C},$ the residual $(\bm{I}-\bm{P}_{\bm{C}})\bm{M}$ is small in some norm. In randomized column subset selection, the columns $\bm{C}$ are choosen randomly, either uniformly or according to some data-dependent distribution. Column subset selection has important applications in statistical data analysis and has been investigated by both the numerical linear algebra and the theoretical computer science communities. For an introduction to the column subset selection literature, biased towards approaches involving randomization, we refer the interested reader to the surveys [Maha, Mahb].

We use the following partitioning of the eigenvalue decomposition of $\bm{A}$ to state our results:

The columns of $\bm{U}_{1}$ and $\bm{U}_{2}$ respectively span a dominant $k$-dimensional invariant subspace of $\bm{A}$ and the corresponding bottom $(n-k)$-dimensional invariant subspace of $\bm{A}.$ The interaction of the column sampling matrix $\bm{S}$ with the invariant subspaces spanned by $\bm{U}_{1}$ and $\bm{U}_{2}$ is captured by the matrices

Assume $\bm{\Omega}_{1}$ has full row rank. Then the spectral approximation error of the Nyström extension of $\bm{A}$ using $\bm{S}$ as the column sampling matrix satisfies

Prior analyses of Nyström extensions have used the Cholesky decomposition of $\bm{A}.$ By instead using the square-root, Theorem 5 establishes an equivalence between the column subset selection problem and the Nyström extension procedure and gives a deterministic relative-error bound on the performance of Nyström extensions.

To establish Theorem 5, we use the following bound on the error incurred by projecting a matrix onto a random subspace of its range ([HMT11, Theorem 9.1]).

Let $\bm{U}_{1}$ and $\bm{U}_{2}$ be matrices with orthogonal columns spanning, respectively, a dominant $k$-dimensional invariant subspace of $\bm{M}$ and the corresponding bottom $(n-k)$-dimensional invariant subspace of $\bm{M}.$ Let $\bm{\Sigma}_{2}$ be the diagonal matrix of eigenvalues corresponding to the bottom $(n-k)$-dimensional invariant subspace of $\bm{M}.$

We write the Nyström extension in terms of the square root of $\bm{A}$ and a projection onto the space spanned by $\bm{A}^{1/2}\bm{S}:$

It follows that the spectral error of the Nyström extension satisfies

The second equality holds because of the idempotency of projections. The third follows from the fact that $\|\bm{A}\bm{A}^{t}\|_{2}=\|\bm{A}\|_{2}^{2}$ for any matrix $\bm{A}.$ Partition $\bm{A}$ as in equation (3). Equation (5) now follows immediately from Proposition 1 with $\bm{M}=\bm{A}^{1/2}.$ ∎

Error bounds for naïve Nyström extension

In this section, we provide a bound on the spectral norm approximation error of naïve Nyström extensions. For convenience, we recall the following partitioning of the eigenvalue decomposition of a PSD matrix of size $n$:

where the columns of $\bm{U}_{1}$ and $\bm{U}_{2}$ respectively span a dominant $k$-dimensional invariant subspace of $\bm{A}$ and the corresponding bottom $(n-k)$-dimensional invariant subspace of $\bm{A}.$ We also recall the matrices

that capture the interaction of the column sampling operation with the invariant subspaces of $\bm{A}.$ Theorem 2 establishes that, if the spectrum of $\bm{A}$ decays sufficiently and an appropriate number of columns are sampled, then the error incurred by the naïve Nyström extension process is small.

Let $\bm{A}$ be a PSD matrix of size $n.$ Given an integer $k\leq n,$ partition $\bm{A}$ as in equation (6). Let $\tau$ denote the coherence of $\bm{U}_{1},$

Fix a failure probability $\delta\in(0,1).$ For any $\varepsilon\in(0,1),$ if

columns of $\bm{A}$ are chosen uniformly at random and used to form a Nyström extension, the spectral norm error of the approximation satisfies

The coherence of $\bm{U}_{1}$ is a measure of how much comparative influence the individual columns of $\bm{A}$ have over the dominant $k$-dimensional invariant subspace of $\bm{A}$ spanned by $\bm{U}_{1}$: if $\tau$ is small, then all columns have essentially the same influence; if $\tau$ is large, then it is possible that there is a single column in $\bm{A}$ which alone determines one of the top $k$ eigenvectors of $\bm{A}.$

We might ask where attempts at sharpening the analysis of the naïve Nyström extension should be aimed: toward more refined linear algebra bounds on column selection (Proposition 1), or toward a deeper analysis of the randomness (Theorem 2)?

To obtain Theorem 2, we use Theorem 5 in conjunction with a bound on \big{\|}\bm{\Omega}_{1}^{\dagger}\big{\|}_{2}^{2} provided by the following lemma.

Let $\bm{U}$ be an $n\times k$ matrix with orthonormal columns. Take $\tau$ to be the coherence of $\bm{U},$

Then with probability exceeding $1-\delta$, the matrix $\bm{U}^{t}\bm{S}$ has full row rank and satisfies

We now proceed with the proof of Theorem 2.

with at least the same probability. To obtain the second inequality, we used the fact that \big{\|}\bm{\Omega}_{2}\big{\|}_{2}\leq\big{\|}\bm{U}_{2}\big{\|}_{2}\big{\|}\bm{\Omega}\big{\|}_{2}\leq 1.

One potential source of difficulty in the proof of Lemma 1 is the fact that the columns are sampled without replacement, which introduces dependencies among the entries of the sampling matrix $\bm{S}.$ The following matrix Chernoff bound, a standard simplification of the lower Chernoff bound developed in [Tro11, Theorem 2.2], allows us to gloss over these dependencies.

Let $\mathcal{X}$ be a finite set of PSD matrices with dimension $k,$ and suppose that

Note that $\bm{U}^{t}\bm{S}$ has full row rank if $\lambda_{k}(\bm{U}^{t}\bm{S}\bm{S}^{t}\bm{U})>0.$ Furthermore,

Thus to obtain both conclusions of the lemma, it is sufficient to verify that

We apply Proposition 2 to bound the probability that this inequality is not satisfied. Let $\bm{u}_{i}$ denote the $i$th column of $\bm{U}^{t}.$ Then

where the $\bm{X}_{i}$ are chosen uniformly at random, without replacement, from the set $\mathcal{X}=\{\bm{u}_{i}\bm{u}_{i}^{t}\}_{i=1,\ldots,n}.$ Clearly

with probability greater than $1-\delta$, so we set

References