  We present estimators for a well studied statistical estimation problem: the
estimation for the linear regression model with soft sparsity constraints
($\ell_q$ constraint with $0<q\leq1$) in the high-dimensional setting. We first
present a family of estimators, called the projected nearest neighbor estimator
and show, by using results from Convex Geometry, that such estimator is within
a logarithmic factor of the optimal for any design matrix. Then by utilizing a
semi-definite programming relaxation technique developed in [SIAM J. Comput. 36
(2007) 1764-1776], we obtain an approximation algorithm for computing the
minimax risk for any such estimation task and also a polynomial time nearly
optimal estimator for the important case of $\ell_1$ sparsity constraint. Such
results were only known before for special cases, despite decades of studies on
this problem. We also extend the method to the adaptive case when the parameter
radius is unknown.
