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\*}



Reconstructing set of points from one-dimensional images
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.


