Reconstructing set of points from one-dimensional images

Question

Consider a set of $N$ points in $n$-dimensional space, i.e. \begin{align*} \{x_1, \dots, x_N\} \subset \mathbb R^n. \end{align*} Let us be given a finite family of non-injective matrices \begin{align*} \{M_j \in \mathbb R^{m \times n} : j = 1, \dots, J\}, \end{align*} e.g. $m<n$.

In a nutshell, the problem I would like to address is the following: For any $j = 1, \dots, J$ we are given the set of points (i.e. no knowledge about ordering!) \begin{align*} \{M_j x_1 , \dots, M_j x_N\} \end{align*} which can be seen as a projection of the set $\{x_1, \dots, x_N\}$.

My question is: Under which conditions on the family of projection matrices we can uniquely reconstruct the set $\{x_1, \dots, x_N\}$? Intuitively I would say that $J$ has to be large enough (dependend on $N$) and that the matrices should fullfill some assumption like \begin{align*} \bigcap_{j = 1,\dots, J} \ker M_j = \{0\}. \end{align*}

Answer 1

Denote by $S$ your finite collection of $N$ points in $\newcommand{\bR}{\mathbb{R}}$ $\bR^n$. Here is how you can recover $S$ from the knowledge of its images via a finite collections of linear maps of rank $<n$. More precisely one can use a universal family consisting of roughly $\frac{N^4}{2}$ matrices of type $(n-1)\times n$ and $n+2$ matrices of type $1\times n$. This may not be optimal but at least it is polynomial in $N$. (For a precise statement you can skip to the highlighted portion at the end of my answer.)

Pick a finite collection $\newcommand{\eL}{\mathscr{L}}$ $\eL$ of linear maps $\bR^n\to\bR$ in general position, i.e., any $n$ of them are linearly independent. Denote by $\nu$ the cardinality of $\eL$. The number $\nu$ is $> n$ and will be specified later. For any collection $C\subset \eL$ we obtain a linear map

$$L_C:\bR^n\to\bR^C. $$

Denote by $\binom{\eL}{n-1}$ the collection of subsets of $\eL$ of cardinality $n-1$.There are $\binom{\nu}{n-1}$ such subsets. If $C$ is such a collection, then the linear map $L_C:\bR^n\to\bR^{n-1}$ is surjective and it has a one-dimensional kernel. The general position assumption shows that if $C_0,C_1\in \binom{\eL}{n-1}$, then

$$ C_0=C_1\iff \ker L_{C_0}=\ker L_{C_1}. $$

A. Suppose we know $L_C(S)$ for any collection $C\in\binom{\eL}{n-1}$.

Assume $\nu$ is large enough so that

$$\binom{\nu}{n-1}>\binom{N}{2}. $$

Since the $N$ points in $S$ determine at most $\binom{N}{2}$ lines, we deduce that at least one of the linear maps $L_C$, $C\in\binom{\eL}{n-1}$, restricts to an injective map $S\to \bR^C$. In particular we deduce that

$$ N=\# S= \max_{\# C=n-1} L_C(S). $$

Choose $C_0\in\binom{\eL}{n-1}$ such that $\# L_{C_0}(S)=\# S=N$. Without loss of generality we can assume that $L_{C_0}$ is the projection

$$P_0:\bR^n\to \bR^{n-1},\;\;(x_1,\dotsc,x_n)\mapsto (x_1,\dotsc, x_{n-1}). $$

For each point $s\in S$ we set $s':=P_0(s)$. Now we have complete knowledge of the set

$$ S'=\bigl\lbrace\; s';\;\;s\in S\;\bigr\}=P_0(S). $$

The set $S'\subset \bR^{n-1}$ has the same cardinality as $S$. Moreover any point $s'\in S'$ determines a vertical line, i.e., a line parallel with $\ker P_0$,

