Optimal Sparsity Testing in Linear regression Model

Understand

We consider the problem of sparsity testing in the high-dimensional linear regression model.

• The problem is to test whether the number of non-zero components (aka the sparsity) of the regression parameter $\theta^*$ is less than or equal to $k_0$.
• We pinpoint the minimax separation distances for this problem, which amounts to quantifying how far a $k_1$-sparse vector $\theta^*$ has to be from the set of $k_0$-sparse vectors so that a test is able to reject the null hypothesis with high probability.
• Two scenarios are considered.