A conversation with Hau-Tieng Wu: Alternating Projections in Phase Retrieval

A few days ago Hau-tieng Wu, a colleague from Princeton that is now in Stanford, told me about an exciting new result of his in Phase Retrieval, he and his collaborators were able to show the convergence, to a global solution, of the Alternating Projections algorithm under very general conditions.

Given how difficult it seems to give good theoretical guarantees to the Alternating projection method, I was pretty excited with the news.

To put in prospective, alternative projections (also known, in a particular case, as Gerchberg-Saxton)  was proposed over 40 years ago and it seems to be the method of choice for practitioners. However, it seemed to lack theoretical guarantees until recently. To the best of my knowledge, the only known guarantees for convergence of methods of this sort is, for Gaussian measurements this paper, and the results that are going to be discussed below.

Nothing better than having one of the authors talking about his work so I decided to have Hau-tieng reply to a few questions, here is the small interview:

A.B.: How general is your result? Given a matrix and a vector that I want to recover from the absolute values of the entries in , what conditions are needed on in order to guarantee convergence of the Alternating projections method?

H.-T. W.: If is an matrix whose rows form a frame of , then, as long as and is generic (see the article for the definition. Essentially it means that with probability , the chosen frame enjoys the property), the Alternating Projections method converges to the solution up to a global phase. The issue is that it might converge at an extremely slow rate. That’s why we need phase synchronization to help.

A.B.: How slow can the convergence be? Does it converge in polynomial time?

H.-T. W.: Very slow. So slow that you might not see the convergence in you life time if you don’t have a good initial. That’s why we need phase synchronization to speed up. Also, it is not known whether it converges in polynomial time. However, in a paper by Lewis, Luke and Malick 2008 FOCM, the local linear convergence of the AP algorithm is discussed under some nontrivial conditions. This also motivates us to apply the phase synchronization approach to have a nice initial guess.

A.B.: If instead of measurements one has something like does it converge much faster? What about ?

H.-T. W.: We do not know it at this point.

A.B.: The condition is a bit mysterious. In particular, it is now known (see here) that suffices for injectivy. Do you think the guarantees for convergence of Alternating projections can be pushed all the way down to ?

H.-T. W.: Yes. The proof depends on the injectivity result. So with this new result by Edidin, it can go down to .

A.B.: What does the phase synchronization step achieve? Is it only usable in your particular application?

H.-T. W.: We use phase synchronization to offer a good initial of the AP algorithm. At this moment, we only apply the phase synchronization to the ptychography problem, and I am not sure if it helps for other cases. But we have to see.

A.B.: Can you say a few more words about the phase synchronization step? Is it similar to the synchronization used in the approach to Phase Retrieval using polarization?

H.-T. W.: It is motivated by the AP algorithm actually. Inspired by the convergence of the AP algorithm, we can write down a non-convex optimization problem reading like

By expanding , the relationship between pixels and diffractive images led us to build up a connection graph. Then the synchronization property of the connection graph Laplacian helps us to obtain a nice initial guess. Compared with the polarization approach, here we don’t need to design a new set of bases.

Advertisement