On Conditions for Uniqueness in Sparse Phase Retrieval

I Introduction

In many areas in optics, physical limitations make it imposable to measure the phase. If the signal is real, then the sign is lost and if the signal is complex, the phase. Even though the phase is not measured, it often contains valuable information. For example, in X-ray crystallography , only the magnitude of the Fourier transform is observed. If the phase would be observable, then the inverse Fourier transform would directly give the atomic structure of the crystal considered. Therefore the phase has to be retrieved before structural information can be explored.

The problem of retrieving the phase from intensity measurements is often referred to as the phase retrieval problem. The problem is by nature often ill-posed and early methods relied on additional information about the sought signal, such as band limitation, nonzero support, and nonnegativity to successfully recover the signal. The Gerchberg-Saxton algorithm is one of the popular methods for recovery. It utilizes a prior on the support and alternates between the Fourier and inverse Fourier transforms to obtain a phase estimate from a set of Fourier magnitude measurements . More recent development has shown that e.g., random collections of measurement vectors are rich enough to provide a well posed phase retrieval problem.

There has also been recent interest in sparse phase retrieval. In contrast to the literature on compressive sensing, which assumes a linear relation between measurements and the sparse unknown and is quite mature, the literature on sparse phase retrieval is still developing. Recent work has demonstrated that as in the case of linear measurements, the number of intensity measurements required to recover the true solution can be reduced by taking into account that the sought signal is sparse .

Even though showed that there exist collections of measurement vectors that provide accurate phase estimates, it is still not fully understood what properties these sets need to satisfy for the phase retrieval map to be injective. The first attempt to try to characterize these properties was given in (later refined in ). In particular the authors derived necessary and sufficient conditions for injectivity for a real signal and real collection of measurement vectors. Injectivity in the real case was also discussed in . For the complex case (complex signal and complex collection of measurement vectors), gave necessary conditions for injectivity.

As for sparse phase retrieval, it was shown in that $\mathcal{O}(k\log(M/k))$ real measurement vectors are sufficient for stable recovery of a $k$-sparse $M$-dimensional real signal. This means that the number of measurements needed for recovery from quadratic measurements is the same, up to a multiplicative scalar, as for linear measurements. The work in extended results presented in and derived bounds on the number of measurements needed for unique recovery in the sparse real case (real measurement vectors and real sparse signal) and for the complex sparse case (complex measurement vectors and complex sparse signal). For a $k$-sparse signal, $4k-1$ measurements were reported sufficient in the real case and $8k-2$ in the complex case. However, no characterization of the properties that lead to a unique recovery was given in . In the authors discuss sparse recovery from Fourier magnitude measurements and show that, under general conditions, the sought signal is uniquely defined by the magnitude of the full Fourier transform.

The contribution of the current letter is twofold. We first give a characterization of properties leading to unique recovery for sparse signals. In particular we show that only $4k-1$ phaseless measurements suffice to guarantee uniqueness of a $k$-sparse $M$-dimensional real solution while $2M-1$ measurements are required for a general $M$-dimensional real solution. Note that also showed that $4k-1$ phaseless measurements suffice. However, the authors did not provide any condition for when this is sufficient. Secondly we consider the important case of sparse recovery from Fourier magnitude measurements. We show that under rather mild conditions, $2(k^{2}-k+1)$ Fourier magnitude measurements guarantee uniqueness. This improves on which only considered recovery from a full Fourier ensemble, namely, $M$ measurements.

II The Phase Retrieval Problem

As shown in , the complement property is particularly useful when considering the theory of phase retrieval.

Using the complement property, the following theorem on the injectivity of intensity measurements using a real collection of measurement vectors was shown in :

It is now easy to show that $2M-1$ intensity measurements are necessary for $\mathcal{A}$ to be injective. This bound was also given (without a proof) in .

To satisfy the complement property we must have $N\geq 2M-1$ intensity measurements. Any $N<2M-1$ intensity measurements do not provide an injective map $\mathcal{A}$.

