---
kind: concept
slug: spectral-methods
title: Spectral methods
summary: >-
  Estimate hidden structure from the leading eigen- or singular vectors of a matrix built from data. A monograph gives perturbation bounds for denoising, PCA, SBM clustering, ranking, phase retrieval and matrix and tensor completion. Also covered: spectral matching for point-cloud outliers, spectral initialisation of one-hidden-layer nets, and signed, directed graph filters.
tags: [spectral-methods, matrix-perturbation, leave-one-out-analysis, community-detection, matrix-completion, phase-retrieval, ranking, pca, point-clouds, signed-graph, graph-filters, parameter-recovery]
papers: ["1706.03175", "1810.04285", "2012.08496", "2103.05465", "2209.00546", "2210.07606"]
related: [spectral-clustering, matrix-completion, leave-one-out-analysis, community-detection, bradley-terry-model, outlier-rejection, graph-neural-network, stochastic-block-model, tensor-decomposition]
status: draft
updated_at: 2026-11-01
---

## Overview

A spectral method builds one matrix from the data and reads the answer from
its leading eigenvectors or singular vectors. The shared idea is to treat that
matrix as a true low-rank matrix plus noise and ask how far the leading
directions move [arxiv:2012.08496 §1.1].

The eigenvector variants rest on one perturbation result. The subspace error is
bounded by the noise size divided by the eigengap of the target, the gap between
its important eigenvalues and the rest. The classic bounds are the Davis–Kahan
theorem for symmetric matrices and Wedin's theorem for singular subspaces
[arxiv:2012.08496 §2.3] [arxiv:2012.08496 §2.4]. The paper's 2×2 example shows
that when the perturbation is as large as the gap, the leading eigenvector can
rotate by a right angle [arxiv:2012.08496 §2.3]. The gap condition is the first
thing to check for any eigenvector variant.

Guarantees come at two scales. The ℓ2 scale measures subspace distance. The
entrywise scale (ℓ∞ and ℓ2,∞) measures error per entry or per row, and it is
proved with leave-one-out arguments [arxiv:2012.08496 §4]. The paper states
that a naive ℓ2 bound is often loose by an order of magnitude when the question
is entrywise [arxiv:2012.08496 §4]. See [leave-one-out analysis](/concepts/leave-one-out-analysis).

**Two senses of "spectral".** The cards use the word in two ways. In the
eigenvector sense, the answer is a leading eigenpair of a data matrix. This is
the monograph's theme [arxiv:2012.08496 §1.1] and the spectral matching step in
PointDSC [arxiv:2103.05465 §3.4], and in the top-k subspace of a label-weighted
second moment used to initialise one-hidden-layer networks [arxiv:1706.03175 §5].
In the graph-signal sense, a filter is defined
on a graph Laplacian and applied to node signals, as in MSGNN
[arxiv:2209.00546 §3.3] and in the low-pass and high-pass channels of ACM-GCN
[arxiv:2210.07606 §4.2]. A third use is a Fourier-style scan over candidate
periods in the hypertime model, which picks a frequency from a time series, not
an eigenvector [arxiv:1810.04285 §3.7]. Check which sense a paper means before
comparing results across them.

## Variants

The eigenvector variants differ in the surrogate matrix they build and in which
eigenpairs they keep. The first eight are from the monograph and are cited to it.

### Low-rank denoising

Observe M = M* + E, with M* symmetric of rank r and E symmetric with Gaussian
noise. Estimate the rank-r eigenspace of M, sorted by absolute eigenvalue
[arxiv:2012.08496 §3.2]. Under the noise bound and a signal-to-noise condition,
the subspace error is at most 10σ√n divided by the r-th eigenvalue of M*
[arxiv:2012.08496 §3.2]. The paper calls this order-wise optimal, citing a
minimax lower bound for r = 1 [arxiv:2012.08496 §3.2]. Card:
[Spectral Methods for Data Science](/papers/2012.08496).

### PCA and spiked covariance

Samples are x_i ~ N(0, M*), where M* = U*Λ*U*ᵀ + σ²I [arxiv:2012.08496 §3.3].
The estimate is the top-r eigenspace of the sample covariance (1/n) Σ x_i x_iᵀ
[arxiv:2012.08496 §3.3]. The error bound has one term for the sample size and
one for noise relative to the eigenvalues [arxiv:2012.08496 §3.3]. With missing
or heteroskedastic data, the diagonal of the surrogate changes, and the paper
suggests correcting it [arxiv:2012.08496 §3.3]. Card:
[Spectral Methods for Data Science](/papers/2012.08496).

