Algorithmic foundations for the diffraction limit

DOI10.1145/3406325.3451078MaRDI QIDQ6087020zbMATH OpenOpenAlexFDO

Authors Sitan Chen, Ankur Moitra

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.07659

zbMATH Keywords

mixture modelsextremal functionstensor decompositionFourier opticsmatrix pencil method

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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 the statistical and algorithmic complexity needed to resolve closely spaced point sources. In particular we show that there is a phase transition where the sample complexity goes from polynomial to exponential. Surprisingly, we show that this does not occur at the Abbe limit, which has long been presumed to be the true diffraction limit.

Recommendations

• On an algorithm for calculating diffraction integrals
• Algorithms yield upper bounds in differential algebra
• Computation considerations and fast algorithms for calculating the diffraction integral
• Algorithmic arguments in physics of computation
• Efficient algorithm for computing QFT bounds
• The computational complexity of linear optics
• The computational complexity of linear optics
• A mathematical theory of the computational resolution limit in one dimension
• A mathematical theory of computational resolution limit in multi-dimensional spaces
• Conjectures on spectral properties of ALIF algorithm

Cited in

(5)

• An Operator Theory for Analyzing the Resolution of Multi-illumination Imaging Modalities
• Short Communication: Weak Sparse Superresolution is Well-Conditioned
• A mathematical theory of super-resolution and two-point resolution
• Improved resolution estimate for the two-dimensional super-resolution and a new algorithm for direction of arrival estimation with uniform rectangular array
• Nonharmonic multivariate Fourier transforms and matrices: condition numbers and hyperplane geometry

This page was built for publication: Algorithmic foundations for the diffraction limit

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087020)