It can easily be verified that $2M-1$ measurement vectors independently drawn from e.g., an $M$-dimensional standard Gaussian distribution (zero mean, unit variance) satisfy the complement property with probability 1. According to Theorem 1 it is hence possible to uniquely recover an $M$-dimensional real signal from $2M-1$ intensity measurements.

II-B Complex Measurement Vectors and a Complex Signal

It is easy to verify that the complement property is only necessary and not sufficient for injectivity. An example of a set of measurement vectors that satisfies the complement property but does not provide an injective map is given in . It was conjectured (but not proven) in that $4M-4$ generic (see for definition) measurements are both necessary and sufficient for unique recovery.

III Uniqueness in Sparse Phase Retrieval

We now build on previous results and generalize them to the analysis of sparse phase retrieval. We start by studying a collection of real measurement vectors and then extend the results to an important class of complex measurement vectors, a partial Fourier basis, in Section III-B.

To handle sparse signals, it is convenient to introduce the following less restrictive version of the complement property:

The $k$-complement property reduces to the complement property of Definition 1 when $k=M$. If $k<M$ then the $k$-complement property is less restrictive. Furthermore, if $\Phi$ satisfies the $k$-complement property then it also satisfies the $(k-1)$-complement property.

We are now ready to state the following theorem on unique recovery of a $k$-sparse real signal:

For a sufficiently sparse ${\bf x}$, unique recovery can hence be guaranteed from fewer measurements than in the dense case. We give this result as a corollary:

A collection of $\min(4k-1,2M-1)$ measurement vectors suffice to uniquely recovery any $k$-sparse ${\bf x}$.

Before proving the corollary, we state the following lemma:

A set of $4k-1$ independent samples from an $M$-dimensional standard Gaussian distribution satisfies the $2k$-complement property with probability 1.

Generate the collection of measurement vectors by independently drawing $4k-1$ samples from a $M$-dimensional standard Gaussian distribution. Introduce $\mathsf{\Phi}$ as the $M\times(4k-1)$-matrix obtained by arranging the $4k-1$ vectors of $\Phi$ into a matrix. Let $\mathsf{\Phi}_{K,S}$ be the $|K|\times|S|$-matrix obtained by picking out the rows indexed in $K$ and columns indexed by $S$.

Consider the probability that $\Phi$ does not satisfy the $2k$-complement property:

where $\lambda_{min}$ denotes the smallest eigenvalue. We now use Boole’s inequality for unions of events

where we used that $P(\text{a }2k\times s\text{-submatrix is singular})=0$ when $s\geq 2k$ and $P(\text{a }2k\times(4k-1-s)\text{-submatrix is singular})=0$ when $s<2k$, which follow from the Gaussianity of the entries of the submatrices. ∎

First, since $2M-1$ measurements are enough in the dense case, this provides an upper bound on the number of measurements. Second, Theorem 4 gives that ${\bf y}=\mathcal{A}({\bf x})$ has a unique $k$-sparse solution for $\min(4k-1,2M-1)$ measurements if the collection satisfies the $2k$-complement property. Finally we have from Lemma 6 that such a collection exists since a set of $4k-1$ samples from an $M$-dimensional unit Gaussian distribution satisfies the $2k$-complement property with probability 1. ∎

III-B Complex Measurement Vectors and Real Signal: Fourier Magnitude Measurements

A particularly interesting set of complex measurement vectors is the incomplete Fourier basis. This special case is of great importance since Fourier magnitude measurements (FMMs) are inherent in applications such as X-ray crystallography , speckle imaging and blind channel estimation .

In deriving guarantees for FMMs, we need the concept of a collision free vector introduced in [17, Def. 1].

Let ${\bf x}(i)$ denote the $i$th element of the vector ${\bf x}$. We say that ${\bf x}$ is collision free if ${\bf x}(i)-{\bf x}(j)\neq{\bf x}(k)-{\bf x}(l)$, for all distinct $i,j,k,l\in\{i:i\in\{1,\dots,M\},\,{\bf x}(i)\neq 0\}$.

We are now ready to state the following theorem on the uniqueness of a sparse real solution given its FMMs.