$$ \ell_{s'}=P_0^{-1}(s')=\bigl\{\; (s', t)\in\bR^n;\;\;t\in\bR\;\bigr\}. $$

We now have determined $N$ vertical lines and each one of them contains exactly one point in $S$.

B. Suppose that we know $L(S)\subset \bR$ for any $L\in\eL$.

Choose a linear functional $L\in \eL\setminus C_0$. The set $L(S)$ has $m\leq N$ elements $r_1<\cdots <r_m$. We obtain $m$-hyperplanes

$$H_j(L)=\{ L(x)=r_j\},\;\;j=1,\dotsc, m, $$

and a set $X(S,L)$ consisting of $Nm$ points

$$ H_j(L)\cap \ell_{s'},\;\;j=1,\dotsc, m,\;\;s'\in S'. $$

Clearly $S\subset X(S,L)$. Thus $S$ can only be one of the $\binom{Nm}{N}$ subsets of $X$ of cardinality $Nm$. Doing this with any $L\in \eL\setminus C_0$ we deduce

$$ S\subset \bigcap_{L\in\eL\setminus C_0} X(S,L). $$

Fix a linear map $L_0\in \eL\setminus C_0$ and set $X_0=X(S, L_0)$. We know that

$$ S\subset X_0,\;\; \# X_0\leq N^2. $$

Suppose that $\nu$ is large enough so that

$$\binom{\nu}{n-1}>\binom{N^2}{2} +2. $$

We can then find a collection $C_1\in\binom{\eL}{n-1}$ such that $C_1\neq C_0$ and $L_{C_1}$ and the restriction of $L_{C_1}$ to $X_0$ is injective. We know know exactly $L_{C_1}(X_0)$ and $S_1:=L_{C_1}(S)\subset L_{C_1}(X_0)$. Note that $\# S_1=\# S=N$.

For each point $s_1\in S_1$ we get a line $\ell_{s_1}= L_{C_1}^{-1}(s_1)$. Let us observe that each line $\ell_{s_1}$ intersects exactly one of the lines $\ell_{s'}$, $s'\in S'$, because

$$\ell_{s_1}\cap\ell_{s'}\subset X_0, $$

and the restriction of $L_{C_1}$ to $X_0$ is one-to-one.

To conclude, if $\eL\subset {\rm Hom}\;(\bR^n,\bR)$ is a finite collection in general position whose cardinality $\nu$ satisfies

$$\binom{\nu}{n-1}>\binom{N^2}{2}+2, \tag{$\nu$}$$

and we know $L_C(S)$ $\forall C\subset \eL$ of cardinality $1$ or $n-1$, then we can completely recover $S$.

Remark. We can relax assumption B to

B'. We know $L(S)$ for any $L$ in a family $F\subset \eL$ of cardinality $n+2$.

Update. Let me explain how the above procedure can be used to recover multisets. First, let me define a discrete weight distribution or d.w.d. in $\bR^n$ to be a pair $(S, w)$ where $S$ is a finite subset of $\bR^n$ and $w$ is a function $w:S\to (0,\infty)$. We say that $S$ is the support of the d.w.d.

Given a d.w.d. $(S,w)$ in $\bR^n$ and a map $f:\bR^n\to\bR^m$ we obtain a d.w.d. $f_*(S,w)$ in $\bR^m$ given by [ $$ f_*( S, w)= \bigl(\; f(S), f_* w)\;\bigr), $$

where for any $y\in f(S)$ we set

$$ f_* w(y)=\sum_{x\in f^{-1}(y)\cap S} w(x). $$

Suppose that $(S,w)$ is a d.w.d. in $\bR^n$ $\DeclareMathOperator{\Hom}{Hom}$ such that $|S|=N$, and $\eL\subset \Hom(\bR^n,\bR)$ of cardinality $\nu$ constrained by the inequality ($\nu$) above. I claim that if we know the d.w.d.'s $(L_C)_*(S,w)$ for any subset $C\subset \eL$ of cardinality $1$ and $n-1$, then we can completely determine $(S,w)$.

To see this, note that the above discussion shows that this information can be used to determine the support $S$ of the unknown d.w.d. $(S,w)$. To determine $w$ choose a subset $C_0\in \binom{\eL}{n-1}$ such that the restriction of $L_{C_0}$ to $S$ is injective. Let $x\in S$ and set $y=L_{C_0}(x)\in\bR^{C_0}$. In this special case we have

$$ w(x)= (L_{C_0})_*w(y). $$

From our assumption, the quantity in the right hand side of the above equality is known.

Answer 2

I don't provide an actual answer (I don't have one), but do provide some musings that might be helpful to others who would like to consider this problem.

First, if there is only one point, then the condition $$\bigcap_{j = 1,\dots, J} \ker M_j = \{0\}$$ is both necessary and sufficient. It is clearly necessary even if there are more points.

Consider the two-dimensional case, i.e. the situation $n=2 =m$, and suppose the matrices are projections to one-dimensional subspaces. For any two projections it seems possible to place three points so that they can't be distinguished from four points - for example, suppose the two projections are coordinate projections, and take the three or four points to be corners of a square.

By drawing additional pictures it seems that, in the plane, $J$ maps are not enough (in the sense that one can select $J+2$ points so that omitting specific one of them does not change the set of projections) but $J+1$ projections to different lines do seem to suffice. Actually proving this would presumably be a matter of linear algebra, but I have not done it.

In two dimensions the strategy seems to be to consider projections to arbitrary and different lines. In higher dimensions it might be useful to first consider projections to one-dimension or $n-1$-dimensional subspaces, and only after getting some grip on those try to consider a situation with projections onto subspaces of mixed dimensions.