Math @ Duke

Publications [#235966] of Robert Calderbank
Papers Published
 Bajwa, WU; Calderbank, R; Jafarpour, S, Revisiting model selection and recovery of sparse signals using onestep thresholding,
2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
(2010),
pp. 977984 [doi]
(last updated on 2018/08/19)
Abstract: This paper studies nonasymptotic model selection and recovery of sparse signals in highdimensional, linear inference problems. In contrast to the existing literature, the focus here is on the general case of arbitrary design matrices and arbitrary nonzero entries of the signal. In this regard, it utilizes two easily computable measures of coherence  termed as the worstcase coherence and the average coherence  among the columns of a design matrix to analyze a simple, modelorder agnostic onestep thresholding (OST) algorithm. In particular, the paper establishes that if the design matrix has reasonably small worstcase and average coherence then OST performs nearoptimal model selection when either (i) the energy of any nonzero entry of the signal is close to the average signal energy per nonzero entry or (ii) the signaltonoise ratio (SNR) in the measurement system is not too high. Further, the paper shows that if the design matrix in addition has sufficiently small spectral norm then OST also exactly recovers most sparse signals whose nonzero entries have approximately the same magnitude even if the number of nonzero entries scales almost linearly with the number of rows of the design matrix. Finally, the paper also presents various classes of random and deterministic design matrices that can be used together with OST to successfully carry out nearoptimal model selection and recovery of sparse signals under certain SNR regimes or for certain classes of signals. ©2010 IEEE.


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

