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 three stringent assumptions for various types of consistency in sparse linear regression. Given X∈Rn×p and Y∈Rn that satisfy the standard regression equation, this paper demonstrates that even if the design matrix X does not satisfy the irrepresentable condition, the restricted eigenvalue condition, or the restricted isometry property, the design matrix FX often does, where F∈Rn×n is a preconditioning matrix defined in this paper. By computing the Lasso on (FX,FY), instead of on (X, Y ), the necessary assumptions on X become much less stringent. Crucially, left multiplying the regression equation by F does not change β, the vector of unknown coefficients.

      Our preconditioner F ensures that the singular values of the design matrix are either zero or one. When n ≥ p, the columns of FX are orthogonal and the preconditioner always circumvents the stringent assumptions. When p ≥ n, F projects the design matrix onto the Stiefel manifold; the rows of F X are orthogonal. The Stiefel manifold is a bounded set and we show that most matrices in this set satisfy the the stringent assumptions. Simulation results are particularly promising.

      As an example of preconditioning technique, I also talk about my recent work on the analysis of the fused Lasso. We find that in general, the FLSA might not be able to recover the signal pattern.  We then apply the newly developed preconditioning method – Puffer Transformation  on the transformed Lasso problem. We call the new methodthepreconditionedfusedLasso and we give non-asymptotic results for this method. Results show that when the signal jump strength (signal difference between two neighboring groups) is big and the noise level is small, our preconditioned fused Lasso estimator always gives the correct pattern with high probability.