# What is the minimal feature space dimension for an input to be linearly saparable?

I would like to know what methods exists to determine for certain feature-space-mapping-functions and a related finite number of inputs the minimal dimension of the feature space to make the inputs linearly separable?

# tl;dr

For a binary classification problem, if you have $$2n$$ data points that aren't rank-deficient, $$n$$ of each class, then they are guaranteed to be linearly separable if they have greater than or equal to $$2n-1$$ dimensions. Otherwise, they may or may not be depending on their arrangement in space.

# the gory details

To see that this is the case, note that if we have exactly $$2n-2$$ dimensions, then if none of the $$n$$ points in each class are co-($$n-1$$)-planar, they all lie on a uniquely-determined ($$n-1$$)-plane. If the two ($$n-1$$)-planes for our two classes are not parallel, then they will intersect somewhere at a $$0$$-plane (a point). We can see this by noting that each ($$n-1$$)-plane has $$n-1$$ basis vectors in ($$2n-2$$)-space. Putting the two together, we get $$2n-2$$ basis vectors, which leaves no directions in which they can be parallel.

By putting some of the points from each class in their respective hyperplanes on either side of the intersection, we obtain a situation where a single hyperplane cannot possibly separate them. In 2D, this arrangement is equivalent to the well-known xor problem.

However, if we have $$2n-1$$ dimensions, we can construct a decision surface easily using the hyperplanes previously described. Specifically, these $$n-1$$-planes no longer intersect in the same way that two lines in 2D definitely intersect unless they are parallel, but two lines in 3D definitely don't intersect unless the four points describing them are all co-planar. We can obtain a hyperplane that not only separates the data, but separates the entire (n-1)-planes containing the original data.

One way to obtain said hyperplane is to note that each of the ($$n-1$$)-planes representing our two classes of data have ($$n-1$$) basis vectors in ($$2n-1$$) space. If we put the basis vectors for these two ($$n-1$$)-planes together, we get ($$2n-2$$) vectors, which leaves one dimension in which they can be parallel. By simply taking that vector to be the normal vector of our separating hyperplane, we obtain a hyperplane capable of perfectly separating our data.

• Need a little bit help to understand this: How can (n-1)-planes intersect in only a point? Another question would be "I tried to separate the solutions of the XOR-Problem using the kernel-trick and the kernel $k(x,y)=(1+x\cdot y)^d$ and ended up in the 6-th dimension, is there a solution that can generally determine the necessary solution depending on the used kernel? Commented Sep 29, 2019 at 15:31
• @baxbear, I'm not sure about your kernel question. However, about the ($n-1$)-planes, the only intuition I can provide is this: In 2D, two non-parallel lines intersect at a point. In 3D, a line and a plane, if not parallel, intersect at a point. This is because the plane and the line have 2+1=3 dimensions. If you have 2 non-parallel planes in 3D, then you must have 1 dimension that is a linear combo of the others, and they will therefore intersect at a line. This generalizes, and a linearly independent 3-plane and a line in 4D will intersect at a point, etc.
– Him
Commented Sep 30, 2019 at 12:19
• Following your argumentation shouldn't it then be a $(n-2)$-plane at which two $(n-1)$-planes intersect and not a $0$-plane? Commented Oct 1, 2019 at 8:05
• @baxbear in $n$-space, yes, two linearly-independent ($n-1$)-planes intersect in an ($n-2$)-plane. $n-1$ vectors in the first plane, plust $n-1$ vectors in the second plane gives $2n-2$ vectors. Minus the number of "free" directions we have to move about in $n$-space ($n$), gives $n-2$.
– Him
Commented Oct 1, 2019 at 13:43