### Community detection in the SBM

Two equal groups; within-group edges appear with probability p, between-group
edges with probability q, and p > q [arxiv:2012.08496 §3.4]. The surrogate is
the adjacency matrix, centred by (p+q)/2 and with p added on the diagonal. The
label is the sign of its leading eigenvector, and labels are recovered only up
to a global sign [arxiv:2012.08496 §3.4]. Weak recovery holds when
p ≳ log n / n and √(p/n) = o(p − q) [arxiv:2012.08496 §3.4]. Exact recovery
is a threshold result: it holds when (√p − √q)² is at least 2(1 + ε) log n / n,
and no algorithm can succeed below the matching lower threshold
[arxiv:2012.08496 §4.5]. Card:
[Spectral Methods for Data Science](/papers/2012.08496).

### Gaussian mixture clustering

The mean of the data matrix has rank r with block-constant structure, and the
spectral method works on that spiked structure [arxiv:2012.08496 §3.5]. Under
the stated separation condition, the mis-clustering rate is o(1) with high
probability [arxiv:2012.08496 §3.5]. The card does not summarise the algorithm
steps, so no pseudocode is given here; see §3.5 of the paper.
Card: [Spectral Methods for Data Science](/papers/2012.08496).

### Ranking from pairwise comparisons

Items follow a Bradley–Terry–Luce model with positive scores w
[arxiv:2012.08496 §1.1]. Build a transition matrix from the comparison counts,
scaled by 1/n, with the diagonal filling each row to sum to one. The score
estimate is the leading left eigenvector, normalised to sum to one
[arxiv:2012.08496 §3.6]. The relative error is about κ^2.5 √(log n / n) once
n ≥ Cκ⁵ log n [arxiv:2012.08496 §3.6]. Scores are recoverable only up to scale
[arxiv:2012.08496 §3.6]. The model is the [Bradley–Terry model](/concepts/bradley-terry-model).

The paper's convention is that y_{i,j} = 1 means j beat i, the reverse of the
usual reading. Reversing it reverses the ranking [arxiv:2012.08496 §3.6]. Card:
[Spectral Methods for Data Science](/papers/2012.08496).

### Phase retrieval

Measurements are y_i = (a_iᵀ x*)² with Gaussian design vectors a_i
[arxiv:2012.08496 §3.7]. The surrogate is the weighted sum of outer products
(1/m) Σ y_i a_i a_iᵀ. Its leading eigenvector, scaled, estimates x* up to a
global sign [arxiv:2012.08496 §3.7]. The plain estimator needs
m ≳ n log³ m. When m is about n log m or less, the largest y_i dominates the
surrogate, so the plain estimator fails and a truncated version is needed
[arxiv:2012.08496 §3.7]. The truncation constants are not given numerically,
and the truncated bound needs m ≥ c₀ n [arxiv:2012.08496 §3.7]. Card:
[Spectral Methods for Data Science](/papers/2012.08496).

### Matrix completion

Each entry is observed independently with probability p. Zero-fill the
unobserved entries, divide by p, and take the rank-r truncated SVD
[arxiv:2012.08496 §3.8]. The subspace error scales with the incoherence μ and
the rank r, and it holds once n₁p ≥ C₁κ²μ r log n₂ [arxiv:2012.08496 §3.8].
Incoherence is needed: a matrix with its mass on a single entry cannot be
recovered [arxiv:2012.08496 §3.8]. See [matrix completion](/concepts/matrix-completion).
Card: [Spectral Methods for Data Science](/papers/2012.08496).

### Tensor completion

Unfold the n × n × n tensor into an n × n² matrix of rank at most r
[arxiv:2012.08496 §3.9]. Build the Gram matrix of the unfolding, then set its
diagonal to zero. The diagonal is removed because, at small p, it is large and
not constant, and it hides the low-rank part [arxiv:2012.08496 §3.9]. The
estimate is the top-r eigenspace. The subspace guarantee holds with probability
at least 1 − O(n⁻⁷) and needs a sampling rate of order n^(−3/2)
[arxiv:2012.08496 §3.9]. Card:
[Spectral Methods for Data Science](/papers/2012.08496).

### Spectral initialisation for one-hidden-layer networks

