Reviews: High Dimensional Linear Regression using Lattice Basis Reduction

The paper presents a novel method of exactly recovering a vector of coefficients in high-dimensional linear regression, with high probability as the dimension goes to infinity. The method assumes that the correct coefficients come from a finite discrete set of bounded rational values, but it does not - as is commonplace - assume that the coefficient vector is sparse. To achieve this, the authors extend a classical algorithm for lattice basis reduction. Crucially, this approach does not require the sample size to grow with the dimension, thus in certain cases the algorithm is able to recover the exact coefficient vector from just a single sample (with the dimension sufficiently large). A novel connection between high-dimensional linear regression and lattice basis reduction is the main strength of the paper.