1
$\begingroup$

Question:

I want to determine a boolean vector $b \in \{0,1\}^n$ consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product of $b$ with a real-valued vector $v \in \mathbb{R}^n$ of my choosing. I.e., access to $b$ is available through evaluation of the map $$v \mapsto b^T v.$$ How can I recover all of the entries of $b$ using as few of these dot products as possible? (maybe even just 1 dot product?)

Below I detail a couple ideas I had which might work in theory, but which don't work in practice (I think). For concreteness, one may assume that $n \approx 1 \text{ million}$, and arithmetic is done in double precision floating point format. This question arose as a subproblem in a machine learning application.


Idea 1:

One idea I had is to use a vector with fast growing entries. Say, for example, $n=9$. Then we could use the vector $$v=\begin{bmatrix}1 & 10 & 100 & 1000 & \dots\end{bmatrix}^T.$$ One could then read off $b$ as the digits of $b^T v$. The problem with this solution is that the numbers grow so fast, that in finite precision computer arithmetic it will not work for large $n$.


Idea 2:

Another idea I had was to use a vector with entries that are algebraically independent. Then determining $b$ from $b^Tv$ is a subset sum problem.

For example, if $n=3$ and $$v = \begin{bmatrix}\pi & e & 1\end{bmatrix}^T,$$ then $b^T v$ will take on one of a finite number of possibilities, $$b^T v \in \{\pi,~e,~1,~\pi+e,~\pi+1,~e+1,~\pi+e+1\}.$$ We can determine which of these is the case, thereby determining $b$.

But this seems quite combinatorial, and therefore unfeasible for large $n$.

$\endgroup$
  • 1
    $\begingroup$ "$b^T v \in \{\pi,~e,~1,~\pi+e,~\pi+1,~e+1,~\pi+e+1\}$". 0 is missing. $\endgroup$ – Apass.Jack Jul 25 at 6:49
1
$\begingroup$

Here is an variant of the idea 1 in the question, where a factor of 2 is used to replace the original factor of 9.

  1. Let $v=[2^0, 2^1, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$. Obtain $b^Tv$, which will determine the first 64 entries of $b$.
  2. Let $v=[0, 0, 0, \cdots, (64 \text { zeros}), 1, 2, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$. Obtain $b^Tv$, which will determine the next 64 entries of $b$.
  3. Let $v=[0, 0, 0, \cdots, (128 \text { zeros}), 1, 2, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$. Obtain $b^Tv$, which will determine the next 128 entries of $b$.
  4. And so on, until we have determined all entries of $b$. There may be less than 64 positive numbers in $v$ in the last round.

The above scheme is the best possible if the number of effective bits in $b^Tv$ is 64 and we have no prior knowledge about $v$ except the number of its entries. This can be seen easily from information theory, as each query against the black box can provide at most 64 bits of information.

$\endgroup$
  • $\begingroup$ Oh, I see. This makes sense, thank you $\endgroup$ – Nick Alger Jul 25 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.