Singular vectors under random perturbation

Van Vu

TL;DR

This paper investigates how much the singular vectors of a large matrix change when the matrix is slightly perturbed by random noise. The authors develop new, tighter bounds for this change, particularly when the original matrix has a low rank, using techniques from high-dimensional geometry. This is crucial for understanding the stability of data analysis techniques like Principal Component Analysis (PCA) in the presence of noise.

What Problem Does This Paper Address?

In many fields, such as statistics and numerical analysis, we often work with large matrices that represent data. A fundamental task is to compute the "singular vectors" of these matrices, which are essential for techniques like Principal Component Analysis (PCA) used for dimensionality reduction and data visualization. However, real-world data is rarely perfect; it's often corrupted by noise, meaning we're working with a perturbed matrix (A + E) instead of the true matrix (A).

A critical question then arises: how much do the singular vectors of the original matrix A change when we add this noise E? Classical results, like the Davis-Kahan and Wedin theorems, provide bounds on this change. These bounds typically depend on the "gap" between consecutive singular values of A. However, these existing bounds can be overly conservative, especially when the noise is random and the underlying data has a low-rank structure (meaning the data can be well-represented by a smaller number of underlying components). This paper aims to provide sharper, more refined bounds for this scenario, offering a better understanding of how reliably we can recover the true singular vectors from noisy data.

Methods

The paper's core contribution lies in developing new theoretical bounds for the perturbation of singular vectors under random noise. The authors leverage tools from high-dimensional geometry, which is a departure from the methods used in prior classical theorems.

Key techniques include:

  • Probabilistic Analysis: The analysis heavily relies on the properties of random matrices, specifically Bernoulli random matrices (where entries are +1 or -1 with equal probability). Lemmas are presented to bound the norm of such matrices and the correlation between random noise and existing vectors.
  • Concentration Inequalities: Tools like Chernoff bounds and concentration inequalities are used to show that certain random events occur with high probability (approaching 1 as the matrix size increases). This is crucial for establishing that the derived bounds hold "almost surely."
  • Courant-Fisher Minimax Principle: This standard linear algebra principle is used to establish lower bounds on singular values.
  • e-net Lemma: This lemma from geometric measure theory is used to relate the behavior of a function on a continuous set (like a sphere) to its behavior on a discrete subset (an e-net). This is helpful in analyzing the behavior of the perturbed matrix on subspaces.

The paper introduces new theorems (Theorems 8 and 9) that provide these improved bounds, particularly for low-rank matrices and when the noise is random.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on deriving bounds for general matrices with random perturbations.

Key Insights and Ideas

  • Low Rank Matters: The paper's central insight is that the low-rank structure of a matrix significantly improves the stability of its singular vectors under random noise. This means that if the data can be explained by a small number of underlying factors, the singular vectors are more robust to noise than previously thought.
  • Random Noise is Advantageous: The random nature of the noise, when analyzed with high-dimensional geometry tools, allows for tighter bounds compared to worst-case deterministic perturbations.
  • Gap is Still Important, But Contextualized: While the gap between singular values remains a key parameter, the paper shows that for low-rank matrices with random noise, a smaller gap can still lead to good recovery of singular vectors, provided the noise level is also controlled.
  • New Geometric Approach: The use of high-dimensional geometry provides a novel perspective and allows for the derivation of sharper bounds than those obtained through purely algebraic methods.

Key Results

The paper presents several key theorems and corollaries that quantify the change in singular vectors.

  • Theorem 8 (Probabilistic sin-theorem): Provides a bound on the angle between the first singular vector of A and the first singular vector of A+E. This bound is shown to be significantly better than classical results when A has low rank and the noise is random. The bound depends on terms like $\sqrt{r \log n} / \delta$ and $\sigma_1 / \delta$, where $r$ is the rank, $n$ is the matrix dimension, $\delta$ is the gap between the first two singular values, and $\sigma_1$ is the largest singular value.
  • Theorem 9: Extends the results to bound the change in the first $k$ singular vectors. This theorem provides a recursive bound that also benefits from the low-rank assumption.
  • Improved Bounds for Low Rank: Corollaries 6 and 7 demonstrate that for low-rank matrices, the condition for good approximation of singular vectors can be relaxed from $O(\sqrt{n})$ to $O(\sqrt{r \log n})$, where $r$ is the rank.

Limitations and Future Work

  • Focus on Bernoulli Noise: While the paper mentions extensions to other noise models (Gaussian, bounded entries) in Section 5, the primary analysis and detailed proofs are for Bernoulli random matrices.
  • Low Rank Assumption: The most significant improvements are achieved under the assumption that the matrix A has low rank ($r \ll n$). The paper acknowledges that extending these results to matrices that are only "approximately" low-rank (i.e., A = A' + B where A' is low-rank and B is small) requires further work.
  • Technical Complexity: The paper notes that improving the error terms further (e.g., to $(\sigma_1)^{3/2}$) is possible but requires more technical proofs.
  • Generalization to Non-Square Matrices: The paper mentions that the analysis can be extended to rectangular matrices with nominal modifications.
  • Applications: While the paper highlights the relevance to PCA, further exploration of specific applications and empirical validation would be valuable.

Summary updated

Abstract

Computing the first few singular vectors of a large matrix is a problem that frequently comes up in statistics and numerical analysis. Given the presence of noise, exact calculation is hard to achieve, and the following problem is of importance: \vskip2mm \centerline {\it How much a small perturbation to the matrix changes the singular vectors ?} \vskip2mm Answering this question, classical theorems, such as those of Davis-Kahan and Wedin, give tight estimates for the worst-case scenario. In this paper, we show that if the perturbation (noise) is random and our matrix has low rank, then better estimates can be obtained. Our method relies on high dimensional geometry and is different from those used an earlier papers.
BibTeX
@article{vu2011singular,
  author = {Van Vu},
  title = {{Singular vectors under random perturbation}},
  journal = {Random Struct. Algorithms},
  year = {2011},
  doi = {10.1002/rsa.20367},
}
Figure