32
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
21
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ 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$. $\endgroup$
    – shadowtalker
    Nov 18, 2014 at 18:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Roman
    Nov 19, 2014 at 7:53
  • $\begingroup$ Your definition explains why PCA and Factor analysis are linear dimensionality reduction methods, but it can't explain why NNMF (non-negative matrix factorization) is a linear dimensionality reduction method (NNMF usually noted as linear dimensionality reduction, see here for example). In NNMF we do the following projection $X \to W H$, so there is no $X$ matrix at the right side at all (unlike PCA, which do $X \to XW$). $\endgroup$
    – Rodvi
    Mar 5, 2021 at 11:15
56
$\begingroup$

A picture is worth a thousand words:

PCA vs Isomap

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Does this mean that we can define methods of linear dimensionality reduction as methods which map original high-dimensional points to the set of points which lie on some linear low-dimensional manifold? And similarly define methods of nonlinear dimensionality reduction as methods which map original high-dimensional points to the set of points which lie on some non-linear low-dimensional manifold? $\endgroup$
    – Rodvi
    Mar 5, 2021 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.