A simple performance analysis of ℓ1 optimization in compressed sensing

It is well known that compressed sensing problems reduce to solving large under-determined systems of equations. If we choose the elements of the compressed measurement matrix according to some appropriate probability distribution and if the signal is sparse enough then the l₁ optimization can recover it with overwhelming probability (see, e.g. [4], [6], [7]). In fact, [4], [6], [7] establish (in a statistical context) that if the number of measurements is proportional to the length of the signal then there is a sparsity of the unknown signal proportional to its length for which the success of the l₁ optimization is guaranteed. In this paper we introduce a novel, very simple technique for proving this fact. Furthermore, in addition to being very simple the new technique provides very good values for proportionality constants. In some cases, the presented analysis, although very simple, provides the best currently known values for the proportionality constants.