Supplementary material: - icml12-proofs.pdf: a convergence rate derivation. - ee_COIL_multiple_runs.gif: GIF animation of 50 runs of the EE algorithm with 10 manifolds from the COIL-20 data set (N=720) initialized randomly close to 0. The affinities are constructed with a perplexity of 20. The animation shows the decrease of the objective function vs the number of iterations with time. Our preferred method (SD) is able to decrease the objective function to the lowest value among all methods. In addition, the method is able to take far more iterations than methods that have to solve a linear system (SD-). - ssne_COIL_multiple_runs.gif: as ee_COIL_multiple_runs.gif but for s-SNE. - ee_homotopy.gif: GIF animation of the homotopy optimization for the EE method with 10 manifolds from the COIL-20 data set (N=720). Most of the methods converge to the same embedding. However, the runtime required to achieve that result is dramatically different depending on each method. Again, SD works very well. - ee_MNIST.gif: GIF animation of the EE run on the subset of MNIST data set with N=20000 random images of digits from 0 to 9. The runtime is limited to 60 minutes for all the methods. The spectral direction (SD) is the only method that is able to produce a reasonable embedding that separates most of the digits already after 15 minutes of runtime. - tsne_MNIST.gif: as ee_MNIST.gif but for t-SNE. All these animations may be seen with a web browser or with specialized GIF image viewers.