← All Cracked ML projects
PL-I02NOT STARTEDINTERMEDIATEMLPYTHONIMPACT ★★☆☆☆

t-SNE from scratch with FFT-interpolated gradients

Your t-SNE versus openTSNE on single-cell RNA data, scored by how many neighbourhoods are kept, not by how pretty the plot is.

EST.14 h
REWARD+300 XP
AFTERopenTSNE documentation + 1

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
final KL divergence (how badly the 2-D map's neighbour probabilities match the original ones; lower is better); fraction of each point's 10-NN (10 nearest neighbours) preserved; runtime
GOAL · KL within 2% and 10-NN preservation within 0.01 of openTSNE; ≤ 5× openTSNE's runtime at 50k points
openTSNE (same perplexity, iterations, init) · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

In NumPy, compute perplexity-calibrated sparse affinities using your kNN from PL-B09, the vector-search project. Affinities say how strongly each point is tied to each of its neighbours; perplexity calibration picks a Gaussian width per point so every point has about the same effective number of neighbours. Then compute exact O(n²) gradients. Then add an FIt-SNE-style FFT interpolation of the repulsive term: the push-apart force between all pairs of points is approximated on a grid and computed with a fast Fourier transform, which avoids the n² cost. Include early exaggeration (multiply the attractions for the first iterations so clusters form) and momentum schedules. Run on PBMC3k (2,700 blood cells), then on a 50k-point dataset where O(n²) is impossible.

VICTORY CONDITIONS

  1. KL within 2% and 10-NN preservation within 0.01 of openTSNE; ≤ 5× openTSNE's runtime at 50k points (final KL divergence (how badly the 2-D map's neighbour probabilities match the original ones; lower is better); fraction of each point's 10-NN (10 nearest neighbours) preserved; runtime).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

t-SNE
A method that places high-dimensional points on a 2-D map so that points that were neighbours stay neighbours.
Perplexity
In t-SNE, a knob that sets roughly how many neighbours each point should care about.
Repulsive term
The part of the t-SNE gradient that pushes every pair of points apart; it is the expensive all-pairs part.
FFT interpolation
Spreading points onto a regular grid so the all-pairs force can be computed quickly with a fast Fourier transform.
Early exaggeration
Making attractions artificially strong at the start of optimisation so clusters separate cleanly.

Why it rates ★★☆☆☆

Reimplementing a fast t-SNE shows numerical maturity. It is still a reproduction of a known tool.