Lasso and Partially-Rotated Designs

Abstract

We consider the sparse linear regression model $\mathbf{y}=X{\hat{I}}^2+\mathbf{w}$, where $X\in {\mathbb{R}}^{n\times d}$ is the design, ${\hat{I}}^2\in {\mathbb{R}}^d$ is a $k$-sparse secret, and $\mathbf{w}\sim N(0,I_n)$ is the noise. Given input $X$ and $\mathbf{y}$, the goal is to estimate ${\hat{I}}^2$. In this setting, the Lasso estimate achieves prediction error $O(k\log d/{\hat{I}}^{3}n)$, where ${\hat{I}}^3$ is the restricted eigenvalue (RE) constant of $X$ with respect to $\mathrm{support}({\hat{I}}^2)$. In this paper, we introduce a new $\text{semirandom}$ family of designs -- which we call $\text{partially-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 $\mathrm{support}({\hat{I}}^2)$. Let $\hat{I}{»}_{\min }$ be the smallest eigenvalue of $\frac{1}{n}{X}_{\mathrm{support}({\hat{I}}^2)}^{\top }{X}_{\mathrm{support}({\hat{I}}^2)}$, where $X_{\mathrm{support}({\hat{I}}^2)}$ is the restriction of $X$ to the columns indexed by $\mathrm{support}({\hat{I}}^2)$. In this setting, our results imply that Lasso achieves prediction error $O(k\log d/\hat{I}{»}_{\min }n)$ with high probability. This prediction error bound is independent of the arbitrary columns of $X$ not indexed by $\mathrm{support}({\hat{I}}^2)$, 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 $\text{restricted 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].

19 pages