CRT Matrix Factorization

Netflix/Amazon/Spotify patents. CC0 alternative.

Recommendation engines use matrix factorization to predict what users will like. Standard approach: factorize one huge matrix. CRT approach: decompose into 7 tiny independent matrices (mod 8, 9, 25, 49, 11, 13, 17), factor each in its own channel, reconstruct via CRT over Z/214,414,200. Block-diagonal: zero cross-channel gradient leakage. Three parity channels (mod 11, 13, 17) give free trust verification.

How It Works

CRT Factorization Theorem
A ratings matrix R in Z/214,414,200 decomposes into 7 channel matrices: mod 8, mod 9, mod 25, mod 49, mod 11, mod 13, mod 17. Factor each independently. Predicted rating = CRT reconstruction from 7 channel predictions. Independence: error in one channel cannot corrupt another. Three data channels {mod 8, mod 25, mod 49} carry preference. Four parity channels {mod 9, mod 11, mod 13, mod 17} verify trust.
7 factorizations
CRT decomposition
One NxM matrix becomes 7 tiny NxM matrices with values in Z/8..Z/17.
Block-diagonal
Zero gradient leak
Each channel trains independently. No cross-channel interference.
3+4 split
Data + verification
3 data channels carry preference. 4 parity channels verify trust.
Triple parity
Free anomaly detection
Poisoned ratings deviate in parity channels (mod 11, 13, 17). Detection without extra computation.

Try It

Random seed:

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

Batch Test

CRT vs Standard Matrix Factorization

DecompositionStandard: one monolithic NxM matrixCRT: 7 independent matrices in Z/8..Z/17ComplexitySVD: O(min(m,n)^2 * max(m,n))CRT: 7 x O(mnk) with k in {8,9,25,49,11,13,17}ParallelismMust synchronize across full gradient7 channels = 7 independent workersError detectionSeparate validation neededmod-11, mod-13, mod-17 detect poisoned ratings for freePrivacyFull preference matrix exposed3 data + 4 parity channels. Share parity only.Patent statusNetflix/Amazon collaborative filtering patentsCC0. Public domain. Forever.

Source code · Public domain (CC0)

Report issue

.ax source compiled to WASM via self-hosting compiler. Zero HTML authored.