High Dimensional Linear Regression using Lattice Basis Reduction

We consider a high dimensional linear regression problem where the goal is to efficiently recover an unknown vector \beta * from n noisy linear observations Y X \beta * W in R n, for known X in R {n \times p} and unknown W in R n. Unlike most of the literature on this model we make no sparsity assumption on \beta *. Instead we adopt a regularization based on assuming that the underlying vectors \beta * have rational entries with the same denominator Q. 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.