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

We consider the high-dimensional linear regression problem, where the algorithmic goal is to efficiently infer an unknown feature vector <tex-math notation="LaTeX">β *∈ Rᵖ </tex-math> from its linear measurements, using a small number <tex-math notation="LaTeX">n </tex-math> of samples. Unlike most of the literature, we make no sparsity assumption on <tex-math notation="LaTeX">β * </tex-math> , but instead adopt a different regularization: In the noiseless setting, we assume <tex-math notation="LaTeX">β * </tex-math> consists of entries, which are either rational numbers with a common denominator <tex-math notation="LaTeX">Q∈ Z⁺ </tex-math> (referred to as <tex-math notation="LaTeX">$Q-$ </tex-math> rationality); or irrational numbers taking values in a rationally independent set of bounded cardinality, known to learner; collectively called as the mixed-range assumption. Using a novel combination of the Partial Sum of Least Squares (PSLQ) integer relation detection, and the Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithms, we propose a polynomial-time algorithm which provably recovers a <tex-math notation="LaTeX">β *∈ Rᵖ </tex-math> enjoying the mixed-range assumption, from its linear measurements <tex-math notation="LaTeX">Y=Xβ *∈ Rⁿ </tex-math> for a large class of distributions for the random entries of <tex-math notation="LaTeX">X </tex-math> , even with one measurement ( <tex-math notation="LaTeX">$n=1$ </tex-math> ). In the noisy setting, we propose a polynomial-time, lattice-based algorithm, which recovers a <tex-math notation="LaTeX">β *∈ Rᵖ </tex-math> enjoying the <tex-math notation="LaTeX">$Q-$ </tex-math> rationality property, from its noisy measurements <tex-math notation="LaTeX">Y=Xβ *+W∈ Rⁿ </tex-math> , even from a single sample ( <tex-math notation="LaTeX">$n=1$ </tex-math> ). We further establish that for large <tex-math notation="LaTeX">Q </tex-math> , and normal noise, this algorithm tolerates information-theoretically optimal level of noise. We then apply these ideas to develop a polynomial-time, single-sample algorithm for the phase retrieval problem. Our methods address the single-sample ( <tex-math notation="LaTeX">$n=1$ </tex-math> ) regime, where the sparsity-based methods such as the Least Absolute Shrinkage and Selection Operator (LASSO) and the Basis Pursuit are known to fail. Furthermore, our results also reveal algorithmic connections between the high-dimensional linear regression problem, and the integer relation detection, randomized subset-sum, and shortest vector problems.