# What is the proof that non-linearly separable data can't become linearly separable with the results of PCA?

Give a non-linearly separable dataset $$X,$$ I want to proof that after performing PCA on it, the resulting dataset is guaranteed to be still non-linearly separable. I think we could argue that we still use the eigenvectors of the original feature space to describe the transformed feature space, and if it wasn't possible to find a linear combination for a hyperplane, it's also not possible to do so in the truncated space, but not exactly sure if that's the right approach. A second approach of mine was to try to model PCA as a linear transformation altogether using a matrix for the transformation $$J(XW+b)$$ and thinking about the hyperplane in terms of $$XW+b>0$$ or $$XW+b<0,$$ like in SVM. Unfortunately i didn't get ahead with this approach either (didn't know how to show that the sign for each datapoints stays the same after performing the J matrix), so would be interested in how to solve this.

Proof by ChatGPT (not sure if correct):

• Please explain to us how your chatbot can multiply a "datapoint with dimensionality D" by a "matrix with shape 1 x N"!! You can be absolutely sure that junk is not correct (and quite confident that it's pure BS). You will be better off reviewing the relevant definitions and constructing a valid, understandable argument that reflects the basic intuition.
– whuber
Commented Jan 21, 2023 at 22:12
• ChatGPT is not even close to reliable: its "proofs" are parts of conversations in a style of proofs, but there is no reason to believe any of its steps are actually correct Commented Jan 21, 2023 at 22:33
• What makes you think ChatGPT provided you a proof as opposed to a wall of text derived by pattern matching? Commented Jan 21, 2023 at 23:45
• I’m voting to close this question because I don't think we should be vetting ChatGPT "proofs", although I do realize there's some public service in attempting to explain to posters that ChatGPT does not actually construct proofs except by accident. Commented Jan 21, 2023 at 23:55
• @jbowman, while I hold with your opinion, I think the present meta CV discussion caters to the case. Commented Jan 22, 2023 at 8:59

This formulation of the question is presented as a way to expose the relevant concepts of separability and PCA.

### Separability

Suppose $$S$$ and $$X$$ are sets and that $$X = Y\cup Z$$ partitions $$X;$$ that is, $$Y\cap Z = \emptyset;$$ and let $$\mathscr F$$ be a set of $$X$$-valued functions defined on $$S.$$

Let us say that a pair $$\{A,B\}$$ where $$A\subset S$$ and $$B\subset S$$ is $$\mathscr F$$-separable when there exists $$f\in\mathscr F$$ for which either $$f(A)\subset Y$$ and $$f(B)\subset Z$$ or $$f(A)\subset Z$$ and $$f(B)\subset Y.$$

(This language assumes $$X=Y\cup Z$$ is understood in the context. Otherwise, we would use a more specific expression like "$$(\mathscr F, Y\cup Z)$$-separable.")

Linear separability

Let $$S=\mathbb W$$ be a real vector space. Take $$\mathscr F$$ to be the set of translates of linear forms. That is, $$f\in\mathscr F$$ means $$f$$ is a real-valued function on $$\mathbb W$$ and there exists a scalar $$b$$ and a linear form (aka covector) $$\phi$$ for which $$f(w)=\phi(w)+b$$ for all $$w\in\mathbb W.$$ Thus $$X=\mathbb R.$$ Taking $$Y$$ to be the positive numbers and $$Z$$ to be the non-positive numbers is how linear separability is often defined. If your definition differs, you will want to pause here to verify that it's equivalent to this one.

### PCA

Given a probability distribution $$\Pr$$ on a vector space $$\mathbb W$$ (together with other information: namely, an inner product), PCA finds a basis of $$\mathbb W$$ determined by that distribution. That's all we need to know about PCA for this question.

### The question

Given samples $$\mathscr A$$ and $$\mathscr B$$ of a real vector space $$\mathbb W,$$ let $$\Pr$$ be the empirical distribution of the combined sample. (That is, it assigns equal weight to every vector in the combined sample. Such a distribution always exists provided the combined sample is not empty.) Let $$A\subset \mathbb W$$ be the support of $$\mathscr A$$ (the set of distinct values in the sample) and $$B\subset \mathbb W$$ be the support of $$\mathscr B.$$

Prove that if $$\{A,B\}$$ is not linearly separable and you apply PCA to the combined sample $$(\mathscr A,\mathscr B),$$ then $$\{A,B\}$$ is still not linearly separable.

There is nothing to show.

The reason is that the linearity of a form $$\phi$$ does not depend on choosing a basis for a vector space. How is this standard fact proven? By showing that (1) a change of basis effects a linear transformation of coordinates and (2) composing such a linear transformation with a linear function is still a linear function. If you feel you need to demonstrate this to satisfy your professor, that would be fine.

You might be working with a slightly different concept of PCA in which only the first few principal vectors are retained. By using only a few of the principal vectors you are limiting the set of linear forms in $$\mathscr F$$ you are willing to use after applying PCA (you have thrown away all those defined on the unused principal vectors and vanishing on the selected principal vectors). That only makes it harder to achieve separability after applying PCA.

• I remember you once argued that we can have principle components beyond the dimensions of the original matrix. In that case PCA might make the data seperable? Commented Jan 29, 2023 at 14:20
• @Sextus It would depend on how you mapped the data to the additional PCs. As I recall, that argument was merely that we can always extend a partial basis to a basis. In that case, the loadings on the additional PCs would all be zero and nothing would change about separability. The argument here shows you would need a nonlinear map from the data to the new components to achieve separability -- and that is exactly the idea behind the kernel trick etc.
– whuber
Commented Jan 29, 2023 at 14:46

PCA is a linear transformation (Linearity of PCA), and a composition of linear transformations (effectively the same as a product of matrices representing those linear transformations) is itself a linear transformation.

Say:

Let

• $$x$$ is your original data
• and $$y = Ax$$ is the data after some PCA transformation

If

• $$z = By$$ is a linear transformation of that data $$y$$, which seperates the data

Then

• $$z = BAx$$
• and thus there is also a linear transformation, the composition $$(B \circ A)$$ that seperates the data $$x$$.

The above lines prove that if the PCA transformed data is linearly seperable, then also the non-PCA transformed data will be seperable.

By contraposition we also have that

If the non-PCA transformed data is not linearly seperable, then also the PCA transformed data will be not be seperable.