Binary sparse signal recovery with binary least squares

Abstract The problem of obtaining a 𝐾-sparse binary signal 𝐱 from <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi mathvariant="bold">y</m:mi> <m:mo>=</m:mo> <m:mrow> <m:mrow> <m:mi mathvariant="bold">Φ</m:mi> <m:mo>⁢</m:mo> <m:mi mathvariant="bold">x</m:mi> </m:mrow> <m:mo>+</m:mo> <m:mi mathvariant="bold-italic">ν</m:mi> </m:mrow> </m:mrow> </m:math> \mathbf{y}=\boldsymbol{\Phi}\mathbf{x}+\boldsymbol{\nu} is often encountered in communications and signal processing. Based on orthogonal least squares (OLS), a greedy algorithm guaranteeing the support recovery of a 𝐾-sparse binary signal is presented in this paper. Using the mutual coherence and restricted isometric properties of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi mathvariant="bold">Φ</m:mi> </m:math> \boldsymbol{\Phi} , sufficient conditions ensuring the exact recovery of the support of 𝐱 are given. Finally, compared with binary matching pursuit (BMP) and OLS, the simulation experiments imply the advantage of the proposed algorithm.