Explicit Matrices for Sparse Approximation

We show that girth can be used to certify that sparse compressed sensing matrices have good sparse approximation guarantees. This allows us to present the first deterministic measurement matrix constructions that have an optimal number of measurements for ℓ_1/ℓ_1 approximation. Our techniques are coding theoretic and rely on a recent connection of compressed sensing to LP relaxations for channel decoding.