Scalable dimension reduction 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)$ ?
 A: 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.
A: 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.
