Phase Retrieval for Sparse Signals

Introduction

The theory of compressive sensing has generated enormous interest in recent years. The goal of compressive sensing is to recover a sparse signal from its linear measurements, where the number of measurements is much smaller than the dimension of the signal, see e.g. . The aim of this paper is to study the problem of compressive sensing without the phase information. In this problem the goal is to recover a sparse signal from the magnitude of its linear samples.

Recovering a signal from the magnitude of its linear samples, commonly known as phase retrieval or phaseless reconstruction, has gained considerable attention in recent years . It has important application in X-ray imaging, crystallography, electron microscopy, coherence theory and other applications. In many applications the signals to be reconstructed are sparse. Thus it is natural to extend compressive sensing to the phase retrieval problem.

The best current results on the $k$-sparse phase retrieval property are proved by Li and Voroninski , which state that $k$-sparse phase retrieval property can be achieved by having $m\geq 4k$ and $m\geq 8k$ vectors for the real and complex case, respectively (see also ).

Minimal Sample Number for k𝑘k-Sparse Phase Retrieval

Proof. Note that the full sparsity case $k=d$ is already known: $m\geq 2d-1$ vectors are needed for phase retrieval and a generic set of ${\mathcal{F}}$ with $m\geq 2d-1$ vectors will have the phase retrieval property. So we will focus only on $k<d$.

We divide ${\mathcal{F}}$ into two groups: ${\mathcal{F}}_{1}=\{f_{j}:~{}j\in[1:k]\}$ and ${\mathcal{F}}_{2}=\{f_{j}:~{}j\in[k+1:m]\}$. Let the corresponding frame matrices be $F_{1}$ and $F_{2}$, respectively. Consider the subspace

For the first group ${\mathcal{F}}_{1}$, there exists a $u\in W\setminus\{0\}$ such that $F_{1}^{\top}u=0$, i.e. $\langle{f_{j},u}\rangle=0$ for all $1\leq j\leq k$. This is because $\dim(W)=k+1$ and there are only $k$ equations. Note also that there are at most $k-1$ vectors in the second group ${\mathcal{F}}_{2}$ since $m-k<2k-k=k$. Thus the solution space

Now set $\bar{v}=t_{0}\alpha+s_{0}\beta$ and

Similar with before, we set $\bar{v}=t_{0}\alpha+s_{0}\beta$ and

then $x=\pm y$. Equation (2.1) implies that for all $j$ we have

Thus either $\langle f_{j},x-y\rangle=0$ or $\langle f_{j},x+y\rangle=0$. Without loss of generality, we assume that

Set $A:=F^{\top}$ where $F$ is the frame matrix of ${\mathcal{F}}$. Combining (2.3) and (2.4) now yields

where for any index sets $J_{1},J_{2}$ we use the notation $A_{J_{1},J_{2}}$ to denote the sub-matrix of $A$ with the rows indexed in $J_{1}$ and columns indexed in $J_{2}$. To show $x=\pm y$ we only need to show that the linear equations (2.5) force $v_{x}=0,v_{y}=0$ and either $w_{-}=0$ or $w_{+}=0$.

We next consider the complex case. Similar to the real case we set

${\rm supp}(x)\subset I$, ${\rm supp}(y)\subset J$.

The first nonzero entry of $y$ is real and positive.

$\mathbf{M}_{\mathcal{F}}(x)=\mathbf{M}_{\mathcal{F}}(y)$.

Now the projection of ${\mathcal{A}}_{I,J}$ to the first component gives the full set $G_{I,J}$. Each $(F,x,y)\in{\mathcal{A}}_{I,J}$ gives rise to the constraints $|\langle{f_{j},x}\rangle|=|\langle{f_{j},y}\rangle|$ for $j\in[1:m]$, which lead to the set of quadratic equations in ${\rm Re}(f_{ij}),{\rm Im}(f_{ij})$ (by viewing $x$, $y$ as fixed)

Remark. Although the above theorem shows that in the complex case any $m\geq 4k-2$ generically chosen vectors are $k$-sparse phase retrievable, it is unknown whether $4k-2$ is in fact the minimal number required. We conjecture that the minimal number of vectors needed for being $k$-sparse phase retrievable is indeed $4k-2$. Note that it is obvious that the conjecture holds for $k=1$.

Null Space Property for Sparse Phase Retrieval

The matrix $F$ satisfies the null space property of order $k$ if for any nonzero $\eta=[\eta_{1},\dots,\eta_{d}]^{\top}\in{\mathcal{N}}(F)$ and any $T\subset[1:d]$ with $\#T\leq k$ it holds that

where $T^{c}$ is the complementary index set of $T$ and $\eta_{T}$ is the restriction of $\eta$ to $T$.

2. The null space property for the real sparse phase retrieval

Our goal here is to extend Theorem 3.1 to the phase retrieval for the real signal. For a given frame ${\mathcal{F}}=\{f_{1},\dots,f_{m}\}$ and a subset $S$ of $[1:m]$ we shall use ${\mathcal{F}}_{S}$ to denote the set ${\mathcal{F}}_{S}:=\{f_{j}:~{}j\in S\}$. Similarly for the frame matrix we shall use $F_{S}$ to denote the corresponding frame matrix of ${\mathcal{F}}_{S}$, i.e. the matrix whose columns are the vectors of ${\mathcal{F}}_{S}$. We first consider the real case.

