488 – Hypothesis Testing When Signals Are Rare and Weak
Optimal Variable Selection and Noisy Adaptive Compressed Sensing
M. Ndaoud
CREST-ENSAE
A.B. Tsybakov
CREST-ENSAE
We consider variable selection (VS) based on $n$ observations from a linear regression model. The unknown parameter of the model is assumed to belong to the class $V$ of all $s$-sparse vectors in $R^p$ whose non-zero components are greater than $a > 0$. Variable selection in this context is an extensively studied problem. However, in the theory not much is known beyond the consistency of selection. For Gaussian design, which is important in the context of compressed sensing, necessary and sufficient conditions of consistency for some configurations of $n,p,s,a$ are available. They are achieved by the exhaustive search decoder, which is not realizable in polynomial time and requires the knowledge of $s$. This talk will study optimality in VS based on the Hamming risk criterion. The benchmark behavior is characterized by the minimax risk on the class $V$. For Gaussian design, we propose an adaptive algorithm independent of $s,a$, and of the noise level that nearly attains the value of the minimax risk. This algorithm is the first method, which is both realizable in polynomial time and consistent under the same (minimal) sufficient conditions as the exhaustive search decoder.