Math @ Duke

Publications [#235985] of Robert Calderbank
Papers Published
 Calderbank, R; Jafarpour, S; Nastasescu, M, Covering radius and the Restricted Isometry Property,
2011 IEEE Information Theory Workshop, ITW 2011
(2011),
pp. 558562 [doi]
(last updated on 2018/02/19)
Abstract: The Restricted Isometry Property or RIP introduced by Candes and Tao requires an n × p dictionary to act as a near isometry on all ksparse 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 ⊥. © 2011 IEEE.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

