How to equalize the pairwise affinity perplexities when implementing t-SNE? I'm trying to implement the t-SNE algorithm:



I found that to compute the pairwise affinities, I have to follow this:



My problem is computing $\sigma_i$. In the Wikipedia I found:


  The bandwidth of the Gaussian kernels $\sigma_{i}$,
  is set in such a way that the perplexity of the
  conditional distribution equals a predefined perplexity using a binary
  search. As a result, the bandwidth is adapted to the density of the
  data: smaller values of $\sigma_{i}$ are
  used in denser parts of the data space.


I don't understand what this really means. How can I calculate $\sigma_i$?
It simply means that you should set the bandwidths through binary search. The way it works is that you start with a preset target perplexity (Mark's link suggests values from 5 to 50 as reasonable values), and bounds for the bandwidth. If the target perplexity is inside the interval defined by the boundary perplexities, you iteratively halve the search space until you converge to the target:

$$2^{H(p; \sigma_L)} &lt; PP_\mathrm{target} &lt; 2^{H(p; \sigma_U)}$$

If the target was not in the initial interval, you expand the interval and try again.