Signal recovery from random projections

Abstract

Can we recover a signal <i>f</i>&isin;R^N from a small number of linear measurements? A series of recent papers developed a collection of results showing that it is surprisingly possible to reconstruct certain types of signals accurately from limited measurements. In a nutshell, suppose that <i>f</i> is compressible in the sense that it is well-approximated by a linear combination of <i>M</i> vectors taken from a known basis &Psi;. Then not knowing anything in advance about the signal, <i>f</i> can (very nearly) be recovered from about <i>M</i> log <i>N</i> generic nonadaptive measurements only. The recovery procedure is concrete and consists in solving a simple convex optimization program. In this paper, we show that these ideas are of practical significance. Inspired by theoretical developments, we propose a series of practical recovery procedures and test them on a series of signals and images which are known to be well approximated in wavelet bases. We demonstrate that it is empirically possible to recover an object from about 3<i>M</i>-5<i>M</i> projections onto <i>generically chosen</i> vectors with an accuracy which is as good as that obtained by the ideal <i>M</i>-term wavelet approximation. We briefly discuss possible implications in the areas of data compression and medical imaging.