Abstract
This paper studies non-asymptotic model selection and recovery of sparse signals in high-dimensional, 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 worst-case coherence and the average coherence - among the columns of a design matrix to analyze a simple, model-order agnostic one-step thresholding (OST) algorithm. In particular, the paper establishes that if the design matrix has reasonably small worst-case and average coherence then OST performs near-optimal 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 signal-to-noise 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 near-optimal model selection and recovery of sparse signals under certain SNR regimes or for certain classes of signals.