High Dimensional Linear Regression using Lattice Basis Reduction

MaRDI QIDQ6299223zbMATH OpenFDO

Authors David Gamarnik, Ilias Zadik

Publication date 18 March 2018

Abstract: We consider a high dimensional linear regression problem where the goal is to efficiently recover an unknown vector $$ from $n$ noisy linear observations $$, for known $Xinmathbb{R}^{nimesp}$ and unknown $Winmathbb{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 $Qinmathbb{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=oleft(p/logpight)$ and $Q$ sufficiently large, our algorithm tolerates a nearly optimal information-theoretic level of the noise.

This page was built for publication: High Dimensional Linear Regression using Lattice Basis Reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6299223)