Model Selection: Two Fundamental Measures of Coherence and Their Algorithmic Significance

Download Now Date Added: Apr 2010
Format: PDF

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 worst-case coherence and the average coherence - among the columns of a design matrix. In particular, it utilizes these two measures of coherence to provide an in-depth analysis of a simple One-Step Thresholding (OST) algorithm for model selection.