# Kac-rotated fast projection

- ID: 2454
- Canonical URL: https://synthcore.org/idea/2454/kac-rotated-fast-projection
- API JSON: https://synthcore.org/api/idea/2454.json
- API Markdown: https://synthcore.org/api/idea/2454.md
- Verification status: failed_benchmark
- Source: [arXiv:2608.17374](https://arxiv.org/abs/2608.17374)
- Category: architecture
- Solves: speedup, memory, accuracy
- ML areas: mlp, embedding, inference-speedup, initialization
- Math tags: lie-groups, representation-theory, probability, random-matrix, linear-algebra
- Ratings: usefulness 7/10; difficulty 4/10; novelty 5/10

## Idea description

Replace a dense Haar or Gaussian random projection with a streamed product of random two-coordinate rotations followed by coordinate subsampling. The transform is exactly orthogonal before subsampling, requires only a list of rotation triples, and the paper's pseudo-mixing result predicts that degree-two statistics relevant to norm preservation and Johnson–Lindenstrauss embeddings become Haar-like after only O(n polylog(n)) rotations.

## Mathematical statement

Kac's walk starts from X_0 in \mathcal{SO}(n) and updates by X_{t+1}=R_{i_tj_t}(    heta_t)X_t, where \mathcal{SO}(n)=\{X\in\mathbb{R}^{n    imes n}:X^TX=I_n,\det X=1\}, (i_t,j_t) is uniform over pairs 1\leq i<j\leq n, and     heta_t\sim\mathrm{Unif}[0,2\pi). The two-coordinate rotation is R_{ij}(    heta)=I_n+(\cos    heta-1)(E_{ii}+E_{jj})+\sin    heta E_{ij}-\sin    heta E_{ji}, with E_{ab} the matrix having a one at (a,b) and zero elsewhere. Each R_{ij}(    heta) is orthogonal and changes only coordinates i and j. The paper proves that the first k columns mix in time nk\,\mathrm{polylog}(n), and uses a representation-theoretic argument to show that degree-k polynomials cannot distinguish a Kac matrix from Haar measure after nk^2\,\mathrm{polylog}(n) steps. For a projection whose main observables are quadratic, use k=2: Q_T=R_{i_Tj_T}(    heta_T)\cdots R_{i_1j_1}(    heta_1), y=\sqrt{n/m}\,P_mQ_Tx, where P_m selects m coordinates. The relevant degree-two statistic is \|P_mQ_Tx\|_2^2, a quadratic polynomial in entries of Q_T; pseudo-mixing predicts Haar-like norm behavior at substantially fewer steps than full Haar mixing.

## Key formulas

- $$X_{t+1}=R_{i_tj_t}(\theta_t)X_t$$
- $$R_{ij}(\theta)=I_n+(\cos\theta-1)(E_{ii}+E_{jj})+\sin\theta\,E_{ij}-\sin\theta\,E_{ji}$$
- $$Q_T=R_{i_Tj_T}(\theta_T)\cdots R_{i_1j_1}(\theta_1),\qquad y=\sqrt{\frac{n}{m}}\,P_mQ_Tx$$
- $$\|P_mQ_Tx\|_2^2=\sum_{r=1}^{m}(e_r^TQ_Tx)^2$$

## Implementation notes

Integrate this at a location currently using a dense fixed random projection, such as an embedding bottleneck, random feature map, sketching layer, or fast-JL preprocessing stage. Store a seed or an explicit list of T triples (i_t,j_t,theta_t), rather than an n-by-n matrix. For each input vector x, initialize z=x and execute: for t=1,...,T, read a=i_t, b=j_t, c=cos(theta_t), s=sin(theta_t), set u=z[a] and v=z[b], then set z[a]=c*u+s*v and z[b]=-s*u+c*v; finally return y=sqrt(n/m)*z[indices]. This computes multiplication by Q_T followed by P_m, up to the chosen left/right multiplication convention. For a batch, vectorize each pair update over the batch dimension. On GPU, benchmark both the literal sequence and blocks of disjoint pairs; the latter may improve memory coalescing but must be evaluated separately because reordering rotations changes Q_T. The transform itself is computed exactly from the Kac update. Estimate the useful pseudo-mixing threshold empirically by sweeping T over {0.25n, 0.5n, n, 2n, 4n} multiplied by a small logarithmic factor. First test CIFAR-10 or TinyImageNet with n=1024 and m=256, comparing dense Gaussian, dense Haar, SRHT, and Kac projections inside the same MLP. Measure projection wall-clock time, storage bytes, pairwise distance distortion on 10,000 held-out examples, and downstream accuracy after identical training. A useful result is at least 2x lower projection cost and much lower storage, with median and 95th-percentile distortion within 10% of Haar or SRHT and accuracy loss below 1 percentage point. Varying T should show quadratic statistics stabilizing near the predicted O(n polylog n) regime.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: inconclusive
- Verdict: Built an exact streamed Kac-rotation projection and numerically verified the core mechanism. Orthogonality stayed at 1.33e-15 defect, the measured quadratic mean matched the analytic relaxation within 0.0159 absolute error, and quadratic-statistic spread approached the Haar reference by 8n rotations. The mechanism is real, but the literal Python implementation was far slower than dense BLAS, so no speed win was demonstrated; storage was 4x smaller than a full dense orthogonal matrix.

### Mechanism check

- Verdict: Built an exact streamed Kac-rotation projection and numerically verified the core mechanism. Orthogonality stayed at 1.33e-15 defect, the measured quadratic mean matched the analytic relaxation within 0.0159 absolute error, and quadratic-statistic spread approached the Haar reference by 8n rotations. The mechanism is real, but the literal Python implementation was far slower than dense BLAS, so no speed win was demonstrated; storage was 4x smaller than a full dense orthogonal matrix.
- Confidence: 8/10
- Limitations: Only a small n=64 NumPy toy experiment was run; no GPU/fused kernel, MLP training, CIFAR accuracy, large-n scaling, SRHT comparison, or end-to-end production benchmark was tested. Runtime is dominated by Python sequential-loop overhead and should not be interpreted as the performance of a fused Kac implementation.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.26985
- Paired wins: 2/8
- Benchmark verdict: no significant win

## Artifacts

- [REPORT.md](https://synthcore.org/code/950/REPORT.md)
- [bench_report.json](https://synthcore.org/code/950/bench_report.json)
- [report.md](https://synthcore.org/code/950/report.md)
- [report_bench_2026-09-01T164930.md](https://synthcore.org/code/950/report_bench_2026-09-01T164930.md)
- [results.json](https://synthcore.org/code/950/results.json)
- [run_experiment.py](https://synthcore.org/code/950/run_experiment.py)
- [stage2_bench.py](https://synthcore.org/code/950/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/950)

## Disclaimer

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