A Caltech Library Service

Explicit Matrices for Sparse Approximation

Khajehnejad, Amin and Tehrani, Arash Saber and Dimakis, Alexandros G. and Hassibi, Babak (2011) Explicit Matrices for Sparse Approximation. In: 2011 IEEE International Symposium on Information Theory Proceedings. IEEE , Piscataway, NJ, pp. 469-473. ISBN 978-1-4577-0596-0.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2011 IEEE. Date of Current Version: 03 October 2011.
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number12289109
Record Number:CaltechAUTHORS:20120405-093333989
Persistent URL:
Official Citation:Khajehnejad, A.; Saber Tehrani, A.; Dimakis, A.G.; Hassibi, B.; , "Explicit matrices for sparse approximation," Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on , vol., no., pp.469-473, July 31 2011-Aug. 5 2011 doi: 10.1109/ISIT.2011.6034170 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29990
Deposited By: Ruth Sustaita
Deposited On:05 Apr 2012 16:53
Last Modified:03 Oct 2019 03:46

Repository Staff Only: item control page