Question 5

What does the representation look like?

What geometric, spectral or low-dimensional structure does the model have or learn, what can it express, and up to which symmetries is that structure determined?

Symptoms

Is this your question?

This question deliberately covers three theorem types: geometry ("the features look like this"), expressivity ("the architecture can represent this") and identifiability ("this can be recovered, up to these symmetries").

Sub-cases

Which version are you facing?

Case Usually start with
Eigenvalues or eigenspaces of learned features? A Gram or covariance matrix, the variational eigenvalue characterization, Weyl and Davis–Kahan.
Low-rank structure or the best subspace? SVD, Eckart–Young, matrix concentration and perturbation.
Neural collapse or simplex geometry? Within- and between-class scatter, equality cases, often reduced to an unconstrained-feature model.
Is the target representable? Constructive approximation, rank or width arguments, covering or universal-approximation results.
Are latent factors recoverable uniquely? Define the equivalence group first, then prove identifiability modulo that group from interventions, independence, temporal structure or moments.
The recipes

Three kinds of claim, three routes

This question covers three different theorem types, and each has its own route. Decide which one you are making before you start.

Geometry or spectra: "the features look like this." Find the matrix whose structure is your claim.

  1. Define the object that captures the claim: a feature Gram matrix, class-mean matrix, covariance or Jacobian.
  2. Solve the idealized population problem first and characterize its spectrum or optimum.
  3. Bound the empirical or training perturbation in a norm your perturbation theorem accepts.
  4. Apply Weyl for eigenvalues, and Davis–Kahan only if you have an eigengap.
  5. Translate the structure into a consequence someone can use, such as linear-probe error, rank or robustness.

Expressivity: "the architecture can represent this." Build the witness explicitly.

  1. Fix the target class and the error metric, for example Lipschitz functions on a cube in sup norm.
  2. Construct a network that approximates a building block (a bump, a product, a piecewise-linear piece).
  3. Assemble the blocks and add up their errors.
  4. Count the resources (width, depth, number of parameters) as a function of the accuracy.
  5. If you claim the count is necessary, prove a lower bound with a counting or covering argument. That is Question 6.

Identifiability: "this can be recovered, up to these symmetries." Reverse the usual order.

  1. Name the symmetry group \(G\) first: permutations, rotations, scalings, sign flips, component-wise transformations.
  2. Find statistics of the observed distribution that pin the parameters down up to \(G\): moments, conditional independences, the effect of interventions, temporal structure.
  3. Prove injectivity modulo \(G\): if two parameters give the same statistics, they differ by an element of \(G\).
  4. Only then add estimation: how many samples recover the parameters to a given accuracy, which is Question 4.
1.00
0.10
Top eigenvectorgreen wedge: where Davis–Kahan allows it
Eigenvaluesgreen band: where Weyl allows them
\(A = \operatorname{diag}(\lambda_1, \lambda_2)\) \(A + E\)
Eigenvalues are stable; eigenvectors need a gap. Weyl keeps every eigenvalue within \(\lVert E \rVert_2\) of where it was, whatever the gap. Davis–Kahan bounds the angle of the top eigenvector by \(2\lVert E \rVert_2/\delta\). Shrink the gap below the perturbation size and the bound says nothing, and the eigenvector can swing anywhere while the eigenvalues barely move.
A complete proof

Weyl's inequality from Courant–Fischer

The claim

For symmetric \(A, E \in \mathbb{R}^{d \times d}\) with eigenvalues sorted in decreasing order, every eigenvalue moves by at most the operator norm of the perturbation:

\[\lvert \lambda_i(A + E) - \lambda_i(A) \rvert \le \lVert E \rVert_2 \quad \text{for all } i.\]
Assumptions
  • \(A\) and \(E\) are symmetric, for example a covariance or Gram matrix and its sampling error.
  • Nothing about the gap between eigenvalues; that is exactly what makes this result robust.
First move, and why

Rewrite each eigenvalue as an optimization over subspaces with Courant–Fischer. Eigenvalues are awkward to compare directly, but values of a max–min problem can be compared one quadratic form at a time.

Show the proof, with commentary

Step 1: pointwise. For every unit vector \(x\),

