"smart" unsupervised dimensionality reduction and feature selection for "large" problems

If your data matrix is sparse (which I'd expect for a text corpus) and you don't want to do full eigen-decomposition, you can try using Lanczos algorithm which is an iterative algorithm for finding the top K eigenvectors. Matlab has it implemented via the eigs/svds functions that can give you top K eigenvectors (or even smallest ones if you need).

There also exist a number of other packages such as SVD/LSA which you could use. Besides, if you want to try a probabilistic version, there is the expectation maximization (EM) algorithm based latent semantic analysis which can be reasonably fast. Here is a matlab implementation. Even PCA can be solved using EM. See the Wikipedia entry on PCA.

Another option could be to use kernel PCA which has two-fold benefits: (1) it can learn nonlinear projections and (2) it can be very efficient if the number of features D far exceeds the number of examples N because it is based on the eigen-decomposition of the NxN data kernel matrix rather than the DxD covariance matrix.

Ted Dunning has told me that his technique for fast dimensionality reduction is a random projection followed by SVD. YMMV.

Random projections alone are not the same as a random projection based SVD decomposition method. See the arxiv link I posted just a bit ago.

Also, keep in mind that beyond a very modest decrease in singular values, you are only going to get very fancy random numbers out of any SVD algorithm. Real data tends to have long tail x long tail structure which means that the singular values are likely to decay very quickly. This often means that only a few (at most 10-20) eigenvalues are large enough for the decomposition of a noisy matrix to justify extracting.

There have been a number of experiments with, say LSI, that showed a much large dimension for the reduced space gave better results. My experience that the reduced dimensionality should, indeed, be larger than 10 for most problems, but that replacing eigenvectors 11..300 with random numbers works just as well as 300 supposedly real eigenvectors.

The number of latent factors required varies widely with problem. The LSI team routinely used 300. HNC Software also used 300 with Convectis. At the other end, Menon and Elkan got very good results on recommendation problems with 5 latent factors in their latent factor log-linear model (LFL).

It depends somewhat on which approaches you're prepared to consider for working with the data afterwards.

If you're not averse to offsetting some of the time gains from preprocessing the data by random projection with, say, boosting an ensemble of weak learners to reduce the impact of information loss and variability in the randomly projected data then you can still probably expect good results (especially since your text data are likely to be reasonably sparse, so compressed sensing results imply that most of the information from the full dimensional data is retained following RP). In (Bingham, 2001) the authors got good results from RP on text data. In (Fradkin and Madigan, 2003) RP was found to be competitive, on average, with PCA for a variety of classifiers on a range of standard datasets.

More recently we presented some theory at KDD 2010 (Durrant and Kaban, 2010) that gives guarantees on classification error for RP combined with Fisher's Linear Discriminant (on average, over the random picks of projection matrix) when the projection dimensionality is only logarithmic in the number of classes. We found that the classification error increases nearly exponentially as the projected dimension gets smaller, and (unsurprisingly) the variability of the classifier performance also increases as the projected dimension drops. Nonetheless, one can still expect better than chance performance from the projected classifier in this setting, so an ensemble approach can recover the lost performance. The space complexity savings then more or less come for free.

Btw, here is some R code that implements a random projection SVD. The point here is that this is really simple to do and for sparse A, it is really, really fast. This approach is much simpler to get right than Lanczos and much easier to parallelize as well.

# SVD decompose a matrix, extracting the first k singular values/vectors
# using k+p random projection
svd.rp = function(A, k=10, p=5) {
  n = nrow(A)
  y = A %*% matrix(rnorm(n * (k+p)), nrow=n)
  q = qr.Q(qr(y))
  b = t(q) %*% A
  svd = svd(b)
  list(u=q %*% svd$u, d=svd$d, v=svd$v)
}

Specifically for text, there is a much cited work by Yang and Pedersen, " A comparative study on feature selection in text categorization" (ICML 1997). Maybe you'll find one of the methods there useful.

Also, if your data has some natural topology (like an image), you can create a very sparse dissimilarity matrix between features. Once you have this, you can apply a ward cluster on it to reduce a bit the size of the data by feature agglomeration.

My experience is that this works really well, as long as you don't agglomerate too many features. Indeed, you are agglomerating on noise as much as data. As you go higher in the Ward tree, the resulting clusters become more and more sensitive to the noise. We tend to use this technique in addition to other methods more robust, such as based on minimizing a convex function, rather than a greedy solution (see our paper for application to feature selection in brain imaging).