Teacher-student setting: Gaussian inputs, noiseless labels from a one-hidden-layer
network with k units, and k ≤ d [arxiv:1706.03175 §3]. The method first forms
label-weighted moments, the second of which is E[y(xxᵀ − I)] [arxiv:1706.03175
§5]. Its top-k eigenspace, found by power iteration with a shift, gives the
first-layer subspace [arxiv:1706.03175 §5, alg. 1]. Within that subspace, a
third-moment tensor is decomposed to get the weights, and the output weights
follow [arxiv:1706.03175 §5, alg. 4]. The spectral step fixes the subspace; the
tensor step fixes the weights inside it.

The output is a starting point, not the final estimate. The paper then runs
gradient descent on fresh samples at each step, with a step size of at most
1/(k v_max² σ₁^{2p}) [arxiv:1706.03175 §6, alg. 2]. The sample count is linear
in d up to factors in k, κ and log d that the theorems leave unstated
[arxiv:1706.03175 §5, §6]. Prior tensor methods need O(d³/ε²) samples
[arxiv:1706.03175 §2]. The guarantees cover activations with three listed
properties; the paper says ReLU and squared ReLU satisfy them [arxiv:1706.03175
§3]. Linear-rate convergence is proved only for smooth activations
[arxiv:1706.03175 §4]. Experiments are synthetic, with squared ReLU and k = 5,
and run without resampling, which the paper says "still works well"
[arxiv:1706.03175 §7]. Card:
[Recovery Guarantees for One-hidden-layer Neural Networks](/papers/1706.03175).
See also [tensor decomposition](/concepts/tensor-decomposition).

### Spectral matching for correspondence outliers

Used inside a learned pipeline for 3D point-cloud registration. For each seed
correspondence, take its k nearest neighbours in feature space (not in 3D), so
the subset can hold points far apart in space [arxiv:2103.05465 §3.4]. Build a
compatibility matrix M = β ⊙ γ on the subset, where β is a length-consistency
term between point pairs and γ is a feature similarity. Set its diagonal to
zero. The leading eigenvector, found by power iteration, gives an inlier score
per correspondence, and only the relative sizes matter [arxiv:2103.05465 §3.4].
The scores weight a least-squares rigid-transform fit for that seed. The
paper's k is 40 [arxiv:2103.05465 §4]. The network that learns β and γ is
trained against ground-truth poses [arxiv:2103.05465 §3.6]. On 3DMatch with
FCGF features, the authors report 93.28% registration recall and about 60 times
the speed of RANSAC-100k [arxiv:2103.05465 §5.1]. Their traditional spectral
matching baseline is a re-implementation, which uses a different selection rule
than the greedy original [arxiv:2103.05465 §5.1]. Card:
[PointDSC](/papers/2103.05465).

See [outlier rejection](/concepts/outlier-rejection).

### Signed and directed graph filters

Spectral GNN for graphs whose edges carry a sign and a direction. The edge sign
goes into the real part of each entry and the direction into a phase angle set
by a charge q. The resulting Hermitian magnetic signed Laplacian is positive
semidefinite, and its normalised form has eigenvalues in [0, 2]
[arxiv:2209.00546 §3.2]. The layer uses a first-order Chebyshev filter, so it
needs no eigendecomposition, and its cost is that of the unsigned undirected
case [arxiv:2209.00546 §3.3]. The network MSGNN uses two such layers with
complex weights [arxiv:2209.00546 §3.4]. The authors report the highest link
prediction accuracy in all 25 cells against six baselines, 24 outright and one
tie [arxiv:2209.00546 §4.4.2]. Card:
[MSGNN](/papers/2209.00546). See also [graph neural networks](/concepts/graph-neural-network).

### Low-pass and high-pass channels for heterophily

