Preconditioning to comply with the Irrepresentable Condition

Abstract

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 $FX$ often does, where $F\in R^{n\times 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. Our preconditioner $F$ ensures that the singular values of the design matrix are either zero or one. When $n\ge p$, the columns of $FX$ 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 $FX$ 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.

39 pages, 6 figures

References in corpus (5)

• Nearly unbiased variable selection under minimax concave penalty
• Simultaneous analysis of Lasso and Dantzig selector
• High-dimensionality effects in the Markowitz problem and other quadratic programs with linear constraints: Risk underestimation
• "Pre-conditioning" for feature selection and regression in high-dimensional problems
• OEM for least squares problems

Cited by in corpus (7)

• Sparse Identification of Truncation Errors
• DECOrrelated feature space partitioning for distributed sparse regression
• On pattern recovery of the fused Lasso
• On the consistency theory of high dimensional variable screening
• A note relating ridge regression and OLS p-values to preconditioned sparse penalized regression
• A Greedy Homotopy Method for Regression with Nonconvex Constraints
• Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees