# linear versus nonlinear dimensionality reduction techniques [duplicate]

I was going through a short tutorial on dimensionality reduction techniques. Some of these techniques are linear while others are non-linear. What is the distinction between them? Why the terms 'linear' and 'non-linear'?

## marked as duplicate by amoeba, kjetil b halvorsen, Michael Chernick, Silverfish, JohnDec 21 '17 at 2:12

Linear vs. non-linear are two different types of transformations. Here gives the details of the linear transformation.

A linear transformation between two vector spaces $V$ and $W$ is a map $T:V->W$ such that the following hold:

1. $T(v_1+v_2)=T(v_1)+T(v_2)$ for any vectors $v_1$ and $v_2$ in $V$, and
2. $T(\alpha v)= \alpha T(v)$ for any scalar alpha.

For example, in dimension reduction domain, principal component analysis (PCA) is a linear transformation. And kernel PCA is a non-linear one.

Here are details (thanks @whuber for the suggestion).

Suppose we have data matrix $X$ and the Singular-value decomposition of $X$ is $X=UDV^T$, the PCA transformation is just a matrix multiplication on $X$, which is $XV$.

We can show the matrix multiplication is linear algebraically: Define $T(X)=XV$ (the transformation of $X$ is multiply $X$ by matrix $V$), then we know $(X_1+X_2)V=X_1V+X_2V$ and $\alpha X V=\alpha XV$.

Intrusively, you can think about linear transformation is shifting and stretching the data, and non-linear transformation will make more dramatic changes on data such as making data "inside out".

If we visualize the transformation, linear transformation looks like this

Nonlinear transformation looks like this

Picture source

http://mathinsight.org/media/image/source/linear_transformation_2d_m1_m1_1_3.svg

http://2.bp.blogspot.com/_slrAR0IXTL0/TF-OZaNbRCI/AAAAAAAAAUo/SdYS3hXd4MI/s1600/figure.png

• Could you clarify how PCA is a linear transformation in the algebraic sense described in this answer? You should be able to describe the vector spaces that are its domain and codomain and, given bases for each, exhibit the matrix corresponding to "PCA." – whuber Dec 20 '17 at 19:04
• @whuber thanks for the suggestion, could you help me to check if I made some mistake? – hxd1011 Dec 20 '17 at 19:25
• There's a subtle problem: since $V$ depends on $X$, the mapping $X\to XV$ is not necessarily linear. If we explicitly recognize this dependence by writing $V(X)$, you need to show that $(\alpha X + \beta Y)V(\alpha X + \beta Y)=\alpha XV(X) + \beta YV(Y)$ for all scalars $\alpha,\beta$ and comparable matrices $X,Y$. – whuber Dec 20 '17 at 21:06
• The way you wrote PCA assumes zero mean. If that's not true, then the learned mapping from the input space to the lower dimensional space requires subtracting the mean, and your conditions for linearity don't hold. – user20160 Dec 21 '17 at 5:29