Graph-signal sense, with no eigenvectors. The low-pass operator is row-normalised
averaging with self-loops, and the high-pass operator is the identity minus it
[arxiv:2210.07606 §2.1]. Adaptive channel mixing (ACM) runs three channels in a
layer: low-pass, high-pass and the node's own features. A per-node softmax
weights them [arxiv:2210.07606 §4.2]. Each node can therefore use whichever
view suits its neighbourhood. The authors report 94.75% on Cornell and 90.66%
on PubMed with random 60/20/20 splits [arxiv:2210.07606 §6.2]. Their ablation
shows that adding the three channels without the learned mixing gives lower
accuracy on Cornell (91.64% against 94.75%) [arxiv:2210.07606 §6.1]. Card:
[Revisiting Heterophily For Graph Neural Networks](/papers/2210.07606).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Noisy symmetric matrix, rank r known, gap well above the noise | Low-rank denoising | Needs only the rank and the gap; order-wise optimal per the paper [arxiv:2012.08496 §3.2] |
| Independent samples, want principal directions | PCA | Covariance surrogate; missing data needs a diagonal correction [arxiv:2012.08496 §3.3] |
| Graph with two groups, edge probabilities p and q known | SBM spectral clustering | Needs p and q to build the surrogate; exact recovery has a sharp threshold [arxiv:2012.08496 §3.4] [arxiv:2012.08496 §4.5] |
| Two groups, p and q unknown | Not covered | The paper sketches a parameter-free variant but does not analyse it [arxiv:2012.08496 §3.4] |
| Pairwise comparisons, want relative scores | Spectral ranking | Needs n ≥ Cκ⁵ log n; scores only up to scale [arxiv:2012.08496 §3.6] |
| Quadratic measurements, many of them (m ≳ n log³ m) | Plain phase retrieval | Simplest estimator; fails when measurements are few [arxiv:2012.08496 §3.7] |
| Quadratic measurements, m ≥ c₀ n but below the plain estimator's requirement | Truncated phase retrieval | Truncation controls the largest y_i; constants not stated [arxiv:2012.08496 §3.7] |
| Partly observed matrix, uniform sampling, incoherent | Matrix completion | Rescaled SVD; sampling must be uniform, and heterogeneous sampling is open [arxiv:2012.08496 §3.8] [arxiv:2012.08496 §5] |
| Partly observed 3-way tensor | Tensor completion | Subspace guarantee only, with a sampling rate of order n^(−3/2) [arxiv:2012.08496 §3.9] |
| Feature-matched 3D correspondences with many outliers, labelled training pairs available | Spectral matching (PointDSC) | Reported 93.28% recall on 3DMatch with FCGF; needs ground-truth poses to train [arxiv:2103.05465 §5.1] [arxiv:2103.05465 §3.6] |
| Gaussian inputs, noiseless labels, one hidden layer, weights to recover | Spectral initialisation + gradient descent | Subspace from the second moment, then descent on fresh samples; theory only, synthetic experiments [arxiv:1706.03175 §6] [arxiv:1706.03175 §7] |
| Signed and/or directed graph, node classes or link types | Spectral graph filter (MSGNN) | Carries sign and direction in one Hermitian matrix; author-reported gains on link prediction [arxiv:2209.00546 §4.4.2] |
| Neighbours often have different labels (heterophily) | Channel mixing (ACM) | Per-node choice of low-pass, high-pass or own features; author-reported on ten benchmarks [arxiv:2210.07606 §6.2] |
| Per-entry or per-row error guarantees needed | Leave-one-out bounds | Entrywise bounds are smaller than ℓ2 bounds, but need independent noise [arxiv:2012.08496 §4] [arxiv:2012.08496 §5] |

Two practical cautions apply to every eigenvector row. First, the gap must
exceed the noise, and the monograph lists small eigengaps as an open problem
[arxiv:2012.08496 §5]. Second, estimates are defined only up to rotation or
sign, so compare them through projection matrices or a sign alignment
[arxiv:2012.08496 §2.2] [arxiv:2012.08496 §4.2]. The sign ambiguity is why SBM
and phase retrieval labels are reported up to a global sign
[arxiv:2012.08496 §3.4] [arxiv:2012.08496 §3.7].

For the graph rows, the paper's settings matter more than the concept. The
MSGNN paper gives the charge q in more than one form, and the normalised
Chebyshev rescaling needs a λ_max that the paper does not specify
[arxiv:2209.00546 §3.2] [arxiv:2209.00546 §3.3]. Read the card before
reimplementing.

## Implementation sketch

The core of every eigenvector variant is the same: build a surrogate matrix,
decompose it, and keep the top eigenpairs. The variants differ in the surrogate
and in the selection rule.

```pseudocode
# Common core: decompose a surrogate matrix, keep the top-r eigenpairs  [§3.2]
# Input:  surrogate M (n, n), symmetric; target rank r
#         by_magnitude: True to rank by |lambda|, False to rank by lambda
# Output: U (n, r) estimated eigenspace, lam (r,) its eigenvalues

def spectral_core(M, r, by_magnitude):
    eigenvalues, eigenvectors = eigh(M)
    # Denoising ranks by |lambda| [§3.2]; PCA and phase retrieval use the
    # largest lambda [§3.3] [§3.7]
    if by_magnitude:
        order = argsort(-abs(eigenvalues))
    else:
        order = argsort(-eigenvalues)
    U = eigenvectors[:, order[:r]]
    lam = eigenvalues[order[:r]]
    return U, lam
```

