My mind was blown today by the most remarkable solution to the phase-retrieval problem. (This is the problem of inferring the phase of a Fourier Transform given only the squared amplitude, as comes up in diffraction microscopy.) The solution is a chaotic iterated map, designed such that its fixed points are (related to) solutions to the equation, and such that its dynamics is attracted to those fixed points. The paper we found it in doesn't explain how they found the map or how they constructed it or how they tested it, but it just straight-up rocks on our test problems. And these problems are supposed to be officially NP-Hard. That is, the chaotic map takes us to the correct solution (we have a certificate, as it were) with very high probability, in a problem that is supposed to be combinatorically impossible. How this relates to optimization, I don't understand: The map is not justified as an optimizer of any specific objective function. How this relates to MCMC is possibly interesting: An MCMC is like a stochastic iterated map. Magland ended the day very excited about the breakthrough, even though it means that all the code he has been building and testing is now (probably) obviated.
No comments:
Post a Comment