Convolutional Phase Retrieval
We study the convolutional phase retrieval problem, which considers recovery of an unknown signal x ∈ C n from m measurements consisting of the magnitude of its cyclic convolution with a known kernel a of length m. This model is motivated by applications to channel estimation, optics, and underwater acoustic communication, where the signal of interest is acted on by a given channel/filter, and phase information is difficult or impossible to acquire. We show that when a is random and m is sufficiently large, x can be efficiently recovered up to a global phase using a combination of spectral initialization and generalized gradient descent. The main challenge is coping with dependencies in the measurement operator; we overcome this challenge by using ideas from decoupling theory, suprema of chaos processes and the restricted isometry property of random circulant matrices, and recent analysis for alternating minimizing methods.
The authors of the article consider phase retrieval problems where the measurements have a specific form: they are the convolution of the n-dimensional input signal x with a random filter of length m. The authors show that, provided that m is larger than O(n), up to log factors, and up to a term that is related with the sparsity of x in the Fourier domain, a simple non-convex algorithm can solve such problems with high probability.
The proof is quite technical. Indeed, the measurement vectors are highly correlated with one another. To overcome this difficulty, the authors use "decoupling techniques", together with results from [Rauhut, 2010] and [Krahmer, Mendelson, Rauhut, 2014].
I liked this article. I had not realized it was so complex to prove the convergence of a simple non-convex phase retrieval method in a very structured case, and, in my opinion, it is good that it has been done. The result by itself is interesting, and the proof techniques developed by the authors seem general enough to me so that they can be reused in other settings.
As previously said, the proof is quite technical, and long. There are 38 pages in the appendix. I tried to read as much of it as possible, but, given the time constraints of the review process, I certainly did not have the time to deeply understand everything. However, what I read seems both clear and solid.
The organization is also good. However, maybe the authors could discuss in more detail the case of coded diffraction patterns ([CLS15b]). Indeed, the case of phase retrieval with coded diffraction patterns is, at least at first sight, very similar to the case considered in the article: seen in the Fourier domain, coded diffraction patterns consist in convolving the input signal with (m/n) random filters of length n, while, in convolutional phase retrieval, the input signal is convolved with a single random filter of length m. I would appreciate the authors to compare their result and their proof techniques with the ones obtained for coded diffraction patterns.
Minor remarks and typos:
- Before Equation (4): add "that"?
- l.95 (and also in the "basic notations" paragraph of the appendix): ", because" should be ". Because".
- Paragraph 3.1: I did not know the name "alternating direction method". I think that "alternating projection method" is more common.
- Equation (12), and the previous two: "i\phi" is missing in the exponential function.
- l.180: ". Controlling" should be ", controlling".
- l. 209: "are not" should be "is not".
- Equation (19) (and the one after Equation (46) in the appendix): it took me a while to understand why this equation was true. Maybe it could be proved?
- l.220: "this control obtains" should be "we obtain this control".
- Equations (21) and (23): \mathcal{Q} should be \hat\mathcal{L}.
- The paragraph starting at line 244 seems a bit redundant with the explanations around Equation (22).
- Experiments: the main theorem says that, when x is proportional to the all-one vector, the initialization step still works, but the local descent does not. It would be nice to add an experiment that checks whether this is really what happens in numerical simulations.
- [CC15] has been published.
- The accent on "Candès" is missing in some of the bibliography entries.
- Appendix, l.58: "we proof" should be "we prove".
- Proposition 2.2: some "that" and "such that" could be added.
- l.92: "be" should be "is".
- l.150: I do not understand "for \gamma_2 functional of the set \mathcal{A}".
- Lemma 3.11: the last equation contains a \sqrt{\delta} while, in the statement, it is a \delta (no square root).
- l.202: I think that a "1/m" is missing in front of the expectation.
- l.217: "for w" should be "for all w".
- l.220: "define" should be "be defined".
- l.222: "define" should be "defined".
- l.224: "is constant" should be "is a constant".
- Equation after line 226: I think that there should be no parentheses inside the sup.
- Theorem 4.3: "are" should be "be".
- l.268: a word is missing before "that".
- Second line of the equation after line 278: the upper bound in the second integral should depend on d, not v.
- l. 279: "where the" should be "where in the", and "Choose" should be "choosing".
- Equation after line 292: I do not understand why the first inequality is true.
- l. 297: "so that" should be removed.
- l.305: "is complex" should be "is a complex".
- Equation just before line 326: there should be parentheses aroung the logarithms.
- Lemma 5.3: I do not understand the meaning of the first inequality: what is the difference between the first and the second term?
- l.466: "is close" should be "are close".
- l.481: "are defined" should be "is defined".
- l.484 and 486: "first" and "second" have been exchanged.
- I think that "we have [Equation] holds" (used multiple times) could be replaced with "we have that [Equation] holds" or simply "[Equation] holds".
- Equation after line 492: it could be said that it is a consequence of Lemma 6.2.
- Lemma 6.5, main equation: a multiplicative constant is missing before \delta.
- Equation after l.510, sixth line and after, until the end of the proof: the \leq sign should be a \geq sign.
- Equation after l.513: why w^{(r)}? Also, I think that there should maybe be close to 1 multiplicative constants before the last two terms of the sum.
- Equation after l.551: I do not understand the presence of ||x||.
- Lemma 6.3 and lemma 8.1 are not perfectly identical (there is a 2 in 6.3 that becomes a 2+\epsilon in 8.1).
- References: the name of the authors is missing in reference [led07].