Phase Retrieval for Finitely-Supported Complex Measures via the Fourier Transform

We study the recovery of a finitely-supported complex measure $\mu =\sum j=1scj\delta tj$ from the magnitudes of linear measurements. The distribution $\mu$ is completely determined by the amplitude vector $c\in Cs$ and the support set $\{t1,t2,\dots ,ts\}\subset [0,\Lambda ]$, where $\Lambda >0$ is assumed to be known. We show that by using magnitudes of point evaluations of the Fourier transform $\mu ^$ of $\mu$ at $\{v1,v2,\dots ,vn\}\subset [-\Omega ,\Omega ]$, along with magnitudes of differences of modulated point evaluations of $\mu ^$, we can construct injective maps over the space of all such measures of support length at most $s$. We follow a measurement design by Alexeev et al. \cite{alexeev_bandeira_fickus_mixon_2014} whereby point evaluations of $|\mu ^|2$ are encoded as vertices of a graph, and edges of this graph correspond to interference measurements. In particular, if , $d\ge 3$ and there is a Ramanujan graph, $\Gamma$, that is $d$-regular on $n>6(1+\backslash sfrac6\ln (\backslash sfracs\Lambda \Omega ))s1-\backslash sfrac2d-1d$ vertices, then a set of $M=(d+1)n$ magnitude measurements associated with $\Gamma$ is sufficient for identifying $\mu$ up to an overall unimodular multiplicative constant.

Under some additional assumptions, we provide two recovery algorithms. The first algorithm is based on phase propagation and the Prony method. We show that the reconstruction problem can be reduced to applying linear inverses and finding roots of a polynomial in the case of exact measurements for almost every signal of the above form. In the second algorithm, at the cost of introducing a truncation error, we follow the technique presented by Cand`es and Fernandez-Granda in \cite{cand'es_fernandez-granda_2013} to show that the solution to a total-variation norm minimization problem defined by the given intensity measurements yields an approximation of $\mu$. We give explicit error bounds for recovery using this method depending on the number of given samples, and discuss the effect of noise in this approach.