Compressed sensing is a signal processing method that acquire data directly in a compressed form. This allows one to make less measurements that what is usually considered needed to record a signal, enabling faster and more precise measurement protocols in a wide range of applications. Current techniques, however, still require a number of measurements higher than necessary.

We design a new procedure which is able to reconstruct exactly the signal with a number of measurements that approaches the theoretical limit in the limit of large systems. It is based on the joint use of three essential ingredients: a probabilistic approach to signal reconstruction, a message-passing algorithm adapted from belief propagation, and a careful design of the measurement matrix inspired from the theory of crystal nucleation. The performance of this new algorithm is analyzed by statistical physics methods.