  Single-photon lidar has become a prominent tool for depth imaging in recent
years. At the core of the technique, the depth of a target is measured by
constructing a histogram of time delays between emitted light pulses and
detected photon arrivals. A major data processing bottleneck arises on the
device when either the number of photons per pixel is large or the resolution
of the time stamp is fine, as both the space requirement and the complexity of
the image reconstruction algorithms scale with these parameters. We solve this
limiting bottleneck of existing lidar techniques by sampling the characteristic
function of the time of flight (ToF) model to build a compressive statistic, a
so-called sketch of the time delay distribution, which is sufficient to infer
the spatial distance and intensity of the object. The size of the sketch scales
with the degrees of freedom of the ToF model (number of objects) and not,
fundamentally, with the number of photons or the time stamp resolution.
Moreover, the sketch is highly amenable for on-chip online processing. We show
theoretically that the loss of information for compression is controlled and
the mean squared error of the inference quickly converges towards the optimal
Cram\'er-Rao bound (i.e. no loss of information) for modest sketch sizes. The
proposed compressed single-photon lidar framework is tested and evaluated on
real life datasets of complex scenes where it is shown that a compression rate
of up-to 1/150 is achievable in practice without sacrificing the overall
resolution of the reconstructed image.
