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
- 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).
- 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.