New Theoretical Results for LAD-Based Sparse Recovery Using Expanders
This paper studies sparse recovery using expander graphs in the context of the noisy linear model b = Ax0 +e, where x0 ∈ R<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><sup>n</sup></i> is an (approximately) sparse signal and A ∈ {0, 1}<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><sup>m×n</sup></i> is a measurement matrix derived from the biadjacency matrix of a lossless expander. Our key cont