We present nearly optimal minimax estimators for the classical problem of linear regression with soft sparsity constraints. Our result applies to any design matrix and represents the first result of this kind.

In the linear regression problem, one is given an m*n design matrix X and a
noisy observation y+g in R^{m} where y=Xθ for some unknown θ
in R^{n}, and g is the noise drawn from m-dimensional multivariate
Gaussian distribution. In addition, we assume that θ satisfies the soft
sparsity constraint, i.e. θ is in the unit L_{p} ball for p in
(0,1]. We are interested in designing estimators to minimize the maximum error
(or risk), measured in terms of the squared loss.

The main result of this paper is the construction of a novel family of
estimators, which we call the hybrid estimator, with risk O((log
n)^{1-p/2}) factor within the optimal for any m*n design matrix X as long
as n=Ω(m/log m). The hybrid estimator is a combination of two classic
estimators: the truncated series estimator and the least squares estimator. The
analysis is motivated by two recent work by Raskutti-Wainwright-Yu and
Javanmard-Zhang, respectively.