# Ky-Fan certificate for tensorized layers

- ID: 1477
- Canonical URL: https://synthcore.org/idea/1477/ky-fan-certificate-for-tensorized-layers
- API JSON: https://synthcore.org/api/idea/1477.json
- API Markdown: https://synthcore.org/api/idea/1477.md
- Verification status: unverified
- Source: [arXiv:2607.27116](https://arxiv.org/abs/2607.27116)
- Category: regularization
- Solves: stability, memory, generalization
- ML areas: mlp, transformer, regularization
- Math tags: linear-algebra, spectral-theory, tensor-decomposition
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Parameterize a large linear layer as a sum of binary tensor products, W = Σ_l A_l ⊗ B_l, and regularize a factor-level upper bound on its top-k singular-value sums. The bound controls all Ky Fan norms of W while requiring SVDs only of the small factors, making it suitable for tensorized MLP or attention projections.

## Mathematical statement

For vectors x,y in R^d, weak majorization x ≺_w y means Σ_{i=1}^k x_i^↓ ≤ Σ_{i=1}^k y_i^↓ for every k, where x_i^↓ denotes entries sorted in nonincreasing order. The paper's binary tensor-product result gives, for arbitrary matrices A_l and B_l of compatible square dimensions, σ(Σ_{l=1}^m A_l ⊗ B_l) ≺_w sort(Σ_{l=1}^m σ(A_l) ⊗ σ(B_l)), where σ(A_l) is the nonincreasing singular-value vector and the Kronecker product produces all pairwise products σ_i(A_l)σ_j(B_l); sort reorders the resulting vector. Therefore, for every k, ||W||_(k) := Σ_{i=1}^k σ_i(W) ≤ U_k := Σ_{i=1}^k c_i, where c = sort(Σ_l σ(A_l) ⊗ σ(B_l)). The extracted paper also records the positive-semidefinite eigenvalue specialization λ(Σ_{l=1}^m A_l ⊗ B_l) ≺ Σ_l λ(A_l) ⊗ λ(B_l) for the stated two-summand setting; the singular-value theorem is the version used here. The certificate is exact as an inequality but may be loose when summands have cancellation or mismatched singular vectors.

## Key formulas

- $$x\prec_w y\quad\Longleftrightarrow\quad \sum_{i=1}^{k}x_i^{\downarrow}\leq\sum_{i=1}^{k}y_i^{\downarrow}\quad\text{for every }k,$$
- $$\lambda\Big(\sum_{l=1}^{m}A_l\otimes B_l\Big)\prec\sum_{l=1}^{m}\lambda(A_l)\otimes\lambda(B_l),\quad\text{for }m=2,$$
- $$\sigma\Big(\sum_{l=1}^{m}A_l\otimes B_l\Big)\prec_w\operatorname{sort}\Big(\sum_{l=1}^{m}\sigma(A_l)\otimes\sigma(B_l)\Big),$$
- $$\|W\|_{(k)}=\sum_{i=1}^{k}\sigma_i(W)\leq U_k:=\sum_{i=1}^{k}c_i,\qquad c=\operatorname{sort}\Big(\sum_{l=1}^{m}\sigma(A_l)\otimes\sigma(B_l)\Big),\quad W=\sum_{l=1}^{m}A_l\otimes B_l.$$

## Implementation notes

1. Integration point: replace a dense linear map in a small MLP or transformer projection with a tensorized map W = Σ_{l=1}^m A_l ⊗ B_l. For an input reshaped into compatible tensor dimensions, apply each Kronecker factor without explicitly materializing W, or materialize W only for the baseline comparison. Add a regularizer to the training loss that penalizes selected Ky Fan certificates U_k, especially U_1 for Lipschitz control and U_r for the top-r energy. 2. Pseudocode: `for each layer: for l in 1..m: sA[l] = svdvals(A[l]); sB[l] = svdvals(B[l]); c = sort_desc(sum_l kron(sA[l], sB[l])); U = c.cumsum(0); R = alpha * sum(k in K, weight[k] * (U[k] / target[k])^2); loss = task_loss + R; optimizer.step()`. The symbol c is the paper's majorization right-hand side and U[k] is its certified bound on the sum of the largest k singular values of the assembled layer. 3. Mathematical computation versus estimation: compute factor SVDs exactly when factors are small; for larger factors use 5-10 steps of randomized subspace iteration and treat the resulting singular values as approximate factor spectra. The sorting and cumulative sums are exact for the estimated spectra. Do not assume equality: periodically materialize W and compute its true top-k singular values to measure certificate looseness. 4. First experiment: train a 2-layer CIFAR-10 MLP with a 1024-to-1024 hidden projection represented by m=4 Kronecker summands, comparing no spectral regularization, ordinary dense spectral-norm penalty, and the proposed K={1,8,32} certificate penalty at matched parameter count and FLOPs. Track validation accuracy, gradient norm variance, true spectral/Ky Fan norms of W, and training stability under a 2x larger learning rate. Success is lower true top-k norms and fewer exploding-loss runs at equal accuracy, or equal accuracy with smaller factor ranks or parameter count; also report the ratio U_k / ||W||_(k) to quantify whether the theorem's bound is useful rather than vacuous.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.