Math @ Duke

Publications [#236001] of Robert Calderbank
Papers Published
 Jafarpour, S; Duarte, MF; Calderbank, R, Beyond worstcase reconstruction in deterministic compressed sensing,
IEEE International Symposium on Information Theory  Proceedings
(2012),
pp. 18521856 [doi]
(last updated on 2018/05/21)
Abstract: The role of random measurement in compressive sensing is analogous to the role of random codes in coding theory. In coding theory, decoders that can correct beyond the minimum distance of a code allow random codes to achieve the Shannon limit. In compressed sensing, the counterpart of minimum distance is the spark of the measurement matrix, i.e., the size of the smallest set of linearly dependent columns. This paper constructs a family of measurement matrices where the columns are formed by exponentiating codewords from a classical binary errorcorrecting code of block length M. The columns can be partitioned into mutually unbiased bases, and the spark of the corresponding measurement matrix is shown to be O(√M) by identifying a configuration of columns that plays a role similar to that of the Dirac comb in classical Fourier analysis. Further, an explicit basis for the null space of these measurement matrices is given in terms of indicator functions of binary selfdual codes. Reliable reconstruction of ksparse inputs is shown for k of order M/log(M) which is best possible and far beyond the worst case lower bound provided by the spark. © 2012 IEEE.


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

