Linearity of PCA

Question

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?

Answer 1

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.)

Answer 2

"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".

Answer 3

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