Surrogates by variant, each a one-line change to the first step:

- Denoising: M is the observed matrix [arxiv:2012.08496 §3.2].
- PCA: M is the sample covariance (1/n) Σ x_i x_iᵀ [arxiv:2012.08496 §3.3].
- SBM: M is the adjacency matrix, centred and with p on the diagonal
  [arxiv:2012.08496 §3.4].
- Phase retrieval: M is (1/m) Σ y_i a_i a_iᵀ, or its truncated form
  [arxiv:2012.08496 §3.7].
- Matrix completion: M is the zero-filled observed matrix divided by p. Use a
  rank-r SVD, not an eigendecomposition [arxiv:2012.08496 §3.8].
- Tensor completion: M is the Gram matrix of the unfolding with its diagonal
  removed [arxiv:2012.08496 §3.9].
- Ranking: M is a non-symmetric transition matrix, so use a general eigensolver
  and take the leading left eigenvector [arxiv:2012.08496 §3.6].
- Spectral matching: M is the compatibility matrix β ⊙ γ with zero diagonal,
  and the step is power iteration [arxiv:2103.05465 §3.4].
- Tensor initialisation: M is the label-weighted second moment E[y(xxᵀ − I)];
  take its top-k eigenspace by power iteration [arxiv:1706.03175 §5].
- Graph filter: L̃ = 2L/λ_max − I, then a Chebyshev filter. No eigendecomposition
  is needed [arxiv:2209.00546 §3.3].

The spectral matching step, as a sketch of the power iteration:

```pseudocode
# Inlier scores for one seed's subset  [§3.4]
# Input:  beta (k, k) length consistency, gamma (k, k) feature similarity
# Output: e (k,) inlier scores, scaled to sum to one

def seed_scores(beta, gamma):
    # Compatibility matrix with zero diagonal  [§3.4]
    M = beta * gamma
    fill_diagonal(M, 0)
    # Power iteration; the paper reports fewer than five steps usually  [§3.4]
    e = ones(k) / k
    while not converged(e):
        e = M @ e
        e = e / sum(e)
    return e
```

## Contradictions

None known for numbers reported on the same quantity. Three points need care:

- **Terminology, not disagreement.** "Spectral" means eigenvector estimation in
  the monograph and in spectral matching, and graph-signal filtering in MSGNN and
  in the channels of ACM-GCN [arxiv:2209.00546 §3.3] [arxiv:2210.07606 §4.2]. See
  Overview.
- **Gap condition.** The monograph's perturbation bounds need the eigengap to
  exceed the noise [arxiv:2012.08496 §2.3]. The PointDSC card gives no eigengap
  condition for its compatibility matrix [arxiv:2103.05465 §3.4]. Whether the
  monograph's gap argument carries over to that step is not established here.
- **Reported numbers.** The monograph reports proven bounds with unstated
  constants and runs no benchmarks [arxiv:2012.08496 §1.3] [arxiv:2012.08496 §5].
  The other four papers report benchmark results. Those numbers cannot be
  compared with the monograph's bounds.

## Papers

- [Spectral Methods for Data Science: A Statistical Perspective](/papers/2012.08496): a monograph on perturbation bounds for spectral estimators and their use in denoising, PCA, community detection, ranking, phase retrieval and matrix and tensor completion.
- [Recovery Guarantees for One-hidden-layer Neural Networks](/papers/1706.03175): a power-iteration subspace from a label-weighted second moment, followed by gradient descent with fresh samples; theory with synthetic checks.
- [PointDSC: Robust Point Cloud Registration using Deep Spatial Consistency](/papers/2103.05465): a learned outlier filter whose matching step is a power-iteration spectral method on a compatibility matrix.
- [MSGNN](/papers/2209.00546): a graph network for signed and directed edges, built on a Hermitian Laplacian with Chebyshev filters.
- [Revisiting Heterophily For Graph Neural Networks](/papers/2210.07606): adaptive channel mixing of low-pass, high-pass and identity channels, with homophily measures based on post-aggregation similarity.
- [Warped Hypertime Representations for Long-term Autonomy of Mobile Robots](/papers/1810.04285): a Fourier-style period scan. It is listed here only to mark a different use of "spectral".