Spectral methods

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 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 2012.08496 §2.3 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 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 2012.08496 §4. The paper states that a naive ℓ2 bound is often loose by an order of magnitude when the question is entrywise 2012.08496 §4. See 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 2012.08496 §1.1 and the spectral matching step in PointDSC 2103.05465 §3.4, and in the top-k subspace of a label-weighted second moment used to initialise one-hidden-layer networks 1706.03175 §5. In the graph-signal sense, a filter is defined on a graph Laplacian and applied to node signals, as in MSGNN 2209.00546 §3.3 and in the low-pass and high-pass channels of ACM-GCN 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 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 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* 2012.08496 §3.2. The paper calls this order-wise optimal, citing a minimax lower bound for r = 1 2012.08496 §3.2. Card: Spectral Methods for Data Science.

PCA and spiked covariance

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

Community detection in the SBM

Two equal groups; within-group edges appear with probability p, between-group edges with probability q, and p > q 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 2012.08496 §3.4. Weak recovery holds when p ≳ log n / n and √(p/n) = o(p − q) 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 2012.08496 §4.5. Card: Spectral Methods for Data Science.

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 2012.08496 §3.5. Under the stated separation condition, the mis-clustering rate is o(1) with high probability 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.

Ranking from pairwise comparisons

Items follow a Bradley–Terry–Luce model with positive scores w 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 2012.08496 §3.6. The relative error is about κ^2.5 √(log n / n) once n ≥ Cκ⁵ log n 2012.08496 §3.6. Scores are recoverable only up to scale 2012.08496 §3.6. The model is the 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 2012.08496 §3.6. Card: Spectral Methods for Data Science.

Phase retrieval

Measurements are y_i = (a_iᵀ x*)² with Gaussian design vectors a_i 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 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 2012.08496 §3.7. The truncation constants are not given numerically, and the truncated bound needs m ≥ c₀ n 2012.08496 §3.7. Card: Spectral Methods for Data Science.

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 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₂ 2012.08496 §3.8. Incoherence is needed: a matrix with its mass on a single entry cannot be recovered 2012.08496 §3.8. See matrix completion. Card: Spectral Methods for Data Science.

Tensor completion

Unfold the n × n × n tensor into an n × n² matrix of rank at most r 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 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) 2012.08496 §3.9. Card: Spectral Methods for Data Science.

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 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 1706.03175 §5, alg. 1. Within that subspace, a third-moment tensor is decomposed to get the weights, and the output weights follow 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}) 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 1706.03175 §5, §6. Prior tensor methods need O(d³/ε²) samples 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 1706.03175 §4. Experiments are synthetic, with squared ReLU and k = 5, and run without resampling, which the paper says "still works well" 1706.03175 §7. Card: Recovery Guarantees for One-hidden-layer Neural Networks. See also 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 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 2103.05465 §3.4. The scores weight a least-squares rigid-transform fit for that seed. The paper's k is 40 2103.05465 §4. The network that learns β and γ is trained against ground-truth poses 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 2103.05465 §5.1. Their traditional spectral matching baseline is a re-implementation, which uses a different selection rule than the greedy original 2103.05465 §5.1. Card: PointDSC.

See 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] 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 2209.00546 §3.3. The network MSGNN uses two such layers with complex weights 2209.00546 §3.4. The authors report the highest link prediction accuracy in all 25 cells against six baselines, 24 outright and one tie 2209.00546 §4.4.2. Card: MSGNN. See also graph neural networks.

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 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 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 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%) 2210.07606 §6.1. Card: Revisiting Heterophily For Graph Neural Networks.

When to use which

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 2012.08496 §5. Second, estimates are defined only up to rotation or sign, so compare them through projection matrices or a sign alignment 2012.08496 §2.2 2012.08496 §4.2. The sign ambiguity is why SBM and phase retrieval labels are reported up to a global sign 2012.08496 §3.4 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 2209.00546 §3.2 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.

# 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 2012.08496 §3.2.
• PCA: M is the sample covariance (1/n) Σ x_i x_iᵀ 2012.08496 §3.3.
• SBM: M is the adjacency matrix, centred and with p on the diagonal 2012.08496 §3.4.
• Phase retrieval: M is (1/m) Σ y_i a_i a_iᵀ, or its truncated form 2012.08496 §3.7.
• Matrix completion: M is the zero-filled observed matrix divided by p. Use a rank-r SVD, not an eigendecomposition 2012.08496 §3.8.
• Tensor completion: M is the Gram matrix of the unfolding with its diagonal removed 2012.08496 §3.9.
• Ranking: M is a non-symmetric transition matrix, so use a general eigensolver and take the leading left eigenvector 2012.08496 §3.6.
• Spectral matching: M is the compatibility matrix β ⊙ γ with zero diagonal, and the step is power iteration 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 1706.03175 §5.
• Graph filter: L̃ = 2L/λ_max − I, then a Chebyshev filter. No eigendecomposition is needed 2209.00546 §3.3.

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

# 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 2209.00546 §3.3 2210.07606 §4.2. See Overview.
• Gap condition. The monograph's perturbation bounds need the eigengap to exceed the noise 2012.08496 §2.3. The PointDSC card gives no eigengap condition for its compatibility matrix 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 2012.08496 §1.3 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: 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: 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: a learned outlier filter whose matching step is a power-iteration spectral method on a compatibility matrix.
• MSGNN: a graph network for signed and directed edges, built on a Hermitian Laplacian with Chebyshev filters.
• Revisiting Heterophily For Graph Neural Networks: 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: a Fourier-style period scan. It is listed here only to mark a different use of "spectral".