# Sparse Root-of-Unity Isometric Mixer

- ID: 998
- Canonical URL: https://synthcore.org/idea/998/sparse-root-of-unity-isometric-mixer
- API JSON: https://synthcore.org/api/idea/998.json
- API Markdown: https://synthcore.org/api/idea/998.md
- Verification status: unverified
- Source: [arXiv:2607.16069](https://arxiv.org/abs/2607.16069)
- Category: architecture
- Solves: speedup, stability, memory
- ML areas: mlp, transformer, initialization, inference-speedup, training-dynamics
- Math tags: representation-theory, linear-algebra, combinatorics, algebra
- Ratings: usefulness 6/10; difficulty 6/10; novelty 7/10

## Idea description

Replace a dense channel-mixing matrix by a sparse complex generalised weighing matrix W with exactly w nonzero entries in every row and column, then use U=W divided by square root of w as a norm-preserving mixer. Restricting to k=2 gives a real matrix with entries in {+1,-1}; k=4 supports signed phase rotations. The exact isometry should preserve signal and gradient norms while reducing channel-mixing cost.

## Mathematical statement

A complex generalised weighing matrix CGW(n,w;k) is an n by n matrix W with exactly w nonzero entries in every row and column, with each nonzero entry in the set mu_k={exp(2 pi i r/k): 0 less than or equal to r less than k}, satisfying W W* = w I_n. Here W* is the conjugate transpose and I_n is the identity matrix. Therefore U=W divided by square root of w satisfies U U* = I_n, so every singular value of U equals one and U preserves Euclidean norms. The paper constructs matrices in the centralizer algebra of a transitive monomial representation induced from a linear character. For a finite group G, subgroup H, transversal T={t_i} for H in G, and linear character chi of H, the representation is rho_chi(g)=[chi_plus(t_i g t_k^{-1})]_{i,k}. A centralizer matrix has entries constrained by m(T(g),T(tg))=m(1,t) chi_H(g)^{-1} chi_H(tg). An orbital represented by (1,t) is usable only when chi(t h t^{-1} h^{-1})=1 for every h in H intersected with t^{-1} H t; otherwise its coefficient must vanish. The transferable property is the exact identity W W*=w I, while the centralizer formula supplies a way to generate repeated, structured sparse patterns.

## Key formulas

- $$W W^{\ast}=w I_n,\qquad U=\frac{1}{\sqrt{w}}W,\qquad U U^{\ast}=I_n.$$
- $$\rho_{\chi}(g)=\bigl[\chi^{+}(t_i g t_k^{-1})\bigr]_{i,k}.$$
- $$m({\bf T}(g),{\bf T}(tg))=m(1,t)\,\chi_{\bf H}(g)^{-1}\chi_{\bf H}(tg).$$
- $$\chi(tht^{-1}h^{-1})=1\quad\forall h\in H\cap t^{-1}Ht.$$

## Implementation notes

(1) Integration point: replace one dense channel-mixing operation in an MLP block, residual block, or Transformer feed-forward projection by y = U x, where U is fixed during the first experiment. Use k=2 for a real-valued MVP. Store each row as w integer column indices and w signs, so the operation is a sparse signed gather-and-sum followed by multiplication by 1 divided by square root of w. For a complex k=4 version, represent each complex feature as two real channels and implement phases using the four maps {x, -x, i x, -i x}, which require only sign changes and real-imaginary swaps. (2) Pseudocode: generate candidate W; set every row and column to exactly w nonzeros; assign entries from the chosen root-of-unity table; compute G = W W*; reject the candidate unless max absolute off-diagonal(G) is below 1e-6 and max absolute diagonal(G)-w is below 1e-6. During forward propagation, for each row i compute y_i = sum over r from 1 to w of phase[i,r] times x[idx[i,r]] divided by sqrt(w). Apply the original bias and activation after this mixer. (3) Mathematical checks are the exact weighing identity and the resulting norm preservation ||Ux||_2 = ||x||_2. If reproducing the paper's structured construction, enumerate a small finite group G, subgroup H, transversal T, and character chi; assign edge patterns using the centralizer equation and discard non-orientable orbitals using the commutator condition above. Empirically measure activation-norm ratios, backpropagated gradient-norm ratios, sparse-kernel wall-clock time, and validation loss. (4) First cheap experiment: train a six-layer width-512 residual MLP on CIFAR-10, replacing every second dense mixer with a CGW mixer at w in {16,32,64}. Compare against the dense baseline and a random signed sparse matrix with identical sparsity. Keep optimizer, initialization, and parameter count otherwise fixed. Record accuracy, loss versus optimizer step, gradient-norm variance, mixer FLOPs, parameter memory, and actual examples per second. The idea succeeds if it matches or exceeds random sparse accuracy, remains near-isometric across depth, and provides lower measured mixing cost; a concrete target is at least 2 times fewer mixing multiply-adds without an accuracy drop larger than 0.5 percentage points.

## Disclaimer

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