Math @ Duke

Publications [#235956] of Robert Calderbank
Papers Published
 Bajwa, WU; Calderbank, R; Jafarpour, S, Model selection: Two fundamental measures of coherence and their algorithmic significance,
IEEE International Symposium on Information Theory  Proceedings
(2010),
pp. 15681572 [doi]
(last updated on 2018/12/14)
Abstract: The problem of model selection arises in a number of contexts, such as compressed sensing, subset selection in linear regression, estimation of structures in graphical models, and signal denoising. This paper generalizes the notion of incoherence in the existing literature on model selection and introduces two fundamental measures of coherence  termed as the worstcase coherence and the average coherence  among the columns of a design matrix. In particular, it utilizes these two measures of coherence to provide an indepth analysis of a simple onestep thresholding (OST) algorithm for model selection. One of the key insights offered by the ensuing analysis is that OST is feasible for model selection as long as the design matrix obeys an easily verifiable property. In addition, the paper also characterizes the modelselection performance of OST in terms of the worstcase coherence, μ, and establishes that OST performs nearoptimally in the low signaltonoise ratio regime for N × C design matrices with μ ≈ O(N1/2). Finally, in contrast to some of the existing literature on model selection, the analysis in the paper is nonasymptotic in nature, it does not require knowledge of the true model order, it is applicable to generic (random or deterministic) design matrices, and it neither requires submatrices of the design matrix to have full rank, nor does it assume a statistical prior on the values of the nonzero entries of the data vector. © 2010 IEEE.


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

