Source
Kornblith et al. (2019), LIT-254, read in NOTE-743: §2.1–2.3, Theorem 1 and its proof (App. A), Proposition 1 (App. B).
What was actually shown
Theorem 1. Let X and Y be n × p representations of the same n examples with rank(X) = rank(Y) = n, which needs p ≥ n. If an index satisfies s(X, Z) = s(XA, Z) for every full-rank A, then s(X, Z) = s(Y, Z). The proof stacks X and Y with bases of their row null spaces to get invertible X′ and Y′, and sets A = X′⁻¹Y′, so that XA = Y. Any two such representations are one orbit of GL(p), and an invariant index is constant on it.
Two companions.
- An index invariant to orthogonal maps and to non-isotropic scaling is invariant to every invertible linear map, by the SVD (§2.3). So the group cannot be widened from orthogonal maps by per-axis rescaling without inheriting the degeneracy.
- Proposition 1: an orthogonally invariant index applied to orthonormalized columns, s(Q_X, Q_Y), is invariant to invertible linear maps. This is how CCA acquires the invariance.
What could have failed: an invariant index could have kept some information about how two full-rank representations are placed relative to the examples. It cannot, because the group acts transitively on them.
A precision of the record’s. The paper centres columns. A centred n × p matrix has rank at most n − 1, so centred representations never meet the hypothesis rank = n as written. The construction does go through at rank n − 1, because two centred representations of that rank share the column space orthogonal to the all-ones vector. CLAIM-378 writes it out, in the general form: an index invariant to every invertible linear map depends on a representation only through its column space. That is the record’s, not a statement of the paper.
What this does not say
- Not which group is right. The theorem says only that GL(p) is too large once p ≥ n. The case for orthogonal maps plus isotropic scaling (§2.2) rests on permutation symmetry, on a linear-case result about gradient descent and on rotationally symmetric initialization. The case against GL(p) is empirical (Fig. 1). Neither is a theorem.
- Not that such indexes are blank below full rank. When the rank is below n, an invertible-linear-invariant index can distinguish representations, but only through their column spaces, since XA has the column space of X (CLAIM-378).
- Not that CKA is the right index. CKA’s success on the sanity check (Table 2) is a separate, empirical finding.
Connections
- THEORY-018 and THEORY-002. Softmax training identifies the final representation only up to an invertible linear map. This theorem is the other side of that: a comparison invariant to everything the distribution leaves free is uninformative once the representation is wide enough. Comparisons must either fix a smaller group by stipulation, which is THEORY-018’s point about inner products, or move to identified coordinates, as Nielsen et al. do (LIT-253).
- THEORY-004. Orthogonal invariance is what a centred kernel leaves free. This theorem gives the reason a kernel comparison is not traded for an invertible-linear one.
- CLAIM-193. That kernels fix a representation only up to the symmetry of what is observed is safe from this degeneracy only when that symmetry is smaller than GL(p) or the rank is below n.
- THEORY-008. Kornblith et al. also show that R²_CCA, linear regression and linear CKA are one family, differing in eigenvalue weighting (Eqs. 11–14). That result is held there, as the precursor of the readout account.