High Dimensional Linear Regression using Lattice Basis Reduction
This addresses regression in high dimensions for scenarios where sparsity is not applicable, offering a novel approach with theoretical guarantees, though it is incremental in applying lattice methods to this specific assumption.
The paper tackles high-dimensional linear regression without sparsity assumptions by assuming the unknown vector has rational entries with a common denominator, proposing a polynomial-time algorithm based on lattice basis reduction. It proves exact recovery under small noise, even with a single observation, and achieves near-optimal noise tolerance for Gaussian noise with n=o(p/log p).
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 \in \mathbb{R}^n$, for known $X \in \mathbb{R}^{n \times p}$ and unknown $W \in \mathbb{R}^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 \in \mathbb{Z}_{>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=o\left(p/\log p\right)$ and $Q$ sufficiently large, our algorithm tolerates a nearly optimal information-theoretic level of the noise.