Skip to main content
added 1425 characters in body
Source Link
Liviu Nicolaescu
  • 34.7k
  • 2
  • 91
  • 165

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, $$$$\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$.

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.

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, $$

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

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

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$.

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.

added 247 characters in body
Source Link
Liviu Nicolaescu
  • 34.7k
  • 2
  • 91
  • 165

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 detailsa precise statement you can skip to the highlighted statementportion at the end of my answer.)

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$. (For details you can skip to the highlighted statement at the end.)

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.)

added 303 characters in body
Source Link
Liviu Nicolaescu
  • 34.7k
  • 2
  • 91
  • 165

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$. (For details you can skip to the highlighted statement at the end.)

Pick a finite collection $\newcommand{\eL}{\mathscr{L}}$ $\eL$ of linear maps $\bR^n\to\bR$ in general positiongeneral 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. $$

There areDenote by $\binom{\nu}{n-1}$$\binom{\eL}{n-1}$ the collection of subsets of $C\subset \eL$$\eL$ of cardinality $n-1$. IfThere 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}. $$

SupposeA. Suppose we know $L_C(S)$ for any collection $C\subset \eL$ of cardinality$C\in\binom{\eL}{n-1}$. $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=n-1$$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\subset \eL$$C_0\in\binom{\eL}{n-1}$ such that $\# C_0=n-1$ and $\# 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 \in\bR^{n-1}$$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$.

SupposeB. 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\subset \eL$ of cardinality $n-1$$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, $$

and we know $L_C(S)$ for any collection $C\subset \eL$ $\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$.

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$. (For details you can skip to the highlighted statement at the end.)

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. $$

There are $\binom{\nu}{n-1}$ subsets $C\subset \eL$ of cardinality $n-1$. 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.

Suppose we know $L_C(S)$ for any collection $C\subset \eL$ of cardinality $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=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\subset \eL$ such that $\# C_0=n-1$ and $\# 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 \in\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$.

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\subset \eL$ of cardinality $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, $$

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

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$. (For details you can skip to the highlighted statement at the end.)

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, $$

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$.

added 929 characters in body
Source Link
Liviu Nicolaescu
  • 34.7k
  • 2
  • 91
  • 165
Loading
added 929 characters in body
Source Link
Liviu Nicolaescu
  • 34.7k
  • 2
  • 91
  • 165
Loading
added 99 characters in body
Source Link
Liviu Nicolaescu
  • 34.7k
  • 2
  • 91
  • 165
Loading
added 53 characters in body
Source Link
Liviu Nicolaescu
  • 34.7k
  • 2
  • 91
  • 165
Loading
Source Link
Liviu Nicolaescu
  • 34.7k
  • 2
  • 91
  • 165
Loading