\[x^\top (A + E)\, x = x^\top A x + x^\top E x \le x^\top A x + \lVert E \rVert_2 .\]

Step 2: through the min and the max. Taking the minimum over unit \(x\) in a subspace \(S\), then the maximum over subspaces of dimension \(i\), preserves the inequality:

\[\lambda_i(A + E) = \max_{\dim S = i}\ \min_{x \in S,\, \lVert x \rVert = 1} x^\top (A + E) x \le \lambda_i(A) + \lVert E \rVert_2 .\]

Min and max preserve pointwise inequalities, and adding the same constant to every value shifts them by that constant. That is all this step uses.

Step 3: the other direction. Apply the same argument to \(A = (A + E) + (-E)\), using \(\lVert -E \rVert_2 = \lVert E \rVert_2\). \(\blacksquare\)

A useful corollary: if \(\lVert E \rVert_2 < \delta/2\), where \(\delta\) is the gap below \(\lambda_1(A)\), the perturbed top eigenvalue stays separated from the rest. That is the first hypothesis Davis–Kahan needs.

A tempting approach that fails

Concluding that eigenvectors are stable because eigenvalues are. Take \(A = I_2\): every unit vector is an eigenvector, and an arbitrarily small \(E\) chooses the top eigenvector of \(A + E\) to be whatever direction \(E\) prefers. The demo shows the same thing as the gap shrinks: eigenvalues stay put while the eigenvector swings.

If you relax an assumption
  • Non-symmetric matrices: eigenvalues can be far more sensitive. \(\begin{pmatrix} 0 & 1 \\ \varepsilon & 0 \end{pmatrix}\) has eigenvalues \(\pm\sqrt{\varepsilon}\). Singular values still obey Weyl's inequality, so work with them instead.
  • You need eigenvectors: add an eigengap assumption and use Davis–Kahan.
Try it yourself

A two-by-two perturbation, done exactly

The exercise

Let \(A = \mathrm{diag}(3, 1)\) and \(E = \begin{pmatrix} 0 & \varepsilon \\ \varepsilon & 0 \end{pmatrix}\), so \(\lVert E \rVert_2 = \varepsilon\).

  1. What does Weyl's inequality promise, and what actually happens to the eigenvalues?
  2. Find the exact angle \(\theta\) between the top eigenvectors of \(A\) and \(A + E\), and compare it with the Davis–Kahan bound \(\sin\theta \le 2\lVert E \rVert/\delta\).
  3. Repeat with \(A = I\). What changes?
Hint

For a symmetric \(2 \times 2\) matrix \(\begin{pmatrix} a & b \\ b & c \end{pmatrix}\), the eigenvalues are \(\tfrac{a + c}{2} \pm \sqrt{\big(\tfrac{a - c}{2}\big)^2 + b^2}\), and the top eigenvector makes an angle \(\theta\) with the first axis where \(\tan 2\theta = 2b/(a - c)\).

Show a solution

1. Weyl allows each eigenvalue to move by \(\varepsilon\). The exact eigenvalues are \(2 \pm \sqrt{1 + \varepsilon^2}\), so each moves by \(\sqrt{1 + \varepsilon^2} - 1 \approx \varepsilon^2/2\). Weyl is correct but loose here: an off-diagonal perturbation has no first-order effect on the eigenvalues.

2. \(\tan 2\theta = 2\varepsilon/2 = \varepsilon\), so \(\theta = \tfrac12\arctan\varepsilon \approx \varepsilon/2\). The gap is \(\delta = 2\), so Davis–Kahan gives \(\sin\theta \le \varepsilon\): the right order, off by about a factor of 2.

3. With \(A = I\) the gap is 0. The eigenvalues \(1 \pm \varepsilon\) still move by exactly \(\varepsilon\), as Weyl allows, but the top eigenvector of \(I + E\) is \((1, 1)/\sqrt2\) for every \(\varepsilon > 0\): a 45° turn from \((1, 0)\) for a perturbation as small as you like (with \(A = I\) there was no preferred direction to begin with). Eigenvalues are stable without a gap; eigenvectors are not.

The toolkit

What each tool gives you, and what it costs

Singular value decomposition

\[A = U \Sigma V^\top, \qquad \sigma_1 \ge \sigma_2 \ge \dots \ge 0\]

