  The lasso has become an important practical tool for high dimensional
regression as well as the object of intense theoretical investigation. But
despite the availability of efficient algorithms, the lasso remains
computationally demanding in regression problems where the number of variables
vastly exceeds the number of data points. A much older method, marginal
regression, largely displaced by the lasso, offers a promising alternative in
this case. Computation for marginal regression is practical even when the
dimension is very high. In this paper, we study the relative performance of the
lasso and marginal regression for regression problems in three different
regimes: (a) exact reconstruction in the noise-free and noisy cases when design
and coefficients are fixed, (b) exact reconstruction in the noise-free case
when the design is fixed but the coefficients are random, and (c)
reconstruction in the noisy case where performance is measured by the number of
coefficients whose sign is incorrect.
  In the first regime, we compare the conditions for exact reconstruction of
the two procedures, find examples where each procedure succeeds while the other
fails, and characterize the advantages and disadvantages of each. In the second
regime, we derive conditions under which marginal regression will provide exact
reconstruction with high probability. And in the third regime, we derive rates
of convergence for the procedures and offer a new partitioning of the ``phase
diagram,'' that shows when exact or Hamming reconstruction is effective.
