- Rating
- 1(−1)
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The authors prove that Wirtinger flow solves blind deconvolution from a random initialization with high probability. Most previous studies have instead only been able to prove a local convergence guarantee, and relies on spectral initialization to enter the region of linear convergence. The theory of the paper gives an accurate and understandable description of the training dynamics, which consists of two phases: One initial phase where decay is slow, but the iterate slowly becomes more and more aligned with the ground truth. The authors give a bound on the length of this phase. After that, the iterate enters the region of local convergence.
The theoretical guarantee necessitates, along with some other standard assumptions, that the number of (Gaussian) measurements to grows as the cube of the effective signal dimension. This is likely overly pessimistic, as their empirical evaluation rather point to convergence with a linear amount of measurements.
Critical strengths
The paper provides an elegant analysis of an interesting problem.
Critical weaknesses
The style of presentation is sometimes in my opinion too compact. The proof of a result of this kind is necessarily very technical, but there are many places where many intermediate steps are left to the reader. This is of course per se fine, but there are a number of places where I can't reproduce the argument.
Questions for authors
As said in my 'weaknesses section', there are some steps in the argument I simply do not follow, despite trying my verý best. I do not say that there are errors - I very much suspect the reason I cannot reproduce the steps is incompetence and lack of experience with the particular problem. However, these points it makes it hard for me to fully endorse the correctness of the proof. The main idea of the proof is very plausible to me, and the important steps (e.g., the non-discrete argument population loss argument, and how the sample complexity comes to be) are fine.
I will therefore initially give a very conservative rating, despite finding the paper per se good. I am very open to change this rating a lot if the authors can answer the steps listed below.
- How are (49)-(50) derived from (54)-(57)? I simply cannot reproduce the correct argument.
- What is the definition of in Lemma 9.
- In the proof of Lemma 10, the bound 'after division with gives the first two inequalities below'. What are these inequalities? Is it (78),(79)?
- How does enter the inequality (73)? I genuinely cannot see it since there are no terms related to in the formula for in (47). Same question for in inequality (74).
- In the set of equalities on page 18 ( just after (76)), it seems like a generic constant turns into . Is this so? And if so, why is this OK?
- Just before step 2 in the same proof, the authors argue that . Two questions for this: Is the small meant to mean that the quantity not only is smaller than a constant, but ultimately decays when something changes? If so, what?
- Explain why shows that the inequality holds.
- The authors argue that the right-hand side of (82) is positive 'after reducing the numerical constants'. Which numerical constant? Since seems to be a generic constant that affect a lot of estimates in the proof, a justification here is warranted.
- Please explain why (71) implies that .
- In the sentence right after that, it is supposed that the 'norm threshold occurs first'. What does this mean?
- In the same paragraph, I do not follow the argument for why . I can only reproduce that .
- In the very end of step 2, the authors argue that , but the assumption in step 1 is , i.e., . Is this an issue?
- Can the authors explain in more detail in how they arrive at (87) using (49)?
And comments/questions that rather are open/future work:
- How much do the authors expect the bound to be improvable? Since there are methods that work under (e.g. nuclear norm minimization), the -term is indeed quite large.
- The formulation for blind deconvolution in the paper does not involve a convolution. Although it is standard to rewrite that problem into (1), it seems natural to at least mention the convolution formulation somewhere.
The manuscript needs a major revision before it is publishable.
After reading the updated version of the paper, as well as the responses to mine and other authors concern, I have decided to change my score. My reasons for this are two-fold.
The revised manuscript still does not provide a sufficiently clear and self-contained presentation of the arguments. The additional steps provided in the responses to my comments involve nontrivial arguments, and in some cases appear to rely on assumptions that were not explicitly stated in the original manuscript (e.g., that K is sufficiently large). Several parts of the proofs therefore remain difficult to verify and reproduce. In my opinion, the manuscript needs to go through a round of major revisions, where more care is taken to make the presentation understandable before it can be published.
Reviewer FC4u appears to have identified a significant error in the proof, which has led the authors to revise the main theorem. The resulting theorem is substantially weaker than the one in the original submission. In particular, the failure probability now decreases as (1/log(K), where K is the signal dimension. This is an extremely slow rate of decay, with potentially significant implications for the practical relevance of the result. To get an idea of how weak, let us assume a constant of 1 in the O-notation, we need a signal dimension of about 1.2⋅1030 (one million times the number of stars in the observable universe) to get a failure probability smaller than 1%.
My concerns are of a nature that I do not believe that they can be adequately addressed within the remaining discussion period. I will therefore maintain my revised score.