How can it be proved that if number of samples are less than $d+1$, then the sample set is linearly separable?

Question

Pattern classification by Duda, Hart, Stork (Section- 9.6.8) states that a 2-class training set of $d+1$ or less samples in a d−dimensional space is always linearly separable i.e. if the samples span the $d$ dimensions and not in any sub-space of $d$.

In short, for $n \le d + 1$, where $n$ is the number of samples, there exists a separating hyperplane.

How can it be proved?

Answer 1

Upon increasing the dimension by 1, it's easy to construct a separating hyperplane explicitly.

Index the vectors $v_i \in \mathbb{R}^d$ so that the first $k$ of them ($0 \le k \le d+1$) belong to one class and the remaining $d+1-k$ belong to the other. Embed them all (linearly) into $\mathbb{R}^{d+1}$ by sending $v_i$ to $u_i$ where the first $d$ coordinates of $u_i$ are those of $v_i$ and the $d+1^{st}$ coordinate is $1$. Let's call this map $\sigma$. The assumptions imply the $u_i$ are a basis for $\mathbb{R}^{d+1}$. Let $\omega_i, i=1,2,\ldots,d+1$ be the dual basis: that is, $\omega_j(u_i) = \delta_{ji}$. Define the linear form $\phi: \mathbb{R}^{d+1} \to \mathbb{R}$ via

$$\phi = \sum_{i=1}^k \omega_i - \sum_{i=k+1}^{d+1} \omega_i.$$

That is, $\phi(u_i) = 1$ when $i$ is in the first class and $\phi(u_i) = -1$ when $i$ is in the second class. A separating hyperplane is

$$H: \{x \in \mathbb{R}^{d} \ | \ \phi(\sigma(x)) = 0\}.$$

Example

Let $v_1 = (0,1)'$, $v_2 = (1,0)'$, and $v_3 = (1,1)'$ in $\mathbb{R}^2$ and suppose $k=1$ (i.e., $v_1$ is in one class--"blue"--and $v_2$ and $v_3$ are in the other class, "red").

Then

$$u_1 = (0,1,1)', \quad u_2 = (1,0,1)', \quad \text{and } u_3 = (1,1,1)'.$$

The forms dual to the $u_i$ are

$$\omega_1 = (-1,0,1), \quad \omega_2 = (0,-1,1), \quad \omega_3 = (1,1,-1),$$

as is readily checked by matrix multiplication (e.g., $\omega_2(u_1)$ = $(0,-1,1)(0,1,1)'$ = $0 + -1 + 1 = 0$, as required). Whence

$$\phi = \omega_1 - \omega_2 - \omega_3 = (-2,0,1).$$

For $x = (x_1, x_2)' \in \mathbb{R}^2$, $\phi(\sigma(x)) = (-2,0,1)(x_1,x_2,1)' = -2x_1 + 1$. A separating hyperplane is

$$H: -2x_1 + 1 = 0.$$

As a check, apply this formula for $H$ to the $v_i$, obtaining $1$, $-1$, and $-1$, as intended.