  Preconditioning is a technique from numerical linear algebra that can
accelerate algorithms to solve systems of equations. In this paper, we
demonstrate how preconditioning can circumvent a stringent assumption for sign
consistency in sparse linear regression. Given $X \in R^{n \times p}$ and $Y
\in R^n$ that satisfy the standard regression equation, this paper demonstrates
that even if the design matrix $X$ does not satisfy the irrepresentable
condition for the Lasso, the design matrix $F X$ often does, where $F \in
R^{n\times n}$ is a preconditioning matrix defined in this paper. By computing
the Lasso on $(F X, F Y)$, instead of on $(X, Y)$, the necessary assumptions on
$X$ become much less stringent.
  Our preconditioner $F$ ensures that the singular values of the design matrix
are either zero or one. When $n\ge p$, the columns of $F X$ are orthogonal and
the preconditioner always circumvents the stringent assumptions. When $p\ge n$,
$F$ projects the design matrix onto the Stiefel manifold; the rows of $F X$ are
orthogonal. We give both theoretical results and simulation results to show
that, in the high dimensional case, the preconditioner helps to circumvent the
stringent assumptions, improving the statistical performance of a broad class
of model selection techniques in linear regression. Simulation results are
particularly promising.
