Kernel Reconstruction: an Exact Greedy Algorithm for Compressive Sensing

Compressive sensing is the theory of sparse signal recovery from undersampled measurements or observations. Exact signal reconstruction is an NP hard problem. A convex approximation using the l(1)-norm has received a great deal of theoretical attention. Exact recovery using the l(1) approximation is only possible under strict conditions on the measurement matrix, which are difficult to check. Many greedy algorithms have thus been proposed. However, none of them is guaranteed to lead to the optimal (sparsest) solution. In this paper, we present a new greedy algorithm that provides an exact sparse solution of the problem. Unlike other greedy approaches, which are only approximations of the exact sparse solution, the proposed greedy approach, called Kernel Reconstruction, leads to the exact optimal solution in less operations than the original combinatorial problem. An application to the recovery of sparse gene regulatory networks is presented.