# Reconstructing set of points from one-dimensional images

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

• You write that the data includes no knowledge of ordering. What do you mean by this? Does it mean that we do not know if some y in the data is given as $y =M_1 x_4$ or $y=M_2 x_1$, for example? Apr 16, 2014 at 9:22
• Some more questions: Is J known a priori? Can you select the matrices $M_j$ or are they arbitrary? Apr 16, 2014 at 10:01
• Hello Tommi Brander: concerning your first question: for a fixed $j$, given a point $y$, you dont know whether it is generated by $M_j x_1$ or $M_j x_{100}$ If you had this orderning, then you could trivially solve the problem for each point $x_i$ separately. Hence the nessecary condition of trivial intersection of kernels. Concerning your second question: J is not apriori known and is part of the question. What I am looking for are conditions on $J$ and the set of projection matrices, such that the reconstruction is unique.
– user45183
Apr 16, 2014 at 10:24
• Your question is addressed (for the complex case) in the paper arxiv.org/abs/1312.0158 by Conca, Edidin, Hering and Vinzant, and in the references it cites. Another keyword is "multiview- or epipolar geometry" Apr 16, 2014 at 10:58
• For points in $\mathbb{R}^3$, a version of the problem is called "shape from shadows," and is heavily studied. E.g., "The Episolar Constraint: Monocular Shape from Shadow Correspondence" PDF download link Apr 16, 2014 at 11:58

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.

• Dear Prof. Nicolaescu, thank you very much for your answer. It seems that there was a slight misunderstanding in my question. You wrote that in B that $L(S)$ has $m \le N$ elements. Actually I want to also take into account multiplicities, i.e. view $L(S)$ not as a set but as a multiset. Does this make the problem easier? Can your solution still be applied?
– user45183
May 8, 2014 at 12:41
• Yes, it makes the problem easier. If you know $L(S)$ aa multi-set, then you know a collection of points with some multiplicities. In my proof I do not assume that these multiplicities are known, i.e., I assume a lot less. The method I described can also be used when the set $S$ itself is a multiset. In a few hours will add an update to my answer. May 8, 2014 at 13:51
• I've updated my answer and I explain how to deal with multisets. May 8, 2014 at 15:35
• Thank you very much for your efforts. I am now going through your proof. I am wondering whether the computation of the set $S$ can be made efficient, e.g. by giving an "easier" proof for the multiset-case only. To this end, mathoverflow.net/questions/165534/… might also be interesting to you. Thank you very much again.
– user45183
May 9, 2014 at 10:29

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.