= Solution
Expanding the squared <Euclidean norm> gives
$$
x\in B(c,r)\quad\Longleftrightarrow\quad
\|x\|^2-2c\cdot x+\|c\|^2-r^2\leq0.
$$
In lifted coordinates $(z,t)=\Phi(x)=(x,\|x\|^2)$, this is the <closed half-space>
$$
\boxed{t-2c\cdot z+\|c\|^2-r^2\leq0.}
$$
Every labelling of the original points obtainable by a <Euclidean ball> is therefore obtainable on their lifted images by an <affine linear classifier>. The <feature map> is <injective>, since it preserves the first $d$ coordinates; distinct original points remain distinct. If the original points are shattered, every labelling of the lifted points is realized, as required.
Here “linear separator” means a separator with an intercept, namely an <affine hyperplane>. If a convention demands strict separation on the finite sample, increase the constant term of the positive score $r^2-\|c\|^2+2c\cdot z-t$ by a sufficiently small positive amount. Positive points then have strictly positive score, and the finitely many negative scores remain strictly negative. A homogeneous separator can alternatively be obtained after adjoining one more constant coordinate; this distinction matters for dimension counts.
Back to article page
