# Sparse Weighing Mixer

- ID: 1808
- Canonical URL: https://synthcore.org/idea/1808/sparse-weighing-mixer
- API JSON: https://synthcore.org/api/idea/1808.json
- API Markdown: https://synthcore.org/api/idea/1808.md
- Verification status: unverified
- Source: [arXiv:2608.04814](https://arxiv.org/abs/2608.04814)
- Category: architecture
- Solves: speedup, stability, memory
- ML areas: mlp, transformer, initialization, inference-speedup
- Math tags: linear-algebra, combinatorics, spectral-theory, optimization
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Use enumerated weighing matrices as sparse orthogonal channel-mixing operators inside MLPs or residual blocks. Their ternary entries reduce multiplication to signed additions, while exact orthogonality prevents amplification or attenuation of feature norms; a trainable fixed-support version can recover expressivity without giving up computational sparsity.

## Mathematical statement

A weighing matrix W(m,k) is an m x m matrix with entries W_{ij} in {0,+1,-1}, exactly k nonzero entries in every row and column, and exact orthogonality WW^T = W^TW = kI_m, where m is the channel dimension, k is the weight, T denotes transpose, and I_m is the m x m identity. Therefore the normalized operator Q=W/sqrt(k) satisfies Q^TQ=I_m and ||Qx||_2=||x||_2 for every x in R^m. The paper's enumeration constructs admissible zero patterns column by column and assigns signs so that the resulting columns are orthogonal. For a larger channel dimension M=qm, use a block-diagonal matrix B=diag(W_1,...,W_q), with each W_r an m x m weighing matrix of the same weight k; then B^TB=kI_M. In a neural layer, preserve this property initially with A_0=B/sqrt(k), and optionally learn only entries on the enumerated support while regularizing A^TA toward I_M.

## Key formulas

- $$W\in\{0,\pm1\}^{m\times m},\qquad \#\{j:W_{ij}\ne0\}=\#\{i:W_{ij}\ne0\}=k,$$
- $$WW^{\mathsf T}=W^{\mathsf T}W=kI_m,$$
- $$Q=\frac{W}{\sqrt{k}}\quad\Longrightarrow\quad Q^{\mathsf T}Q=I_m,\qquad \|Qx\|_2=\|x\|_2,$$
- $$\mathcal L_{\mathrm{orth}}(A)=\frac{\lambda}{2}\|A^{\mathsf T}A-I_M\|_F^2,\qquad A_{ij}=0\ \text{whenever}\ B_{ij}=0.$$

## Implementation notes

(1) Integration point: replace one or more square dense MLP projections, preferably the value-to-hidden or hidden-to-output projection in a Transformer block, with a sparse channel mixer. For a hidden width M divisible by a catalog matrix order m, construct B=diag(W_1,...,W_q), normalize A_0=B/sqrt(k), and apply z=A x. Test three variants: fixed A=A_0; trainable A with the same zero support as B; and trainable A with the support fixed plus an orthogonality penalty.

(2) Pseudocode:
```text
# precomputation: obtain W_r in {0,+1,-1}^{m x m}, W_r W_r^T=k I_m
B = block_diag(W_1,...,W_q)
mask = (B != 0)
A = B / sqrt(k)
for minibatch (x, target):
    A_sparse = mask * A
    z = x @ A_sparse.T
    y = activation(z)
    loss = task_loss(y, target)
    if orthogonal_variant:
        loss += (lambda/2) * frobenius_norm(A_sparse.T @ A_sparse - I_M)^2
    backpropagate(loss)
    optimizer_step(A)
```
Use a sparse kernel that stores only support indices and signs; the initial fixed matrix needs only additions/subtractions, and the trainable version stores one scalar per nonzero. For the fixed variant, add a learned diagonal gain G after the mixer, z=G A_0 x, to provide inexpensive feature-wise adaptation. The paper supplies the support/sign construction, sparsity k, and normalization 1/sqrt(k); the implementation must verify the identity numerically and estimate activation variance, gradient norms, and task accuracy empirically. If no catalog is available, generate candidate k-subsets per column and retain sign assignments satisfying W^TW=kI.

(3) First cheap experiment: train a small Transformer on WikiText-2 or a CIFAR-10 MLP, replacing 25%, 50%, and 100% of dense square MLP projections with the sparse mixer. Compare a dense baseline, random sparse matrices at the same k, fixed weighing mixers, and trainable fixed-support mixers. Measure validation perplexity or accuracy at equal training steps, wall-clock time, parameter count, peak memory, and activation/gradient norm variance. Success means lower wall-clock and memory at comparable accuracy, faster or more stable early loss descent than random sparse matrices, and substantially less norm drift in the fixed or orthogonality-regularized variants.

## Disclaimer

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