Minimum entropy pursuit: Noise analysis

Universal compressed sensing algorithms recover a “structured” signal from its under-sampled linear measurements, without knowing its distribution. The recently developed minimum entropy pursuit (MEP) optimization suggests a framework for developing universal compressed sensing algorithms. In the noiseless setting, among all signals that satisfy the measurement constraints, MEP seeks the “simplest”. In this work, the effect of noise on the performance of the relaxed version of MEP optimization, namely Lagrangian-MEP, is studied. It is proved that the performance the Lagrangian-MEP algorithm is robust to small additive noise.