Algorithmic Foundations for the Diffraction Limit

For more than a century and a half it has been widely-believed (but was never rigorously shown) that the physics of diffraction imposes certain fundamental limits on the resolution of an optical system. However our understanding of what exactly can and cannot be resolved has never risen above heuristic arguments which, even worse, appear contradictory. In this work we remedy this gap by studying the diffraction limit as a statistical inverse problem and, based on connections to provable algorithms for learning mixture models, we rigorously prove upper and lower bounds on how many photons we need (and how precisely we need to record their locations) to resolve closely-spaced point sources. We give the first provable algorithms that work regardless of the separation, but only for a constant number of point sources. Surprisingly, we show that when the number of point sources becomes large, there is a phase transition where the sample complexity goes from polynomial to exponential, and we pin down its location to within a universal constant that is independent of the number of point sources. Thus it is rigorously possible both to break the diffraction limit and yet to prove strong impossibility results depending on the setup. This is the first non-asymptotic statistical foundation for resolution in a model arising from first principles in physics, and helps clarify many omnipresent debates in the optics literature.