title: Scaling t-SNE to millions of observations in scikit-learn
body: <p>t-SNE can supposedly scale to millions of observations (see <a href="https://lvdmaaten.github.io/tsne/" rel="noreferrer">here</a>), but I'm curious how that can be true, at least in the Sklearn implementation.</p>
  
  <p>I'm trying it on a dataset with ~100k items, each with ~190 features. Now, I'm aware that I can do a first pass of dimensionality reduction with, e.g. PCA, but the problem seems more fundamental.</p>
  
  <p>t-SNE computes and stores the full, dense similarity matrix calculated for the input observations (
  I've confirmed this by looking at the <a href="https://github.com/scikit-learn/scikit-learn/blob/51a765a/sklearn/manifold/t_sne.py#L496" rel="noreferrer">source</a>). In my case, this is a 10 <em>billion</em> element dense matrix, which by itself requires 80 GB+ of memory. Extrapolate this to just one million observations, and you're looking at 8 <em>terabytes</em> of RAM just to store the distance matrix (let alone computation time...)</p>
  
  <p>So, how can we possibly scale t-SNE to millions of datapoints in the sklearn implementation? Am I missing something? The <a href="http://scikit-learn.org/stable/modules/generated/sklearn.manifold.TSNE.html" rel="noreferrer">sklearn docs</a> at least imply that it's possible:</p>
  
  <blockquote>
    <p>By default the gradient calculation algorithm uses Barnes-Hut approximation running in O(NlogN) time. method=’exact’ will run on the slower, but exact, algorithm in O(N^2) time. The exact algorithm should be used when nearest-neighbor errors need to be better than 3%. <em>However, the exact method cannot scale to millions of examples.</em></p>
  </blockquote>
  
  <p>That's my emphasis, but I would certainly read that as implying the Barnes-hut method <em>can</em> scale to millions of examples, but I'll reiterate that the code requires calculating the full distance matrix well before we even get to any of the actual t-sne transformations (with or without Barnes-hut).</p>
  
  <p>So am I missing something? Is it possible to scale this up to millions of datapoints?</p>