Lasso and Partially-Rotated Designs

We consider the sparse linear regression model y = X β +w, where X ∈ ℝn × d is the design, β ∈ ℝd is a k-sparse secret, and w ~ N(0, In) is the noise. Given input X and y, the goal is to estimate β. In this setting, the Lasso estimate achieves prediction error O(k log d / γ n), where γ is the restricted eigenvalue (RE) constant of X with respect to support(β). In this paper, we introduce a new textitsemirandom family of designs -- which we call textitpartially-rotated designs -- for which the RE constant with respect to the secret is bounded away from zero even when a subset of the design columns are arbitrarily correlated among themselves. As an example of such a design, suppose we start with some arbitrary X, and then apply a random rotation to the columns of X indexed by support(β). Let λmin be the smallest eigenvalue of frac1n Xsupport(β)^top Xsupport(β), where Xsupport(β) is the restriction of X to the columns indexed by support(β). In this setting, our results imply that Lasso achieves prediction error O(k log d / λmin n) with high probability. This prediction error bound is independent of the arbitrary columns of X not indexed by support(β), and is as good as if all of these columns were perfectly well-conditioned. Technically, our proof reduces to showing that matrices with a certain deterministic property -- which we call textitrestricted normalized orthogonality (RNO) -- lead to RE constants that are independent of a subset of the matrix columns. This property is similar but incomparable with the restricted orthogonality condition of [CT05].