Spectral Methods: Eigenbases, Filtering and Smoothing

By Better Wise

The previous lesson showed that the same formula can return different numbers depending on where precision lives in the pipeline. That matters here, because the spectral view reduces filtering to a question about eigenvalues, and eigenvalues are frequently the least accurate numbers a pipeline produces. By the end you should be able to move a signal into an eigenbasis, design a filter there, and tell when the spectrum itself is noise.

• Write a symmetric operator as $A = Q\Lambda Q^\top$ and read filtering as scaling the coefficients $c = Q^\top x$.
• Build a graph Laplacian and interpret $x^\top L x$ as roughness.
• Design low-pass, high-pass, band-pass and truncation filters, with numbers.
• Diagnose ill-conditioned or unresolvable eigenpairs.
• Choose between a dense eigendecomposition and matrix-free polynomial filtering.

The eigenbasis makes the operator diagonal

For a symmetric operator, $A = Q\Lambda Q^\top$ with orthonormal $Q$. Change coordinates with $c = Q^\top x$, scale each coefficient, and change back:

$$ y = Q g(\Lambda) Q^\top x = \sum_i g(\lambda_i)(q_i^\top x),q_i $$

The eigenvectors are fixed shapes; the eigenvalues are gains. "Filter design" is nothing more than choosing a scalar function $g$. Because $g$ acts on $\lambda$, it never needs to distinguish eigenvectors, so a spectral filter is a function of the eigenvalues alone, and it stays well defined even when the eigenvectors are not unique.

flowchart TD
    A["📈<br/>x in node space"] --> B["🔀<br/>c = Q^T x"]
    B --> C["🎚️<br/>c_i *= g(λ_i)"]
    C --> D["🔁<br/>y = Q c"]

The practical payoff: one dense decomposition costs $O(n^3)$, after which every filter evaluation is a $O(n)$ diagonal scaling. If you only need the extreme eigenpairs, you never form $Q$ at all.

The graph Laplacian as a roughness meter

For a weighted graph, $L = D - A$, and its normalized form $L_{sym} = I - D^{-1/2}AD^{-1/2}$ has spectrum in $[0,2]$. The quadratic form is the Dirichlet energy:

$$ x^\top L x = \sum_{i<j} w_{ij}(x_i - x_j)^2 $$

So $x^\top L x$ is _____, which is small exactly when neighbors agree. The eigenvector for $\lambda_0 = 0$ is constant: no differences, no energy. Small eigenvalues carry slowly varying shapes; large eigenvalues carry high-frequency oscillation.

Take the 3-node path with unit weights, $L = [[1,-1,0],[-1,2,-1],[0,-1,1]]$. The spectrum is $0, 1, 3$: constant $(1,1,1)/\sqrt3$, the ramp $(1,0,-1)/\sqrt2$, and the zigzag $(1,-2,1)/\sqrt6$. Reading a signal in this basis is a statement about how much of it is flat, how much is a gradient, how much is a sawtooth.

Building a filter, with numbers

Worked example (low-pass). Signal $x = (1,2,1)$ on the path graph, heat filter with $t = 0.5$. Coefficients: along $\lambda=0$, $q_0^\top x = 4/\sqrt3$; along $\lambda = 1$, $(1-1)/\sqrt2 = 0$; along $\lambda = 3$, $(1-2\cdot 2+1)/\sqrt6 = -2/\sqrt6$. Only two modes are alive. After scaling, $e^{-1.5} = 0.2231$ multiplies the zigzag component, giving

$y \approx 1.333(1,1,1) - 0.182(1,-2,1)/\sqrt6 \approx (1.259,\ 1.482,\ 1.259)$.

The peak dropped from $2$ to $1.48$ and the flanks rose: the filter moved the signal toward its mean, and the mean itself is untouched because $g(0)=1$ and the row sums of $L$ are zero.

Worked example (sharpening). The high-pass $x - \alpha L x$ scales mode $i$ by $1 - \alpha\lambda_i$. With $\alpha = 0.3$, $Lx = (-1,2,-1)$, so $y = (1.3, 1.4, 1.3)$: same mean, steeper peak. Note what the same operator does to a noisy signal: it multiplies every high mode by $1-\alpha\lambda > 1$.

Denoising is projection, and it has a price

Write $x = s + n$ with white noise $n$. Because $Q$ is orthogonal, white noise keeps its isotropy in the spectral domain, so the expected energy per mode is roughly constant, _____. Signal energy, in contrast, concentrates on small eigenvalues. Truncating to $k$ of $n$ modes therefore retains about _____ of the noise energy while keeping most of the signal. That ratio is the whole trade: aggressive smoothing removes noise and also removes genuine edges.

Where spectra break

Three failure modes deserve names, and all three are precision stories.