where $|F^{\top}x|=[\lvert\langle{f_{1},x}\rangle\rvert,\ldots,\lvert\langle{f_{m},x}\rangle\rvert]^{\top}$.

For every $S\subseteq[1:m]$ with $\#S\leq k$, it holds

for all nonzero $u\in{\mathcal{N}}(F_{S})$ and $v\in{\mathcal{N}}(F_{S^{c}})$ satisfying $\|u+v\|_{0}\leq k$.

The solution to (3.2) is denoted as $x_{\epsilon}$. We claim that for any $\epsilon\in\{1,-1\}^{m}$ we must have

if $x_{\epsilon}$ exists (it may not exist), and the equality holds if and only if $x_{\epsilon}=\pm x_{0}$.

To prove the claim let $\epsilon^{*}\in\{1,-1\}^{m}$ such that $b_{\epsilon_{*}}=F^{\top}x_{0}.$ Note that property (B) implies the classical null space property of order $k$. To see this, for any nonzero $\eta\in{\mathcal{N}}(F)$ and $T\subseteq[1:d]$ with $\#T\leq k$, set $u:=\eta$ and $v:=\eta_{T}-\eta_{T^{c}}$. Let $S=[1:m]$. Then $u\in{\mathcal{N}}(F_{S})$ and $v\in{\mathcal{N}}(F_{S^{c}})$. The hypothesis of (B) now implies

Consequently we must have $x_{\epsilon^{*}}=x_{0}$ by Theorem 3.1. Now for any $\epsilon\in\{-1,1\}^{m}\neq\pm\epsilon^{*}$, if $x_{\epsilon}$ doesn’t exist then we have nothing to prove. Assume it does exist. Set $S_{*}:=\{j:~{}\epsilon_{j}=\epsilon^{*}_{j}\}$. Then

since either $\langle{f_{j},u}\rangle=0$ or $\langle{f_{j},v}\rangle=0$. In other words, $|F^{\top}x_{0}|=|F^{\top}(u-v)|$. Note that $u-v\neq-x_{0}$, for otherwise we would have $u=0$, a contradiction. It follows from the hypothesis of (A) that we must have

3. The null space property for the complex sparse phase retrieval

Suppose that $S_{1},\ldots,S_{p}$ is any partition of $[1:m]$ and that $\eta_{j}\in{\mathcal{N}}({F_{S_{j}}})\setminus\{0\}$ satisfy

Now set $\eta_{j}:=c_{j}x_{\epsilon^{*}}-x_{\epsilon}$. Then we have

We next prove (A) $\Rightarrow$ (B). Assume (B) is false, namely, there exist nonzero $\eta_{j}\in{\mathcal{N}}(F_{S_{j}}),j\in[1:p]$ satisfying (3.4) but

Note that $x_{0}$ is $k$-sparse. Combining (3.8), (3.7) and (3.3) now yields

Here, note that $c\notin\{c_{1},c_{2}\}$, for otherwise we will have either $\eta_{1}=0$ or $\eta_{2}=0$. Combining (3.4) and (3.9) leads to

for all $j\in[2:p]$, $\eta_{j}$ and $\eta_{1}$ are linear dependent and hence $\eta_{1}\in{\mathcal{N}}(F_{S_{j}})$.

We remain to prove (3.8). First, when $j\in S_{1}\cup S_{2}$, (3.8) holds, since either $\langle{f_{j},\eta_{1}}\rangle=0$ or $\langle{f_{j},\eta_{2}}\rangle=0$. We consider the case where $j\in S_{3}$. Set $y_{0}:=\frac{\eta_{1}-\eta_{2}}{c_{1}-c_{2}}$. Then (3.6) implies that

Note that $\langle{f_{j},\eta_{3}}\rangle=0$ with $j\in S_{3}$. Then

Using a similar argument, we easily prove the claim for $j\in S_{4},\ldots,S_{p}$.

Null space property for general phase retrieval

Suppose that $S_{1},\ldots,S_{p}$ is any partition of $[1:m]$. There exists no $\eta_{j}\in{\mathcal{N}}({F_{S_{j}}})~{}\setminus~{}\{0\},j=1,\ldots,p,$ such that

Proof. We first prove (A) $\Rightarrow$ (B). Assume (B) is false, namely, there exist nonzero $\eta_{j}\in{\mathcal{N}}(F_{S_{j}}),\,j\in[1:p],$ satisfying (4.10). Set

Using a similar method as the proof of (3.8), we obtain that

Then, according to (A) and the definition of phase retrievable, we have

Combining (4.10) and (4.11), we obtain that, for all $j\in[2:p]$, $\eta_{j}$ and $\eta_{1}$ are linear dependent and hence $\eta_{1}\in{\mathcal{N}}(F_{S_{j}})$. So, $F^{\top}\eta_{1}=0$. The (A) implies that $\eta_{1}=0$, a contradiction.

References