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(...)
