acceptodds
Withdrawn from ICLR 2027

Wirtinger Flow for Blind Deconvolution from Random Initialization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

This paper studies the dynamics of Wirtinger flow (or gradient descent) for solving blind deconvolution from a random initialization. For bilinear measurements, we prove that the gradient method reaches an -accurate solution in iterations when . The analysis reveals two stages. During Stage I, the mismatch between the two vectors and their orthogonal components decay, allowing a weak common signal component to become dominant. Once the iterates enter the local region, they converge linearly during Stage II. We further extend the algorithm and the local analysis to blind deconvolution and demixing, where the update has a contraction coefficient independent of the source condition number. Numerical experiments demonstrate the main findings of our analysis.

Primary area:
optimization
Keywords:
random initialization, blind deconvolution, nonconvex optimization

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_vT2rOpenReview ↗
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 m≥K3m\geq K^3 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.

  1. How are (49)-(50) derived from (54)-(57)? I simply cannot reproduce the correct argument.
  2. What is the definition of E+\mathcal{E}^+ in Lemma 9.
  3. In the proof of Lemma 10, the bound ∣St+1−at2St∣≤…|S_{t+1}-a_t^2S_t|\leq \dots 'after division with StS_t gives the first two inequalities below'. What are these inequalities? Is it (78),(79)?
  4. How does DtD_t enter the inequality (73)? I genuinely cannot see it since there are no terms related to dd in the formula for s+s^+ in (47). Same question for EtE_t in inequality (74).
  5. In the set of equalities on page 18 ( just after (76)), it seems like a generic constant cc turns into 22. Is this so? And if so, why is this OK?
  6. Just before step 2 in the same proof, the authors argue that eC/LS0)=o(1)e^{C/L}S_0)=o(1). Two questions for this: Is the small oo meant to mean that the quantity not only is smaller than a constant, but ultimately decays when something changes? If so, what?
  7. Explain why η/rt2≤c/L3\eta/r_t^2\leq c/L^3 shows that the inequality log(1+u)≥u−Cu2log(1+u)\geq u-Cu^2 holds.
  8. The authors argue that the right-hand side of (82) is positive 'after reducing the numerical constants'. Which numerical constant? Since CC seems to be a generic constant that affect a lot of estimates in the proof, a justification here is warranted.
  9. Please explain why (71) implies that Φ(z0)≥−CL\Phi(z_0)\geq - CL.
  10. In the sentence right after that, it is supposed that the 'norm threshold occurs first'. What does this mean?
  11. In the same paragraph, I do not follow the argument for why Phi(zt)≥Φ(1)Phi(z_t)\geq \Phi(1). I can only reproduce that Φ(zt)−Phi(z0)≥CL2−O(log⁡(L)/L\Phi(z_t)-Phi(z_0)\geq CL^2- \mathcal{O}(\log(L)/L.
  12. In the very end of step 2, the authors argue that rt2≥c/L2r_t^2\geq c/L^2, but the assumption in step 1 is rt2≥1/L2r_t^2\geq 1/L^2, i.e., c=1c=1. Is this an issue?
  13. Can the authors explain in more detail in how they arrive at (87) using (49)?

And comments/questions that rather are open/future work:

  1. How much do the authors expect the bound m≥CK3⋅polylog(m,K)m\geq C K^3 \cdot \mathrm{polylog}(m,K) to be improvable? Since there are methods that work under m≥CKpolylog(m,K)m\geq C K\mathrm{polylog}(m,K) (e.g. nuclear norm minimization), the K3K^3-term is indeed quite large.
  2. 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.
1 comment
Reviewer_vT2rOpenReview ↗

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.

  1. 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 KK 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.

  2. 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)(1/\log(K), where KK 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 11 in the O\mathcal{O}-notation, we need a signal dimension of about 1.2⋅10301.2\cdot 10^30 (one million times the number of stars in the observable universe) to get a failure probability smaller than 1%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.

Reviewer_CPoMOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The authors study a data independent initialization of the Wirtinger flow approach for the blind deconvolution problem. The authors show that the iterates reach a local (i.e. epsilon accurate) region in O(\log(m)+\log(1/epsilon)) steps and then converge linearly to the ground truth.

Critical strengths

The contribution is clear although minor.

Critical weaknesses

Abstract

  • The abstract has to be rewritten.
  • What is K? What is m? in particular, what is \eta ? you need to introduce the parameters of the problem..
  • lines 15 - 16: “The mismatch between the two vectors and their orthogonal components decay” —> Between what two vectors ?
  • allowing a weak signal component to become dominant. which weak signal ?
  • lines 19-20 you say that you extend the analysis from bilinear measurements to blind deconvolution and demixing while these seem to me as two particular cases of bilinear measurements

Introduction

  • lines 61-62: “This produces dynamics beyond those of symmetric UU^H” —> this is not clear to me

Randomly initialized wirtinger flow for blind deconvolution

  • line 115 - 116: your notation \overline{c} is undefined. From what I understand \overline{c} is any constant such that c/\overline{c} = 1 ? Same comment for Equation (6). Shouldn’t the minimum be taken with respect to c and \overline{c} ?

Additional typos:

  • line 90: “several of these works prove convergence from random initializationt” —> “initialization”

References:

[1] Ahmed, A., Cosse, A., & Demanet, L. (2015, December). A convex approach to blind deconvolution with diverse inputs. In 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) (pp. 5-8). IEEE.

[2] Ahmed, A. & Demanet, L. Leveraging diversity and sparsity in blind deconvolution. IEEE Transactions on Information Theory, 2018, vol. 64, no 6, p. 3975-4000.

[3] Boumal, N., Voroninski, V., & Bandeira, A. S. (2020). Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs. Communications on Pure and Applied Mathematics, 73(3), 581-608.

Questions for authors

see weaknesses

Reviewer_FC4uOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper claims to establish global convergence guarantees for Wirtinger flow in blind deconvolution from random initialization. The authors claim that the algorithm exhibits two-stage convergence, reaching a local neighborhood of the ground truth before converging linearly. The paper further claims that the local convergence rate for blind deconvolution and demixing is independent of the source condition number.

Critical strengths

NA

Critical weaknesses
  1. Sample complexity. Theorem 1 requires m≳K3log⁡11mm\gtrsim K^3\log^{11}m, whereas near-linear sample complexity has already been established for closely related blind deconvolution.
  2. Issues in the proof. The proof contains several errors. In particular, equation (51) neglects the deterministic balancing error, and the contraction argument in equation (80) is not justified. Moreover, the success probability in Theorem 1 is inconsistent with Lemma 12.
Questions for authors

NA

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.