Limits on Sparse Support Recovery via Linear Sketching with Random Expander Matrices
[edit]
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:149158, 2016.
Abstract
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 \emphpositions of the nonzero entries in a sparse vector are of primary interest, we consider the problem of \emphsupport recovery from a linear sketch taking the form \mathbfY = \mathbfXβ+ \mathbfZ. We focus on a widelyused expanderbased construction in the columns of the measurement matrix \mathbfX ∈\mathbbR^n \times p are random permutations of a sparse binary vector containing d ≪n ones and nd zeros. We provide a sharp characterization of the number of measurements required for an informationtheoretically 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 moderatetohigh noise levels, while being worse by an arbitrarily large factor at low noise levels.
Related Material