Let $\{k_{1},k_{2},\dots,k_{N}\}\subseteq\{0,\dots,2M-1\}$,

$\|{\bf x}_{0}\|_{0}=6$ and ${\bf x}_{0}(i)\neq{\bf x}_{0}(j)$, for some $i,j\in\{i:i\in\{1,\dots,M\},\,{\bf x}_{0}(i)\neq 0\}$.

The implication of the theorem is that we can guarantee a unique solution from FMMs as long as enough measurements are taken, the signal is sparse enough, collision free and the support constrained.

is $k^{2}-k+1$-sparse (see for instance ). We further have that the autocorrelation is centro-symmetric, ${\bf a}(l)={\bf a}(-l),\,l=0,\dots,M-1,$ and via Wiener-Khinchin’s theorem that ${\bf a}(l),\,l=0,\dots,M-1,$ is related to ${\bf y}(n),\,n=1,\dots,N,$ via ${\bf y}(n)=$ $\langle\varphi_{n},\begin{bmatrix}{\bf a}(0)\,\dots\,{\bf a}(M-1)\,0\,{\bf a}(M-1)\,{\bf a}(M-2)\,\dots\,{\bf a}(1)\end{bmatrix}^{\mathsf{T}}\rangle.$

Ignoring the symmetry, the problem of recovering the sparse autocorrelation from the partial FMMs ${\bf y}$ can therefore be posed as

This is a well studied problem in compressive sensing (see for instance ) and using the result of [21, Thm. 1] it can be shown that if $N$ is prime and satisfies

then (9) has a unique solution. This because ${\bf a}(1),\,\dots\,,{\bf a}(M-1)$ contain $(\|{\bf x}_{0}\|_{0}^{2}-\|{\bf x}_{0}\|_{0})/2$ nonzero elements at most.

Finally, it was recently shown in that whenever there are no collisions in ${\bf x}_{0}$ and the following conditions are satisfied, then the autocorrelation uniquely defines ${\bf x}_{0}$:

$\|{\bf x}_{0}\|_{0}=6$ and ${\bf x}_{0}(i)\neq{\bf x}_{0}(j)$, for some $i,j\in\{i:i\in\{1,\dots,M\},\,{\bf x}_{0}(i)\neq 0\}$, or

$\|{\bf x}_{0}\|_{0}=6$ and ${\bf x}_{0}(i)={\bf x}_{0}(j)$, for all $i,j\in\{i:i\in\{1,\dots,M\},{\bf x}_{0}(i)\neq 0\}$. In this case, the autocorrelation uniquely defines ${\bf x}_{0}$ almost surely.

Hence, under the conditions of the theorem, the FMMs ${\bf y}$ uniquely define ${\bf a}$, and ${\bf a}$ uniquely defines ${\bf x}_{0}$, from which the theorem follows. ∎

Note that the theorem does not require the Fourier basis vectors to be selected deterministically or randomly and therefore holds for both.

IV Conclusion

Even though phase retrieval is a longstanding problem in optics it is still not well understood whether a collection of measurements provides an injective map or not. It was recently shown that the complement property gives necessary and sufficient conditions for the uniqueness of a real signal and a real collection of measurement vectors. Here we show that if the measurement vectors satisfy a weaker version of the complement property then a sought sparse signal can be guaranteed to be uniquely defined by associated intensity measurements. We also consider a complex collection of measurement vectors and Fourier magnitude measurements. We show that in general, $2(k^{2}-k+1)$ Fourier magnitude measurements suffice to guarantee uniqueness of a $k$-sparse signal.

Acknowledgment

Ohlsson is partially supported by the Swedish Research Council in the Linnaeus center CADICS, the European Research Council under the advanced grant LEARN, contract 267381, by a postdoctoral grant from the Sweden-America Foundation, donated by ASEA’s Fellowship Fund, and by a postdoctoral grant from the Swedish Research Council. Eldar is supported in part by the Israel Science Foundation under Grant no. 170/10, and by the Ollendorf Foundation.

References