High-dimensional data: What are useful techniques to know?

Question

Due to various curses of dimensionality, the accuracy and speed of many of the common predictive techniques degrade on high dimensional data. What are some of the most useful techniques/tricks/heuristics that help deal with high-dimensional data effectively? For example,

• Do certain statistical/modeling methods perform well on high-dimensional datasets?
• Can we improve the performance of our predictive models on high-dimensional data by using certain (that define alternative notions of distance) or kernels (that define alternative notions of dot product)?
• What are the most useful techniques of dimensionality reduction for high-dimensional data?

Answer 1

This is very broad question, which I think it's impossible to cover comprehensively in a single answer. Therefore, I think that it would be more beneficial to provide some pointers to relevant answers and/or resources. This is exactly what I will do by providing the following information and thoughts of mine.

First of all, I should mention the excellent and comprehensive tutorial on dimensionality reduction by Burges (2009) from Microsoft Research. He touches on high-dimensional aspects of data frequently throughout the monograph. This work, referring to dimensionality reduction as dimension reduction, presents a theoretical introduction into the problem, suggests a taxonomy of dimensionality reduction methods, consisting of projective methods and manifold modeling methods, as well as provides an overview of multiple methods in each category.

The "projective pursuit" methods reviewed include independent component analysis (ICA), principal component analysis (PCA) and its variations, such as kernel PCA and probabilistic PCA, canonical correlation analysis (CCA) and its kernel CCA variation, linear discriminant analysis (LDA), kernel dimension reduction (KDR) and some others. The manifold methods reviewed include multidimensional scaling (MDS) and its landmark MDS variation, Isomap, Locally Linear Embedding and graphical methods, such as Laplacian eigenmaps and spectral clustering. I'm listing the most of the reviewed methods here in case, if the original publication is inaccessible for you, either online (link above), or offline (References).

There is a caveat for the term "comprehensive" that I've applied to the above-mentioned work. While it is indeed rather comprehensive, this is relative, as some of the approaches to dimensionality reduction are not discussed in the monograph, in particular, the ones, focused on unobservable (latent) variables. Some of them are mentioned, though, with references to another source - a book on dimensionality reduction.

Now, I will briefly cover several narrower aspects of the topic in question by referring to my relevant or related answers. In regard to nearest neighbors (NN)-type approaches to high-dimensional data, please see my answers here (I especially recommend to check the paper #4 in my list). One of the effects of the curse of dimensionality is that high-dimensional data is frequently sparse. Considering this fact, I believe that my relevant answers here and here on regression and PCA for sparse and high-dimensional data might be helpful.

References

Burges, C. J. C. (2010). Dimension reduction: A guided tour. Foundations and Trends® in Machine Learning, 2(4), 275-365. doi:10.1561/2200000002

Answer 2

Aleksander has given a very comprehensive answer but there are a few that are sued very widely:

For dimensionality reduction, PCA is used.This, however, does only a linear transformation and for non-linear dimensionality reduction, Manifold learning is what you are looking for.

Projecting a lower dimensional data to higher dimensions can be done using kernels. You usually do this, when your classifier is unable to find a linear plane of separation in current dimension but will be able to find a linear hyperplane that separates the classes in a higher dimension. Kernels are used widely in SVM's.