Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection

David Gamarnik, Eren C. Kızıldağ, Ilias Zadik

We focus on the high-dimensional linear regression problem, where the algorithmic goal is to efficiently infer an unknown feature vector ${\beta }^{\ast }\in {\mathbb{R}}^p$ from its linear measur…