# Approximation of large dimensional vectors by vectors of smaller dimension

sIs there any (efficient) algorithm for the following problem:

Let $n = 128$ and $m = 64$ (in the end only $n > m$ matters) and $p_1, \ldots, p_t \in \{ -1,1 \} ^{128}$ be given ($t << 2^{128}$) . Find a matrix $A \in M(n \times m, \frac{1}{2^{64}}\mathbb{Z})$ and vectors $q_1, \ldots, q_t \in \{ -1, 1 \}^{64}$, such that if $b_i = A q_i \in \mathbb{R}^{128}$ then $$p_{ij} = sgn (b_{ij})$$ for most $1 \leq i \leq t$ and $1 \leq j \leq n$, i.e., the number of tuples $(i,j)$ violating the equation is neglible compared to $tn$.

• Please fix your typos (click the edit button). For example $b_i$ is only mentioned once. – Brendan McKay May 24 '12 at 2:10
• So, $p_{ij}$ is your notation for the $j$th component of $p_i$, similarly, $b_{ij}$? – Gerry Myerson Jul 11 '12 at 1:27
• Yes, that is precisely what I meant. So in essence practically everything of the vectors $p_i$ can be obtained from $A$ and the smaller vectors $q_i$. – tobias Jul 16 '12 at 14:01