Consider the standard Gaussian linear regression model @math , where @math is a response vector and @math is a design matrix. Numerous work have been devoted to building efficient estimators of @math when @math is much larger than @math . In such a situation, a classical approach amounts to assume that @math is approximately sparse. This paper studies the minimax risks of estimation and testing over classes of @math -sparse vectors @math . These bounds shed light on the limitations due to high-dimensionality. The results encompass the problem of prediction (estimation of @math ), the inverse problem (estimation of @math ) and linear testing (testing @math ). Interestingly, an elbow effect occurs when the number of variables @math becomes large compared to @math . Indeed, the minimax risks and hypothesis separation distances blow up in this ultra-high dimensional setting. We also prove that even dimension reduction techniques cannot provide satisfying results in an ultra-high dimensional setting. Moreover, we compute the minimax risks when the variance of the noise is unknown. The knowledge of this variance is shown to play a significant role in the optimal rates of estimation and testing. All these minimax bounds provide a characterization of statistical problems that are so difficult so that no procedure can provide satisfying results.
@cite_30: The problem of consistently estimating the sparsity pattern of a vector β* ∈ RP based on observations contaminated by noise arises in various contexts, including signal denoising, sparse approximation, compressed sensing, and model selection. We analyze the behavior of l1-constrained quadratic programming (QP), also referred to as the Lasso, for recovering the sparsity pattern. Our main result is to establish precise conditions on the problern dimension p, the number k of nonzero elements in β*, and the number of observations n that are necessary and sufficient for sparsity pattern recovery using the Lasso. We first analyze the case of observations made using deterministic design matrices and sub-Gaussian additive noise, and provide sufficient conditions for support recovery and l∞-error bounds, as well as results showing the necessity of incoherence and bounds on the minimum value. We then turn to the case of random designs, in which each row of the design is drawn from a N(0, Σ) ensemble. For a broad class of Gaussian ensembles satisfying mutual incoherence conditions, we compute explicit values of thresholds 0 0, if n > 2(θu + δ)k log(p - k), then the Lasso succeeds in recovering the sparsity pattern with probability converging to one for large problems, whereas for n < 2(θl - δ)k log(p - k), then the probability of successful recovery converges to zero. For the special case of the uniform Gaussian ensemble (Σ = I p×p), we show that θl = θu = 1, so that the precise threshold n = 2k log (p - k) is exactly determined.
Support estimation. In a non-ultra high dimensional setting it is known @cite_30 that under some assumptions on the design @math (e.g. each component of @math is drawn from iid. standard normal distribution) the support of a @math -sparse vector @math is recoverable with high probability if where @math is a numerical constant. In an ultra-high dimensional setting, even if it is not possible to estimate the support of @math with high probability. Observe that the condition ) is much stronger than ). In fact, it is not even possible to reduce drastically the dimension of the problem without forgetting relevant variables with positive probability. More precisely, for any dimension reduction procedure that selects a subset of variables @math of size @math with some @math (described in Proposition ), we have @math with probability away from zero (see Proposition ). Thus, it is almost hopeless to have a reliable estimation of the support of @math even if @math is large. This impossibility of dimension reduction for ultra-high dimensional problems is numerically illustrated in Section .