Small gaps destabilize eigenvectors. For a symmetric perturbation $E$, eigenvector error scales like $|E|/\text{gap}$, where the gap is the distance to the nearest other eigenvalue. Well-separated eigenvalues give robust shapes; clustered ones do not, and any downstream code that compares eigenvectors across runs is comparing arbitrary signs and near-arbitrary directions. Compare projectors or filtered outputs instead.

Degeneracy makes "the" eigenvectors fictional. A 4-cycle has $L$ eigenvalues $0, 2, 2, 4$. The eigenspace for $\lambda = 2$ is two-dimensional, so any orthonormal basis of it works. $g(L)$ is unaffected, which is precisely why you should express every algorithm as $g(L)$ rather than as an explicit list of eigenvectors.

Absolute eigenvalue error scales with the norm. Computed eigenvalues of a symmetric matrix carry absolute error near ____. In fp32, $\varepsilon \approx 1.2\times10^{-7}$; with $|L| \approx 4$, a true $\lambda{\min} = 10^{-8}$ (two clusters joined by a very weak edge) is entirely inside the noise floor. The algebraic connectivity you read off is not a property of the graph, it is a property of your arithmetic. The same logic explains why $x^\top L x$ must never be computed as $x^\top D x - x^\top A x$ for smooth $x$: two large, nearly equal numbers cancel, and the edge-sum form avoids the cancellation entirely.

Lanczos needs help. Iterative eigensolvers converge slowly on clustered spectra and lose orthogonality in low precision, producing duplicate "ghost" eigenvalues. Reorthogonalization is not optional at scale.

Rules of thumb for spectral filtering

• Test every low-pass filter on the constant vector: the output must be $g(0)\cdot\mathbf{1}$. Any drift is a bug or a precision problem, and it is the cheapest test you will ever write.
• Distrust any $\lambda$ below $\sqrt{\varepsilon},|L|$. Recompute in fp64 or reformulate before drawing conclusions.
• Never materialize $Q$ above a few thousand nodes. Use Lanczos for a handful of extreme eigenpairs, or apply $g(L)$ matrix-free with a Chebyshev expansion in $O(m|E|)$, which needs only smooth $g$.
• Sharp cutoffs (indicator filters) require an actual eigendecomposition; polynomial methods approximate smooth $g$ well and step functions badly.
• Store and compare $g(L)x$, never eigenvector matrices, whenever results must be reproducible across runs.

What to carry forward

Filtering is diagonal scaling in an eigenbasis: choose $g$ to encode what "smooth" means, then verify the spectrum you rely on is resolvable in your precision. Small eigenvalues are signal for smoothing and noise for numerics, and the eigenvalue gap decides whether an individual eigenvector means anything at all. Next, we reuse exactly this move in a probabilistic setting, rewriting a variational bound as a KL objective and reading the ELBO as the cost of approximating one distribution with another.

Front: What form does a filter take on a symmetric operator? Back: g(A) = Q g(Λ) Q^T: same eigenvectors, eigenvalues scaled by g.

Front: Why is the eigenbasis efficient for repeated filtering? Back: One O(n^3) decomposition, then each filter is a diagonal scaling costing O(n).

Front: What does x^T L x measure on a graph? Back: Dirichlet energy: the weighted sum of squared differences across edges.

Front: Which eigenvalues carry slowly varying shapes? Back: The smallest ones, starting at λ = 0, whose eigenvector is constant on a connected graph.

Front: What does the heat kernel e^{-tL} converge to as t grows? Back: The mean of the signal, which is the λ = 0 component.

Front: How does white noise distribute across spectral modes? Back: Roughly uniformly, about σ² per mode, since orthogonal Q preserves isotropy.

Front: How does eigenvalue gap affect eigenvector stability? Back: Eigenvector error scales as ||E||/gap, so small gaps give unstable directions.

Front: Why can 'the' eigenvectors of a matrix be non-unique? Back: Repeated eigenvalues admit any orthonormal basis of the eigenspace, though g(L) stays well defined.

Front: What is the absolute error in computed eigenvalues of a symmetric matrix? Back: About ε·||L||, so tiny eigenvalues can have terrible relative accuracy.

Front: How should x^T L x be evaluated for accuracy? Back: As an edge sum of w_ij (x_i - x_j)^2, not as x^T D x - x^T A x.

Front: What breaks Lanczos on clustered spectra in low precision? Back: Slow convergence and loss of orthogonality, which produces duplicate ghost eigenvalues.

Front: What replaces a dense eigendecomposition for large graphs? Back: Lanczos for a few extreme eigenpairs, or matrix-free Chebyshev approximation of g(L).

Front: What does a high-pass filter do to noise? Back: Amplifies it, since modes with large λ get gain above one.