  This paper studies non-asymptotic model selection for the general case of
arbitrary design matrices and arbitrary nonzero entries of the signal. In this
regard, it 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. It utilizes these two measures of coherence to provide an
in-depth analysis of a simple, model-order agnostic one-step thresholding (OST)
algorithm for model selection and proves that OST is feasible for exact as well
as partial model selection as long as the design matrix obeys an easily
verifiable property. One of the key insights offered by the ensuing analysis in
this regard is that OST can successfully carry out model selection even when
methods based on convex optimization such as the lasso fail due to the rank
deficiency of the submatrices of the design matrix. In addition, the paper
establishes that if the design matrix has reasonably small worst-case and
average coherence then OST performs near-optimally 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 signal-to-noise ratio in the measurement system is
not too high. Finally, two other key contributions of the paper are that (i) it
provides bounds on the average coherence of Gaussian matrices and Gabor frames,
and (ii) it extends the results on model selection using OST to low-complexity,
model-order agnostic recovery of sparse signals with arbitrary nonzero entries.
