  We characterize the fundamental limits of coded aperture imaging systems up
to universal constants by drawing upon a theorem of Nazarov regarding Fourier
transforms. Our work is performed under a simple propagation and sensor model
that accounts for thermal and shot noise, scene correlation, and exposure time.
Focusing on mean square error as a measure of linear reconstruction quality, we
show that appropriate application of a theorem of Nazarov leads to essentially
optimal coded apertures, up to a constant multiplicative factor in exposure
time. Additionally, we develop a heuristically efficient algorithm to generate
such patterns that explicitly takes into account scene correlations. This
algorithm finds apertures that correspond to local optima of a certain
potential on the hypercube, yet are guaranteed to be tight. Finally, for i.i.d.
scenes, we show improvements upon prior work by using spectrally flat sequences
with bias. The development focuses on 1D apertures for conceptual clarity; the
natural generalizations to 2D are also discussed.
