Dimension reduction methods: overview of complexity For classical dimension reduction methods (PMF, PCA, SVD, t-SNE...) or some others, I need to know the complexity of efficient implementations:


*

*with $N$ vectors 

*in dimension $d$

*reduced to dimension $k$


How do you express the complexity of each (or some) of these methods?
As a special case, the complexity of an implementation for spare vectors (with average nonzero entries $c$) would be appreciated. For example, SVD has complexity $O(dcN)$.
Note: Some methods may be iterative with $i$ iterations. This is a least concern for scaling since $i$ tends to grow only logarithmically (as far as i know). Maybe you can skip it.
 A: This interesting question should be, in my opinion rephrased, because many of these methods have different implementations that can be used in different contexts (not only sparse vs dense - see this for example).
More appropriate question would be: what is the complexity of algorithms that perform these decompositions.
For basic methods you can see scikit-learn's documentation on following modules:


*

*decompositions (covers (some) algorithms for PCA, its variants, dictionary learning, Factor Analysis, ICA and NMF)

*manifold learning (covers Isomap, LLE, Hessian Eigenmaps, Spectral Embedding, LTSA and t-SNE).



Some remarks:
Spectral dimensionality reduction methods (every method mentioned from manifold except t-SNE) have the following pipeline:


*

*calculate nearest neighbors to construct graph on this data (edges correspond to distances to nearest neighbors)

*calculate distance in this graph

*decompose appropriate matrix in some way


That means their complexity depends on at least 3 factors - in scikit-learn for example you can specify the kNN method.
Randomized algorithms are used by some approximate matrix decomposition methods (this is related to random projections).
From Finding Structure in Randomness (section 1.4.1. on dense matrices, next section treats sparse matrices):

(...) standard deterministic technique for computing an approximate SVD is to perform a rank-revealing
  QR factorization of the matrix, and then to manipulate the factors
  to obtain the final
  decomposition. The cost of this approach is typically $O(kmn)$ floating-point operations, or
  flops
  , although these methods require slightly longer running times in rare
  cases.
In contrast, randomized schemes can produce an approximate SVD using only
  $O(mnlog(k) + (m+n)k^2)$ flops. The gain in asymptotic complexity is achieved by
  using a random matrix
  $\Omega$
  that has some internal structure(...)

