BLAS/LAPACK not installed: How to install it?
Ubuntu doesn't have a binary distribution of either cblas or openblas, which are required for tsne according to their github. However, ATLAS, which is available on Ubuntu, comes with precompiled cblas.
In Ubuntu, debian, that should work with:
apt-get install libatlas-base-dev https://launchpad.net/ubuntu/+source/atlas
If you need to have different compiler options, you'll have to build openblas yourself.
And check that you get libcblas.a in /usr/lib
Edited: Corrected package name.