Wirtinger Flow for Blind Deconvolution from Random Initialization

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 $\mathcal{O}({\eta }^{-1}\log m+{\eta }^{-1}\log (1/ϵ))$ iterations when $m\gtrsim K^3{\log }^{11}m$. 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.