1
$\begingroup$

What is the smallest length $m$ of a sequence $u_1,\ldots,u_m$ of $d$-dimensional vectors with real entries such that every finite set $X$ of $d$-dimensional vectors with real entries can be reconstructed uniquely from the unordered lists $$L_k:=[u^Tx\mid x\in X]~~~(k=1,\ldots,m)$$ of length $m$?

A related question is Solving for a set of points from projections, with sets $\{u^Tx\mid x\in X\}$ in place of the $L_k$. But the answer given there assumes that the coefficents of all vectors in $X$ are rational, or belong to a fixed countable subfield of the reals; then $m=d+1$ suffices.

Another related question is Reconstructing set of points from one-dimensional images. The answer given there provides for $d=2$ a construction of a sequence of length $m=O(n^4)$ that ensures unique reconstruction of all sets $X$ of fixed cardinality $n$.

But I am looking for a sequence that is independent of the cardinality of $X$. My conjecture is that $m\le 3d$, and that, in the sense of the Lebesgue measure, almost every sequence of length $3m$ leads to unique reconstruction for all $X$.

I am also interested in an algorithm for achieving the reconstruction for any given $X$, for a particular sequence of $u_\ell$ depending on $d$ only.

The case $d=2$ is already nontrivial: The two lists $L_1$ and $L_2$ from $u_1:=(1,0)$ and $u_2:=(0,1)$ determine $X$ up to a permutation $\pi$ as $$X=\{(y_i.z_{\pi i}) \mid i=1,\ldots,|X|\}.$$ The question is how many additional vectors are needed to fix the permutation $\pi$ up to relabeling identical $y_i$. For most but not all $X$, a single additional vector $u_3$ suffices. But this still leaves many exceptional cases. It seems to me that 3 or 4 additional vectors $u_3,\ldots,u_m$ should suffice for $d=2$ since the number of possible exceptions should rapidly decrease to zero.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .