  We consider a sparse linear regression model Y=X\beta^{*}+W where X has a
Gaussian entries, W is the noise vector with mean zero Gaussian entries, and
\beta^{*} is a binary vector with support size (sparsity) k. Using a novel
conditional second moment method we obtain a tight up to a multiplicative
constant approximation of the optimal squared error
\min_{\beta}\|Y-X\beta\|_{2}, where the minimization is over all k-sparse
binary vectors \beta. The approximation reveals interesting structural
properties of the underlying regression problem. In particular, a) We establish
that n^*=2k\log p/\log (2k/\sigma^{2}+1) is a phase transition point with the
following "all-or-nothing" property. When n exceeds n^{*},
(2k)^{-1}\|\beta_{2}-\beta^*\|_0\approx 0, and when n is below n^{*},
(2k)^{-1}\|\beta_{2}-\beta^*\|_0\approx 1, where \beta_2 is the optimal
solution achieving the smallest squared error. With this we prove that n^{*} is
the asymptotic threshold for recovering \beta^* information theoretically. b)
We compute the squared error for an intermediate problem
\min_{\beta}\|Y-X\beta\|_{2} where minimization is restricted to vectors \beta
with \|\beta-\beta^{*}\|_0=2k \zeta, for \zeta\in [0,1]. We show that a lower
bound part \Gamma(\zeta) of the estimate, which corresponds to the estimate
based on the first moment method, undergoes a phase transition at three
different thresholds, namely n_{\text{inf,1}}=\sigma^2\log p, which is
information theoretic bound for recovering \beta^* when k=1 and \sigma is
large, then at n^{*} and finally at n_{\text{LASSO/CS}}. c) We establish a
certain Overlap Gap Property (OGP) on the space of all binary vectors \beta
when n\le ck\log p for sufficiently small constant c. We conjecture that OGP is
the source of algorithmic hardness of solving the minimization problem
\min_{\beta}\|Y-X\beta\|_{2} in the regime n<n_{\text{LASSO/CS}}.
