  We focus on the high-dimensional linear regression problem, where the
algorithmic goal is to efficiently infer an unknown feature vector
$\beta^*\in\mathbb{R}^p$ from its linear measurements, using a small number $n$
of samples. Unlike most of the literature, we make no sparsity assumption on
$\beta^*$, but instead adopt a different regularization: In the noiseless
setting, we assume $\beta^*$ consists of entries, which are either rational
numbers with a common denominator $Q\in\mathbb{Z}^+$ (referred to as
$Q$-rationality); or irrational numbers supported on a rationally independent
set of bounded cardinality, known to learner; collectively called as the
mixed-support assumption. Using a novel combination of the PSLQ integer
relation detection, and LLL lattice basis reduction algorithms, we propose a
polynomial-time algorithm which provably recovers a $\beta^*\in\mathbb{R}^p$
enjoying the mixed-support assumption, from its linear measurements
$Y=X\beta^*\in\mathbb{R}^n$ for a large class of distributions for the random
entries of $X$, even with one measurement $(n=1)$. In the noisy setting, we
propose a polynomial-time, lattice-based algorithm, which recovers a
$\beta^*\in\mathbb{R}^p$ enjoying $Q$-rationality, from its noisy measurements
$Y=X\beta^*+W\in\mathbb{R}^n$, even with a single sample $(n=1)$. We further
establish for large $Q$, 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 $(n=1)$ regime, where the
sparsity-based methods such as LASSO and Basis Pursuit are known to fail.
Furthermore, our results also reveal an algorithmic connection between the
high-dimensional linear regression problem, and the integer relation detection,
randomized subset-sum, and shortest vector problems.
