Evolutionary Algorithm for Compressive Sensing

This paper presents a non–traditional approach to compressive sensing, by developing an evolutionary algorithm–based method for signal reconstruction. Previous work in signal reconstruction in compressive sensing focused primarily on framing the problem as a convex optimisation that minimises the 1 norm of the signal. Minimising the 2 norm does not help as it leads to a non–sparse solution. Minimising the 0 norm is known to be NP–complete, thereby requiring exhaustive enumeration which is computationally prohibitive. Our approach is different from the methods adopted in the literature and is capable of handling 0–, 1– or 2–norm minimisation, and linear or nonlinear combinations thereof, in the same framework, yielding fairly good signal recovery with high probability. We provide empirical results on a number of test problems.