Compressed sensing is triggering a major evolution in signal acquisition that changes completely the way we think about experiments and measurements. It indicates that most data, signals and images, that are usually compressible and have redundancy, can be reconstructed from much fewer measurements than what was usually considered necessary, resulting in a drastic gain of time, cost, and measurement precision. The idea consists in sampling a sparse signal using some random projections, and later using computational power for its exact reconstruction, so that only the necessary information is measured. This has been applied to many situations, from medical imagery and one-pixel-camera to confocal microscopy, acoustic holography or DNA micro-array analysis in biology. par In this talk, I will start by a general instruction to compressed sensing for physicists and discuss the state of the art reconstruction algorithms. Currently used reconstruction techniques are however limited to acquisition rates still higher than the true density of the signal. By using a mapping to a statistical physics problem, and motivated by the theory of crystal nucleation, I will introduce a new algorithm, and new measurement protocols, that achieves exact reconstruction of the signal even at measurement rates very close to the lowest possible ones. \ \ References: \ http://arxiv.org/abs/1109.4424 \ http://nuit-blanche.blogspot.com/p/teaching-compressed-sensing.html \ http://nuit-blanche.blogspot.com/2011/09/stunning-development-in-breaking-donoho.html