For any \(A \in \mathbb{R}^{m \times n}\).

Gives
Canonical low-rank directions, Gram spectra and effective dimensionality.
Costs
A linear representation of the object.
Wrong tool when
The real issue is a nonlinear equivalence.

Eckart–Young–Mirsky

\[\min_{\operatorname{rank}(B) \le r} \lVert A - B \rVert_F^2 = \sum_{j > r} \sigma_j(A)^2\]

Attained by the truncated SVD.

Gives
The optimal rank-\(r\) approximation.
Costs
A Frobenius or other unitarily invariant norm.
Wrong tool when
Low effective rank has not been shown; an arbitrary truncation is not justified.

Weyl's inequality

\[\lvert \lambda_i(A + E) - \lambda_i(A) \rvert \le \lVert E \rVert_2, \qquad \lvert \sigma_i(A + E) - \sigma_i(A) \rvert \le \lVert E \rVert_2\]

For symmetric \(A, E\) (first form) and any matrices (second form).

Gives
Stability of eigenvalues and singular values.
Costs
Control of the perturbation in operator norm.
Wrong tool when
You need eigenvectors; eigenvalues alone do not control them near a repeated eigenvalue.

Davis–Kahan sinΘ theorem

\[\lVert \sin\Theta(\hat U, U) \rVert_2 \le \frac{2\,\lVert \hat A - A \rVert_2}{\delta}\]

One common form (Yu, Wang and Samworth), with \(\delta\) the gap between the target eigenvalues of \(A\) and the rest of its spectrum.

Gives
Stability of eigenvectors and eigenspaces.
Costs
A non-zero eigengap.
Wrong tool when
Eigenvalues are repeated or nearly repeated; then only the whole invariant subspace may be identifiable.

Courant–Fischer

\[\lambda_k(A) = \max_{\dim S = k}\ \min_{x \in S,\ \lVert x \rVert = 1} x^\top A x\]

For symmetric \(A\).

Gives
Turns spectral claims into variational inequalities.
Costs
A symmetric or Hermitian operator.
Wrong tool when
The matrix is non-normal and its eigenvectors are unstable.

Identifiability modulo a symmetry group

\[P_\theta = P_{\theta'} \;\Longrightarrow\; \theta' = g \cdot \theta \ \text{ for some } g \in G\]

For a group \(G\) acting on parameters.

Gives
The correct target for latent-variable and causal representation recovery.
Costs
The group must be specified, and the observations or interventions must break every remaining ambiguity.
Wrong tool when
You claim literal parameter recovery in a model with permutation, rotation, scaling or sign symmetries.
Worked examples

How published papers answer it

  1. HaoChen, Wei, Gaidon & Ma, Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss, NeurIPS 2021. arXiv

    Introduces an augmentation graph, reads the population objective through its spectral decomposition, and shows that minimizing the spectral contrastive loss yields features with linear-probe guarantees. Standard generalization bounds then bridge population and training loss.

  2. Papyan, Han & Donoho, Prevalence of Neural Collapse during the Terminal Phase of Deep Learning Training, PNAS 117(40), 2020. arXiv

    Identifies the four neural-collapse phenomena: within-class collapse, class means forming a simplex equiangular tight frame, alignment with the classifier, and nearest-class-center decisions. Primarily an empirical and structural discovery that later theory set out to explain.

  3. Zhou, Li, Ding, You, Qu & Zhu, On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Features, ICML 2022. PMLR

    Under an unconstrained-feature model, shows every global minimizer exhibits neural collapse and every other critical point is a strict saddle. A template for reducing "what do features look like?" to "what do all global optima look like?"

  4. Lippe, Magliacane, Löwe, Asano, Cohen & Gavves, CITRIS: Causal Identifiability from Temporal Intervened Sequences, ICML 2022. PMLR

    Uses temporal observations with known intervention targets to prove identifiability of scalar and multidimensional causal factors under its model assumptions. A clear model for stating identifiability with explicit observational and interventional information.

Common traps

Where proofs of this kind go wrong

Resources

Where to go next

← Back to the guide

Found an error, or have a better example or a question this guide should cover? Email m.molahasani.m@gmail.com. Corrections and contributions are welcome. Last updated October 5, 2026.