CRT Matrix Factorization

E26: Netflix/Amazon/Spotify. CC0.

Recommendation engines use matrix factorization to predict what users will like. Standard approach: factorize one huge matrix. CRT approach: decompose into 6 tiny independent matrices, factor each in its own channel, reconstruct via CRT. Block-diagonal: zero cross-channel gradient leakage. L=11 = free trust verification.

How It Works

CRT Factorization Theorem
A ratings matrix R in Z/12612600 decomposes into 6 channel matrices R_D (mod 8), R_K (mod 9), R_E (mod 25), R_b (mod 49), R_L (mod 11), R_G (mod 13). Factor each independently. Predicted rating = CRT reconstruction from 6 channel predictions. Independence: error in one channel cannot corrupt another. The 490 split separates data channels (D,E,b) from verification channels (K,L,G).
6 factorizations
CRT decomposition
One NxM matrix becomes 6 tiny NxM matrices with values in Z/8..Z/13.
Block-diagonal
Zero gradient leak
Each channel trains independently. No cross-channel interference.
490 split
Data + verification
DEAD={D,E,b} channels carry preference. ALIVE={K,L,G} verify trust.
L=11 ECC
Free anomaly detection
Poisoned ratings deviate in L channel. Detection without extra computation.

Try It

Random seed:

Generates a 6x8 sparse ratings matrix. CRT decomposes, factors 6 channels independently, predicts missing entries. Gold = predicted. Green = known.

Batch Test

CRT vs Standard Matrix Factorization

DecompositionStandard: one monolithic NxM matrixCRT: 6 independent matrices in Z/8..Z/13ComplexitySVD: O(min(m,n)^2 * max(m,n))CRT: 6 x O(mnk) with k in {8,9,25,49,11,13}ParallelismMust synchronize across full gradient6 channels = 6 independent workersError detectionSeparate validation neededL=11 channel detects poisoned ratings for freePrivacyFull preference matrix exposed490 split: 3 DEAD channels hold data, 3 ALIVE verifyPatent statusNetflix/Amazon collaborative filtering patentsCC0. Public domain. Forever.

This work is and will always be free.
No paywall. No copyright. No exceptions.

If it ever earns anything, every cent goes to the communities that need it most.

This sacred vow is permanent and irrevocable.
— Anton Alexandrovich Lebed

Source code · Public domain (CC0)

Contributions in equal measure: Anthropic's Claude, Anton A. Lebed, and the giants whose shoulders we stand on.

Rendered by .ax via WASM DOM imports. Zero HTML authored.