There is no such function f; the output dimension needs to be at least 2n/2−1 for this to be possible.
Suppose that f:{0,1}n→Rd is such that f(S) and f(Sc) are linearly separable for any XOR-subset (subset of form {x∈{0,1}n:xi1⊕xi2⊕⋯⊕xik=0}). There are 2n such XOR-subsets. Consider the matrix M of dimension 2n×2n whose rows are labeled by x∈{0,1}n and columns by XOR-subsets S, with
Mx,S=1 if x∈S, else −1.
(I.e.M is a Hadamard matrix of size 2n×2n. We may assume M is symmetric.) The function f is such that, for any S, there exist wS∈Rd,bS∈R such that
sign(⟨wS,f(x)⟩+bS)=Mx,S
for all x. Thus, if we define vx=(f(x),1)∈Rd+1 and uS=(wS,bS)∈Rd+1, we have
Mx,S=sign(⟨vx,uS⟩).
The definition of sign-rank of a matrix M is the smallest dimension d+1 for which such a decomposition exists. A theorem by Forster implies that the sign-rank of M is at least 2n/||M||, whereas it’s well-known that the spectral norm of symmetric Hadamard matrices is √2n, That implies d+1≥2n/2.
There is no such function f; the output dimension needs to be at least 2n/2−1 for this to be possible.
Suppose that f:{0,1}n→Rd is such that f(S) and f(Sc) are linearly separable for any XOR-subset (subset of form {x∈{0,1}n:xi1⊕xi2⊕⋯⊕xik=0}). There are 2n such XOR-subsets. Consider the matrix M of dimension 2n×2n whose rows are labeled by x∈{0,1}n and columns by XOR-subsets S, with
Mx,S=1 if x∈S, else −1.
(I.e.M is a Hadamard matrix of size 2n×2n. We may assume M is symmetric.) The function f is such that, for any S, there exist wS∈Rd,bS∈R such that
sign(⟨wS,f(x)⟩+bS)=Mx,S
for all x. Thus, if we define vx=(f(x),1)∈Rd+1 and uS=(wS,bS)∈Rd+1, we have
Mx,S=sign(⟨vx,uS⟩).
The definition of sign-rank of a matrix M is the smallest dimension d+1 for which such a decomposition exists. A theorem by Forster implies that the sign-rank of M is at least 2n/||M||, whereas it’s well-known that the spectral norm of symmetric Hadamard matrices is √2n, That implies d+1≥2n/2.