  This paper investigates the effect of the design matrix on the ability (or
inability) to estimate a sparse parameter in linear regression. More
specifically, we characterize the optimal rate of estimation when the smallest
singular value of the design matrix is bounded away from zero. In addition to
this information-theoretic result, we provide and analyze a procedure which is
simultaneously statistically optimal and computationally efficient, based on
soft thresholding the ordinary least squares estimator. Most surprisingly, we
show that the Lasso estimator -- despite its widespread adoption for sparse
linear regression -- is provably minimax rate-suboptimal when the minimum
singular value is small. We present a family of design matrices and sparse
parameters for which we can guarantee that the Lasso with any choice of
regularization parameter -- including those which are data-dependent and
randomized -- would fail in the sense that its estimation rate is suboptimal by
polynomial factors in the sample size. Our lower bound is strong enough to
preclude the statistical optimality of all forms of the Lasso, including its
highly popular penalized, norm-constrained, and cross-validated variants.
