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 = Ax ₀+e, where x ₀ ∈ R ⁿ is an (approximately) sparse signal and A ∈ {0, 1} ^m× ⁿ is a measurement matrix derived from the biadjacency matrix of a lossless expander. Our key contributions are threefold. First, we extend the (ℓ ₁, ℓ ₁)-Restricted Isometry Property (RIP) for regular lossless expanders to quasi-regular lossless expanders, providing a sharper tool for sparse recovery analysis. Leveraging this tool, we derive better bounds on the expected estimation error for two LAD (Least Absolute Deviations) type models. As an application in the link delay estimation problem, our theoretical results improve the recovery error in the literature. We present extensive numerical experiments that validate our theoretical findings, and demonstrate that the proposed ℓ ₁ regularized LAD method outperforms state-of-the-art methods when applied to a delayed signal with a larger number of substantial nonzero entries.