7
$\begingroup$

In the article Relative Information Loss in the PCA, the authors make, at some point (in the introductory section), the following statement:

In case the orthogonal matrix is not known a priori, but has to be estimated from a set of input data vectors collected in the matrix $\underline{X}$, the PCA becomes a nonlinear operation:

$$\underline{Y} = \underline{w}(\underline{X})\underline{X}$$

Here, $\underline{w}$ is a matrix-valued function which computes the orthogonal matrix required for rotating the data (e.g., using the QR algorithm).

This statement contrasts with most statements about PCA, which is regarded as a linear transformation.

I designed a toy experiment to check the linearity (additivity property): $f(a + b) = f(a) + f(b)$.

import numpy
from sklearn.decomposition import PCA

if __name__ == '__main__':
    numpy.random.seed(42)
    m = 100
    d = 3
    X = numpy.random.normal(size = (m, d))

    # Center data
    X -= numpy.mean(X, axis = 0)

    pca = PCA(n_components = d)
    pca.fit(X)
    Y = pca.transform(X)

    # Check linearity, pca(a + b) = pca(a) + pca(b)
    for i in range(0, m):
        for j in range(0, m):
            d = pca.transform([X[i] + X[j]]) - (Y[i] + Y[j])
            assert numpy.allclose(d, numpy.array([0.0, 0.0, 0.0]))

The expression $f(a + b) - (f(a) + f(b))$, where $f = \mathrm{PCA}$, seems to be the zero vector, thus I assume the transform (PCA) is linear.

What am I missing then, that PCA is considered non-linear when the orthogonal matrix (the matrix of the principal components) is estimated from $X$ (see the quote above)?

$\endgroup$
6
  • 1
    $\begingroup$ Does this have something to do with how sklearn centers the data before transforming it? $\endgroup$
    – Aaron
    Apr 25, 2016 at 20:46
  • 1
    $\begingroup$ The only case where $w$ has a formula linear in $X$ is in one dimension. If you think otherwise, it may be due to a misunderstanding about what $w$ represents: what do you think it is? $\endgroup$
    – whuber
    Apr 25, 2016 at 21:50
  • $\begingroup$ @Aaron and amoeba, thank you for your comments. I have updated the sample code. $X$ is now centered before PCA. $\endgroup$ Apr 27, 2016 at 17:32
  • 2
    $\begingroup$ Isn't it obvious that such a function cannot be linear? In fact, how could you even make sense of adding and rescaling a set of eigenvectors (given that each eigenvector must have unit length)? $\endgroup$
    – whuber
    Apr 27, 2016 at 17:34
  • 1
    $\begingroup$ @whuber, thank you! It took me a while to understand your thoughts. Please correct me if I'm wrong: $w(\cdot)$ is a set of eigenvectors, thus the addition $w(\cdot) + w(\cdot)$ and the multiplication with a scalar $\alpha w(\cdot)$ do not make any sense. Therefore, $w$ can't be a linear transform. $\endgroup$ Apr 28, 2016 at 12:36

1 Answer 1

7
$\begingroup$

I think the confusion is due to what exactly is meant here to be linear or non-linear.

Using the notation of your quote, operation $w(X)$ maps a data matrix $X$ into a projector $P_k$ on the first $k$ principal axes of $X$. Let us be completely clear about the notation here; for simplicity let us fix $k=1$ and assume that $X$ is centered. Then $X\in\mathbb R^{n\times p}$ and $P\in \mathbb P^p \subset \mathbb R^{p\times p}$, where by $\mathbb P^p$ I mean the space of all matrices of the form $P=\mathbf{uu}^\top$ with $\mathbf u\in \mathbb R^p$ and $\|\mathbf u\|=1$.

Now:

  • Operation $w:\mathbb R^{n\times p} \to \mathbb P^p$ is non-linear.
  • Operation $P:\mathbb R^p \to \mathbb R$ is linear.

The quote talks about the $w(\cdot)$ function; it transforms a data matrix into a projection operator. It is non-linear. Your script investigates the $P(\cdot)$ function; it transforms a high-dimensional vector into a low-dimensional PCA projection, given a fixed dataset. It is linear.

So $w(\cdot)$ is a non-linear mapping into linear projections.

No contradiction.

$\endgroup$
1
  • $\begingroup$ Thank you! Still, I am not sure why there is the constraint $P=\mathbf{uu}^\top$. A matrix of that form is symmetric, right? However, as far as I know, the projection matrix learned by PCA (the matrix comprising the eigenvectors) is not necessarily a symmetric one. $\endgroup$ Apr 28, 2016 at 18:21

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.