  We investigate the high-dimensional regression problem using adjacency
matrices of unbalanced expander graphs. In this frame, we prove that the
$\ell_{2}$-prediction error and the $\ell_{1}$-risk of the lasso and the
Dantzig selector are optimal up to an explicit multiplicative constant. Thus we
can estimate a high-dimensional target vector with an error term similar to the
one obtained in a situation where one knows the support of the largest
coordinates in advance.
  Moreover, we show that these design matrices have an explicit restricted
eigenvalue. Precisely, they satisfy the restricted eigenvalue assumption and
the compatibility condition with an explicit constant.
  Eventually, we capitalize on the recent construction of unbalanced expander
graphs due to Guruswami, Umans, and Vadhan, to provide a deterministic
polynomial time construction of these design matrices.
