Can PCA be extended to account for nonlinear dependencies? I have just learned principal component analysis, which seems to be an effective way to do dimension reduction. Now, I would like to know:
Can PCA be extended to account for nonlinear dependencies?
It seems this is possible, based on a few searches to Wikipedia, Google, ScienceDirect, etc. However, the mathematics are quite difficult.
PCA starts by finding covariance matrix $C$ of some multivariate data $X$. If I somehow replaced the entries of $C$ so that nonlinear dependencies were taken into account, would the technique then effectively become "nonlinear PCA"?
Now if I understand this correctly, it would be so, but in practise finding the entries is way too difficult --> one reverts to approximation/optimization techniques.
 A: There is a technique invented by Trevor Hastie and Werner Stuetzle called principal curves, which is a nonlinear generalisation of principal components.
From the abstract for the original paper:

Principal curves are smooth one-dimensional curves that pass through the middle of a p-dimensional data set, providing a nonlinear summary of the data. They are nonparametric, and their shape is suggested by the data. The algorithm for constructing principal curves starts with some prior summary, such as the usual principal-component line. The curve in each successive iteration is a smooth or local average of the p-dimensional points, where the definition of local is based on the distance in arc length of the projections of the points onto the curve found in the previous iteration.

Some links:
http://www.iro.umontreal.ca/~kegl/research/pcurves/
Hastie & Stuetzle's original paper: http://www.stanford.edu/~hastie/Papers/Principal_Curves.pdf
A recent paper in the Journal of Machine Learning Research: http://jmlr.org/papers/volume12/ozertem11a/ozertem11a.pdf
A: The nonlinear dependencies you describe are Mercer kernels. A valid kernel is any function taking two observations that is continuous, symmetric and has a positive definite gram matrix. Gram and covariance are interchangeable in this context. The observations needn't be fixed-length vectors. They could be graphs, strings, variable-length time-series or any other object with which you can endow with a distance function. Some common kernels are given here, by the author of a C# Machine Learning library.
Any supervised or unsupervised algorithm expecting a design matrix can be kernelized. Linear least-squares can learn the sine function with an appropriate kernel.
Kernel PCA is well studied. A popular kernel for nonlinearizing PCA or OLS is the Gaussian Kernel, sometimes called the Radial Basis Function.
$X_{ij} = exp({\frac{-||x_i - x_j||^2} {2\sigma^2}}$)
The parameter $\sigma$ intuitively controls how fast the importance of that comparison drops off with distance.
A revolutionary algorithm for clustering small data sets defined in the paper On Spectral Clustering, is RBF Kernel PCA followed by one of the oldest clustering algorithms called K-Means.
One issue with kernels is that their explicit computation can be prohibitive for larger datasets. Indeed one of the best performing nonlinear classifiers, Support Vector Machines, scale with the algorithmic complexity of evaluating the Gram matrix.
To get around this a number of sampling techniques have been proposed to reduce your ultimate design matrix from $N \times N$ to $N \times B$, where $N$ is the number of observations and $B$ is a smaller basis s.t. your final covariance matrix $X  X^T$ is similar. This is conceptually related to a low-rank approximation that might be performed PCA. Some are kernel specific, while others are general. A simple and effective algorithm is to use Nystroem sampling on the cluster centers of k-means++ as in Improved Nystroem Low-Rank Approximation and Error Analysis
A: Nonlinear principal components are readily obtained using the MGV and MTV methods, implemented in SAS PROC PRINQUAL and the R Hmisc package's transcan function.  The basic idea is to expand each continuous variable with regression spline basis functions, and to expand categorical variables into indicator variables.  Then canonical variates are used to solve for the optimal transformations.  The goal is to have fewer components explain more variation in the system by allowing for nonlinearities.  MTV regresses the set of nonlinear terms for the variable currently being transformed against the first principal component of all (transformed) variables in an iterative fashion.  MGV regresses each individual expanded variable onto the current transformations of all the other variables, combined using multiple regression.  All this is generalized in the R homals package.  See the R psychometrics task view for more information: http://cran.r-project.org/web/views/Psychometrics.html
