35
$\begingroup$

PCA is considered a linear procedure, however:

$$\mathrm{PCA}(X)\neq \mathrm{PCA}(X_1)+\mathrm{PCA}(X_2)+\ldots+\mathrm{PCA}(X_n),$$

where $X=X_1+X_2+\ldots+X_n$. This is to say that the eigenvectors obtained by the PCAs on the data matrices $X_i$ do not sum up to equal the eigenvectors obtained by PCA on the sum of the data matrices $X_i$. But isn't the definition of a linear function $f$ that:

$$f(x+y)=f(x)+f(y)?$$

So why is PCA considered "linear" if it does not satisfy this very basic condition of linearity?

$\endgroup$
  • $\begingroup$ I once wrote or heard (sorry, I can't remember where or when), that PCA "belongs to linear procedures family" because it relies on linear dependencies between variables. It uses Pearson correlation matrix and seeks for linear combinations of highest variance. $\endgroup$ – Łukasz Deryło Jul 10 '17 at 12:53
  • 4
    $\begingroup$ The nature of this question might become a little clearer by contemplating the much simpler and routine setting of ordinary least squares regression: this is the archetype of a linear statistical procedure. Nevertheless, the process of estimating least squares coefficients is a manifestly nonlinear function of the data matrix $X$, as attested by the formula $\hat\beta = (X^\prime X)^{-1}X^\prime y$. (Notice that it is a linear function of the response vector $y$.) $\endgroup$ – whuber Jul 10 '17 at 14:20
  • 4
    $\begingroup$ It might be worth remembering that f(x) = x + 1 is a "linear function" too... but it doesn't satisfy what you just said... which should explain something. $\endgroup$ – Mehrdad Jul 10 '17 at 22:22
  • $\begingroup$ That's because $(X_1+X_2)^T(X_1+X_2)\neq X_1^TX_1+X_2^TX_2$ $\endgroup$ – Gabriel Romon Jul 11 '17 at 8:22
39
$\begingroup$

When we say that PCA is a linear method, we refer to the dimensionality reducing mapping $f:\mathbf x\mapsto \mathbf z$ from high-dimensional space $\mathbb R^p$ to a lower-dimensional space $\mathbb R^k$. In PCA, this mapping is given by multiplication of $\mathbf x$ by the matrix of PCA eigenvectors and so is manifestly linear (matrix multiplication is linear): $$\mathbf z = f(\mathbf x) = \mathbf V^\top \mathbf x.$$ This is in contrast with nonlinear methods of dimensionality reduction, where the dimensionality reducing mapping can be nonlinear.

On the other hand, the $k$ top eigenvectors $\mathbf V\in \mathbb R^{p\times k}$ are computed from the data matrix $\mathbf X\in \mathbb R^{n\times p}$ using what you called $\mathrm{PCA}()$ in your question: $$\mathbf V = \mathrm{PCA}(\mathbf X),$$ and this mapping is certainly non-linear: it involves computing eigenvectors of the covariance matrix, which is a non-linear procedure. (As a trivial example, multiplying $\mathbf X$ by $2$ increases the covariance matrix by $4$, but its eigenvectors stay the same as they are normalized to have unit length.)

$\endgroup$
  • $\begingroup$ That I got 35 upvotes for this trivial answer is pretty ridiculous (and is mostly due to this thread being in the Hot Network Questions for a while). $\endgroup$ – amoeba Jul 16 '17 at 19:45
5
$\begingroup$

"Linear" can mean many things, and is not exclusively employed in a formal manner.

PCA is not often defined as a function in the formal sense, and therefore it is not expected to fulfill the requirements of a linear function when described as such. It is more often described, as you said, as a procedure, and sometimes an algorithm (although I don't like this last option). It is often said to be linear in an informal, not well-defined way.

PCA can be considered linear, for instance, in the following sense. It belongs to a family of methods that consider that each variable $X_i$ can be approximated by a function $$ X_i \approx f_Y(\alpha) $$ where $\alpha \in \mathbb{R}^k$ and $Y$ is a set of $k$ variables with some desirable property. In the case of PCA, $Y$ is a set of independent variables that can be reduced in cardinality with minimal loss in approximation accuracy in a specific sense. Those are desirable properties in numerous settings.

Now, for PCA, each $f_i$ is restricted to the form $$ f_Y(\alpha) = \sum_{i=1}^k \alpha_{i}Y_i $$ that is, a linear combination of the variables in $Y$.

Given this restriction, it offers a procedure to find the optimal (in some sense) values of $Y$ and the $\alpha_{ij}$'s. That is, PCA only considers linear functions as plausible hypotheses. In this sense, I think it can be legitimately described as "linear".

$\endgroup$
3
$\begingroup$

PCA provides/is a linear transformation.

If you take the map associated with a particular analysis, say $\mathbf{M} \equiv PCA(X_1 + X_2)$ then $\mathbf{M}(X_1+X_2) = \mathbf{M}(X_1) + \mathbf{M}(X_2)$.

The culprit is that $PCA(X_1 + X_2)$, $PCA(X_1)$ and $PCA(X_2)$ are not the same linear transformations.


As a comparison a very simple example of a process that uses a linear transformation but is not a linear transformation itself:

The rotation $D(\mathbf{v})$ that doubles the angle of a vector $\mathbf{v}$ (say a point in 2-d euclidian space) with some reference vector (say $\left[x,y\right]=\left[1,0\right]$), is not a linear transformation. For example

$D(\left[1,1\right]) \rightarrow \left[0,\sqrt{2}\right]$

and

$D(\left[0,1\right]) \rightarrow \left[-1,0\right]$

but

$D(\left[1,1\right]+\left[0,1\right]=\left[1,2\right]) \rightarrow \left[-0.78,2.09\right] \neq \left[-1,\sqrt{2}\right]$

this doubling of the angle, which involves calculation of angles, is not linear, and is analogous to the statement of amoeba, that the calculation of eigenvector is not linear

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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