Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

By Cover's Theorem(1965), it is possible to make patterns separable if the original feature space is transformed to a higher-dimensional space.

Think of the XOR problem.

enter image description here

It is not possible to separate the two classes with a hyperplane. One trick is to use Neural Networks, which transformed the feature space linearly to a higher dimensional space. Another is the kernel trick with non-linear transformation.

But can we make the classes separable only using a low-dimensional linear transformation, i.e. $R^2 \rightarrow R^2$ Linear Transformation? I think I cannot find one. Is there any way to prove that such a transformation does not exist?

share|cite|improve this question
Neural networks aren't linear either; the activation function is typically sigmoidal. In any case, as pzf's answer shows, if neural networks were linear, they wouldn't be able to solve the XOR problem no matter how high-dimensional you made the feature space. – Rahul Jun 26 '12 at 5:32
up vote 1 down vote accepted

Two sets of vectors $x_i$ and $y_i$ are linearly separable if there is some vector $w$ and a constant $k$ such that $w\cdot x_i \ge k$ and $w\cdot y_i < k$. You are asking if there is some linear (or affine, doesn't matter) transformation that could make two sets that are not linearly separable linearly separable.

Suppose $M$ is such a transformation. Note that $w\cdot (M x_i)=(M^T w)\cdot x_i$, where $M^T$ is the adjoint/transpose of $M$. Then clearly if $M$ allows you to separate $Mx_i$ and $My_i$ with vector $w$, the original sets were separable using $M^T w$. No linear transformation of that sort will work. Alternatively, hyperplanes will still be hyperplanes under linear transformations (of full rank).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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