Suppose $x_1, x_2, ..., x_n$ are $n$ real-valued vectors of dimension $d$ ($x_i \in R^d$) that are linearly independent ($d \geq n$). There is also another vector of length n, namely $a = (a_1, a_2,...,a_n)$ where each $a_i$ is $-1$ or $1$.
Is this true that for every vector $a \in \{-1,1\}^n$ there is a $d$-dimensional vector $\theta$ where for all $1\leq i \leq n$ we have $a_i = sign(<x_i, \theta>)$?
Add $x_{n+1},...,x_d$ such that the $x_k$ forms a basis of $\mathbb{R}^d$. Then the matrix $A$ whose columns are $x_k$ is invertible.
Pick any $a\in \mathbb{R}^d$ and let $\theta = (A^T)^{-1} a$. Then $x_k^T \theta = e_k^T A^T \theta = e_k^T a = a_k$.