Sparse Signal Recovery Using a Binary Program

Sparsity based signal recovery has seen great success in solving underdetermined systems of equations. This success is due, in large part, to a relaxation: the l0-norm is replaced by the l1-norm, which results in a convex problem. However, such a relaxation may lead to a suboptimal solution, one that may even be asymptotically biased. We propose formulating sparse signal recovery as a binary program, and we derive the conditions under which such a formulation perfectly recovers the signal support. This derivation equips us with a constraint on the dictionary's spectrum. However, designing such a dictionary is a combinatorial problem, so we suggest a heuristic which can be readily satisfied using the alternating projections algorithm. Applied to angle of arrival (AoA) estimation using a sensor array, we show how this paradigm outperforms both the basis pursuit l1-norm relaxation and the Matrix Pencil method.