Limits on Sparse Support Recovery via Linear Sketching with Random Expander Matrices

Linear sketching is a powerful tool for the problem of sparse signal recovery, having numerous applications such as compressive sensing, data stream computing, graph sketching, and routing. Motivated by applications where the \emph{positions} of the non-zero entries in a sparse vector are of primary interest, we consider the problem of \emph{support recovery} from a linear sketch taking the form $\Yv = \Xv\beta + \Zv$. We focus on a widely-used expander-based construction in the columns of the measurement matrix $\Xv \in \RR^{n \times p}$ are random permutations of a sparse binary vector containing $d \ll n$ ones and $n-d$ zeros. We provide a sharp characterization of the number of measurements required for an information-theoretically optimal decoder, thus permitting a precise comparison to the i.i.d.~Gaussian construction. Our findings reveal both positive and negative results, showing that the performance nearly matches the Gaussian construction at moderate-to-high noise levels, while being worse by an arbitrarily large factor at low noise levels.