Statistical-Physics-Based Reconstruction in Compressed Sensing

Popular Summary: When you want an image with 100×100-pixel resolution, how many imaging data points do you need? 10 000, the obvious answer seems to be. No, says compressed sensing, a branch of signal-processing science and computational statistics. This research branch develops methods of acquiring… Read Full Popular Summary

Popular Summary: When you want an image with 100×100-pixel resolution, how many imaging data points do you need? 10 000, the obvious answer seems to be. No, says compressed sensing, a branch of signal-processing science and computational statistics. This research branch develops methods of acquiring and reconstructing a signal that rely on fewer data-acquisition points or measurements than what was previously considered possible, and has enabled faster and more precise measurements in a wide range of applications, including cameras, computed tomography, magnetic-resonance imaging, and genome sequencing. Current techniques are, however, still not optimal, requiring more data points or measurements than necessary. In this interdisciplinary paper, we have designed and tested a new compressed-sensing strategy that allows us to go significantly beyond the known limits for data acquisition and signal reconstruction, by bringing methods and inspirations from statistical physics to bear on compressed sensing—a field that traditionally does not belong to physics.

Mathematically, the problem of compressed sensing is easy to formulate. The signal to be reconstructed is an N-component one, represented by a vectors (N can be viewed as the total number of pixels desired), and compressed sensing deals with signals that are “sparse,” with only a fraction (ρ₀) of the N components being nonzero. The actual acquired data is represented by an M-component vector, y, with M also being only a fraction α of N. y and s are connected linearly by a known mapping. Reconstruction of signal s then becomes a problem of performing the inverse mapping. Current strategies use linear-programming-based optimization to determine the right inverse mapping. But, they require more data points than would be absolutely necessary, i.e., α must be larger than ρ₀.

The strategy we have designed, called the seeded belief-propagation algorithm, approaches the signal acquisition and reconstruction in a radically different way. It views the ultimate signal to be reconstructed as the result of a sufficient sampling of a probabilistic Boltzmann-measure-like distribution, which depends on the mapping that corresponds to data-acquisition measurements and the acquired data points. Using a class of specially designed mappings that exploit the physics intuition about crystal nucleation and a sampling technique known to statistical physics as the belief-propagation algorithm, our new compressed-sensing protocols achieve, in a computationally efficient manner, exact reconstruction of the original signal, not only when α is larger than ρ₀, but also as α approaches ρ₀, in other words, as the number of acquired data points approaches the absolute minimum. In fact, the examples we have tested show that the gains are stunning.

We would like to think that our interdisciplinary approach breaks new ground in the field of compressed sensing, and we anticipate many further fundamental developments and practical applications.

^*Corresponding author;

fk@espci.fr