# High Dimensional Linear Regression using Lattice Basis Reduction

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2018.

## Built on by (most cited first, 5 of 5)

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [On the Hardness of Learning One Hidden Layer Neural Networks](https://mlsanity.com/paper/2410.03477/) (2024)

## Abstract (arXiv)

We consider a high dimensional linear regression problem where the goal is to efficiently recover an unknown vector β^* from n noisy linear observations Y=Xβ^*+W ∈ ℝn, for known X ∈ ℝn × p and unknown W ∈ ℝn. Unlike most of the literature on this model we make no sparsity assumption on β^*. Instead we adopt a regularization based on assuming that the underlying vectors β^* have rational entries with the same denominator Q ∈ mathbbZ>0. We call this Q-rationality assumption. We propose a new polynomial-time algorithm for this task which is based on the seminal Lenstra-Lenstra-Lovasz (LLL) lattice basis reduction algorithm. We establish that under the Q-rationality assumption, our algorithm recovers exactly the vector β^* for a large class of distributions for the iid entries of X and non-zero noise W. We prove that it is successful under small noise, even when the learner has access to only one observation (n=1). Furthermore, we prove that in the case of the Gaussian white noise for W, n=oleft(p/log pright) and Q sufficiently large, our algorithm tolerates a nearly optimal information-theoretic level of the noise.