How to understand “nonlinear” as in “nonlinear dimensionality reduction”?

I am trying to understand the differences between the linear dimensionality reduction methods (e.g., PCA) and the nonlinear ones (e.g., Isomap).

I cannot quite understand what the (non)linearity implies in this context. I read from Wikipedia that

By comparison, if PCA (a linear dimensionality reduction algorithm) is used to reduce this same dataset into two dimensions, the resulting values are not so well organized. This demonstrates that the high-dimensional vectors (each representing a letter 'A') that sample this manifold vary in a non-linear manner.

What does

the high-dimensional vectors (each representing a letter 'A') that sample this manifold vary in a non-linear manner.

mean? Or more broadly, how do I understand the (non)linearity in this context?

Dimensionality reduction means that you map each many-dimensional vector into a low-dimensional vector. In other words, you represent (replace) each many-dimensional vector by a low-dimensional vector.

Linear dimensionality reduction means that components of the low-dimensional vector are given by linear functions of the components of the corresponding high-dimensional vector. For example in case of reduction to two dimensions we have:

[x1, x2, ..., xn] ->  [f1(x1, x2, ..., xn), f2(x1, x2, ..., xn)]


If f1 and f2 are (non)linear functions, we have a (non)linear dimensionality reduction.

• Just to be clear, you should add that "linear" in this context means $f(a\cdot x + b) = a\cdot f(x) + b$, or some generalized equivalent. For instance, each PCA dimension is a "linear combination" of the inputs: $w_1x_1 + \dots + w_nx_n$. – shadowtalker Nov 18 '14 at 18:23
• What I mean is: $f_i = f_i (x_1, \dots, x_n) = c^{(i)} + \omega^{(i)}_1 x_1 + \dots \omega^{(i)}_n x_n$, where $f_i$ and $x_i$ are the components of the low- and high-dimensional vectors, respectively (and I think it is not what you mean). I thought that the problem was not in the understanding what a linear function is but in where the linearity appears. – Roman Nov 19 '14 at 7:53

A picture is worth a thousand words:

Here we are looking for 1-dimensional structure in 2D. The points lie along an S-shaped curve. PCA tries to describe the data with a linear 1-dimensional manifold, which is simply a line; of course a line fits these data quite bad. Isomap is looking for a nonlinear (i.e. curved!) 1-dimensional manifold, and should be able to discover the underlying S-shaped curve.