TY - GEN

T1 - Covering radius and the Restricted Isometry Property

AU - Calderbank, Robert

AU - Jafarpour, Sina

AU - Nastasescu, Maria Monica

PY - 2011/12/21

Y1 - 2011/12/21

N2 - The Restricted Isometry Property or RIP introduced by Candes and Tao requires an n × p dictionary to act as a near isometry on all k-sparse signals. This paper provides a very simple condition under which a dictionary Φ (C) obtained by exponentiating codewords from a binary linear code C satisfies the RIP with high probability. The method is to bound the difference between the dictionary Φ(C) and a second dictionary A generated by a random Bernoulli process which is known to satisfy the RIP with high probability. The difference Δ-Φ (C) is controlled by the covering radius of C, a fundamental parameter that is bounded above by the number of weights in the dual code C ⊥ (the external distance of C). The main result complements a more sophisticated asymptotic analysis by Babadi and Tarokh of the distribution of eigenvalues of random submatrices of Φ(C). In this analysis, divergence from the distribution corresponding to the full Bernoulli matrix depends on a different fundamental parameter of C, namely the minimum distance of the dual code C ⊥.

AB - The Restricted Isometry Property or RIP introduced by Candes and Tao requires an n × p dictionary to act as a near isometry on all k-sparse signals. This paper provides a very simple condition under which a dictionary Φ (C) obtained by exponentiating codewords from a binary linear code C satisfies the RIP with high probability. The method is to bound the difference between the dictionary Φ(C) and a second dictionary A generated by a random Bernoulli process which is known to satisfy the RIP with high probability. The difference Δ-Φ (C) is controlled by the covering radius of C, a fundamental parameter that is bounded above by the number of weights in the dual code C ⊥ (the external distance of C). The main result complements a more sophisticated asymptotic analysis by Babadi and Tarokh of the distribution of eigenvalues of random submatrices of Φ(C). In this analysis, divergence from the distribution corresponding to the full Bernoulli matrix depends on a different fundamental parameter of C, namely the minimum distance of the dual code C ⊥.

UR - http://www.scopus.com/inward/record.url?scp=83655193006&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=83655193006&partnerID=8YFLogxK

U2 - 10.1109/ITW.2011.6089564

DO - 10.1109/ITW.2011.6089564

M3 - Conference contribution

AN - SCOPUS:83655193006

SN - 9781457704376

T3 - 2011 IEEE Information Theory Workshop, ITW 2011

SP - 558

EP - 562

BT - 2011 IEEE Information Theory Workshop, ITW 2011

T2 - 2011 IEEE Information Theory Workshop, ITW 2011

Y2 - 16 October 2011 through 20 October 2011

ER -