Compressed sensing is triggering a major evolution in signal acquisition: 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. In order to make this groundbreaking improvement possible, compressed sensing deals with how measurements should be performed, and how, in a second step, to use computational power in order to reconstruct the original signal. Compressed sensing can be used for many applications (speeding up magnetic resonance imaging without the loss of resolution, performing X-ray scans with less radiation exposure, sensing and compressing data simultaneously, measurements in acoustic holography, in system biology, faster confocal microscopy, etc ...). Currently used measurement protocols and reconstruction techniques, however, are still limited to acquisition rates considerably higher than what is theoretically necessary.The aim of this project is to develop a new interdisciplinary approach to compressed sensing, based on a statistical physics inspired methodology, whose preliminary application by the PI already yield spectacular results. I propose to use both a new algorithm for the reconstruction algorithm, with a mean-field inspired “Belief Propagation” method, and a new class of compressed sensing measurement schemes, motivated by a statistical physics study of the problem and by the theory of crystal nucleation in first order transitions. For reasons detailed below, this statistical physics approach is extremely promising theoretical framework to tackle compressed sensing and I believe it can eventually lead to optimal performance. I expect that the progress we will make in this direction will be instrumental also for other inference and inverse problems at the crossroad between physics and computer science.