9

Considering the number of features constant, Barnes-Hut t-SNE has a complexity of $O(n\log n)$, random projections and PCA have a complexity of $O(n)$ making them "affordable" for very large data sets.

On the other hand, methods relying on Multidimensional scaling have a $O(n^2)$ complexity.

Are there other dimension reduction techniques (apart from trivial ones, like looking at the first $k$ columns, of course) whose complexity is lower than $O(n\log n)$ ?

amoeba
  • 93,463
  • 28
  • 275
  • 317
RUser4512
  • 9,226
  • 5
  • 29
  • 59

2 Answers2

6

An interesting option would be exploring neural-based dimensionality reduction. The most commonly used type of network for dimensionality reduction, the autoencoder, can be trained at the cost of $\mathcal{O}(i\cdot n)$, where $i$ represents the training iterations (is an hyper-parameter independent of training data). Therefore, the training complexity simplifies to $\mathcal{O}(n)$.

You can start by taking a look at the 2006 seminar work by Hinton and Salakhutdinov [1]. Since then, things have evolved a lot. Now most of the atention is attained by Variational Autoencoders [2], but the basic idea (a network that reconstructs the input at its output layer with a bottleneck layer in-between) remains the same. Note that, as opposed to PCA and RP, autoencoders perform nonlinear dimensionality reduction. Also, as opposed to t-SNE, autoencoders can transform unseen samples without the need to retrain the whole model.

On the practical side, I recomend taking a look at this post, which gives details on how to implement different types of autoencoders with the wonderfull library Keras.

[1] Hinton, G. E., & Salakhutdinov, R. R. (2006). Reducing the dimensionality of data with neural networks. science, 313(5786), 504-507.

[2] Kingma, D. P., & Welling, M. (2013). Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114.

Daniel López
  • 5,164
  • 2
  • 21
  • 42
  • 1
    technically you do *not* have to retrain the model for new samples with t-SNE using this particular approach: https://lvdmaaten.github.io/publications/papers/AISTATS_2009.pdf – bibliolytic Nov 21 '17 at 13:23
  • Sure. The author also suggested training a multivariate regressor to predict the map location form input data samples as a potential approach. In the paper you mention the author trains a neural network to directly minimize the t-SNE loss. However, in both cases you have to define an explicit model or function to map data points to te resulting space, so it has to be powerful enough (enough layers/neurons) to learn the embedding, but not too much to avoid over-fitting... It kind of sacrifices some of the usability of standard t-SNE. – Daniel López Nov 22 '17 at 14:23
  • No disagreement there, I just think it's a bit inaccurate to contrast autoencoders and t-SNE as you do in your answer, seeing as t-SNE can be used as a loss for dimensionality reduction – bibliolytic Nov 22 '17 at 14:27
  • Although now that I read again, a question: can we actually say that neural networks are $\mathcal{O}(n)$, seeing as they are not guaranteed to actually converge? Big-O notation is worst-case bounds, right? – bibliolytic Nov 22 '17 at 14:29
  • I did not wanted to include that in the answer since computing the t-SNE loss when training a network takes $\mathcal{O}(m^2)$ time where $m$ is the mini-batch size. – Daniel López Nov 22 '17 at 14:36
  • ah that makes sense – bibliolytic Nov 22 '17 at 14:38
0

Besides the already mentioned autoencoders, one can try exploiting Johnson-Lindenstrauss' lemma with random projections or random subspace methods. Random projections are $\mathcal{O}(k d N)$, with $N$ the number of samples of dimension $d$ and $k$ the target dimension, cf [1].

A bit of googling will get you some very recent results, in particular for sparse datasets.

[1] Random projection in dimensionality reduction: applications to image and text data.

Miguel
  • 549
  • 3
  • 6