# Lasso and Partially-Rotated Designs

arXiv: https://arxiv.org/abs/2505.11093 · HTML: https://mlsanity.com/paper/2505.11093/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 16 May 2025.

## Builds on (most cited first, 9 of 9)

- [Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimator](https://mlsanity.com/paper/1904.06288/) (2019)
- [High Dimensional Robust Sparse Regression](https://mlsanity.com/paper/1805.11643/) (2018)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers](https://mlsanity.com/paper/2111.02966/) (2021)
- [Compressed Sensing with Adversarial Sparse Noise via L1 Regression](https://mlsanity.com/paper/1809.08055/) (2018)
- [Feature Adaptation for Sparse Linear Regression](https://mlsanity.com/paper/2305.16892/) (2023)
- [Graph-based regularization for regression problems with alignment and highly-correlated designs](https://mlsanity.com/paper/1803.07658/) (2018)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)

## Abstract (arXiv)

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].