High Dimensional Linear Regression using Lattice Basis Reduction

Abstract

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^