arXiv:1803.06716v1 [] 18 Mar 2018

High Dimensional Linear Regression
using Lattice Basis Reduction
David Gamarnik∗

Ilias Zadik†

Abstract
We consider a high dimensional linear regression problem where the goal is to efficiently
recover an unknown vector β ∗ from n noisy linear observations Y = Xβ ∗ + W ∈ Rn , for
known X ∈ Rn×p and unknown W ∈ Rn . 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 Q ∈ 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 = o (p/ log p)
and Q sufficiently large, our algorithm tolerates a nearly optimal information-theoretic level
of the noise.

1

Introduction

We consider the following high-dimensional linear regression model. Consider n samples of a
vector β ∗ ∈ Rp in a vector form Y = Xβ ∗ + W for some X ∈ Rn×p and W ∈ Rn . Given the
knowledge of Y and X the goal is to infer β ∗ using an efficient algorithm and the minimum
number n of samples possible. Throughout the paper we call p the number of features, X the
measurement matrix and W the noise vector.
We focus on the high-dimensional case where n may be much smaller than p and p grows to infinity, a setting that has been very popular in the literature during the last years [Chen et al., 2001],
[Donoho, 2006], [Candes et al., 2006], [Foucart and Rauhut, 2013], [Wainwright, 2009]. In this
case, and under no additional structural assumption, the inference task becomes impossible,
even in the noiseless case W = 0, as the underlying linear system becomes underdetermined.
Most papers address this issue by imposing a sparsity assumption on β ∗ , which refers to β ∗
having only a limited number of non-zero entries compared to its dimension [Donoho, 2006],
[Candes et al., 2006], [Foucart and Rauhut, 2013]. During the past decades, the sparsity assumption led to a fascinating line of research in statistics and compressed sensing, which established,
∗
†

MIT; e-mail: gamarnik@mit.edu. Research supported by the NSF grants CMMI-1335155.
MIT; e-mail: izadik@mit.edu

1

among other results, that several polynomial-time algorithms, such as Basis Pursuit Denoising
Scheme and LASSO, can efficiently recover a sparse β ∗ with number of samples much smaller than
the number of features [Candes et al., 2006], [Wainwright, 2009], [Foucart and Rauhut, 2013].
For example, it is established that if β ∗ is constrained to have at most k ≤ p non-zero
entries,

X has iid N(0, 1) entries, W has iid N(0, σ 2 ) entries and n is of the order k log kp , then both
of these algorithms can recover β ∗ , up to the level of the noise. Different structural assumptions than sparsity have also been considered in the literature. For example, a recent paper
[Bora et al., 2017] makes the assumption that β ∗ lies near the range of an L-Lipschitz generative
model G : Rk → Rp and it proposes an algorithm which succeeds with n = O(k log L) samples.
A downside of all of the above results is that they provide no guarantee in the case n is much
smaller than k log kp . Consider for example the case where the components of a sparse β ∗ are
binary-valued, and X, W follow the Gaussian assumptions described above. Supposing that σ
is sufficiently small, it is a straightforward argument that even when n = 1, β ∗ is recoverable
from Y = hX, β ∗ i + W by a brute-force method with probability tending to one as p goes to
infinity (whp). On the other hand, for sparse and binary-valued β ∗ , the Basis Pursuit method
in the noiseless case [Donoho and Tanner, 2006] and the Basis Pursuit Denoising Scheme in the
noisy case [Gamarnik
and Zadik, 2017b] have been proven to fail to recover a binary β ∗ with

p
n = o(k log k ) samples. Furthermore, LASSO has been proven to fail to recover a vector
with the same support of β ∗ , with n = o(k log p) samples [Wainwright, 2009]. This failure to
capture the complexity of the problem accurately enough for small
sample sizes also lead to an

algorithmic hardness conjecture for the regime n = o(k log kp ) [Gamarnik and Zadik, 2017a],
[Gamarnik and Zadik, 2017b]. While this conjecture still stands in the general case, as we show
in this paper, in the special case where β ∗ is rational-valued and the magnitude of the noise W is
sufficiently small, the statistical computational gap can be closed and β ∗ can be recovered even
when n = 1.
The structural assumption we impose on β ∗ is that its entries are rational numbers with
denominator equal to some fixed positive integer value Q ∈ Z>0 , something we refer to as
the Q-rationality assumption. Note that for any Q, this assumption is trivially satisfied by
the binary-valued β ∗ which was discussed above. The 1-rationality assumption corresponds to
β ∗ having integer entries, an assumption that arises in various places in the statistics literature, for example in the study of global navigation satellite systems (GPS) and communications
[Hassibi and Boyd, 1998], [Hassibi and Vikalo, 2002], [Brunel and Boutros, 1999], [Borno, 2011].
Some related examples are also discussed in the book [Foucart and Rauhut, 2013]. The case
Q = m! for some m ∈ Z>0 , corresponds to β ∗ having rational entries with denominator equal to
m! which in particular contains all possible rational entries with denominator between −m and
m. Hence, the m!-rationality assumption can be considered as an approximation, as m grows,
to the general case of arbitrary rational-valued ground truth vectors β ∗ .
In the Bayesian setting, where the ground truth β ∗ is sampled according to a discrete distribution [Donoho et al., 2013] proposes a low-complexity algorithm which provably recovers β ∗ with
n = o(p) samples. This algorithm uses the technique of approximate message passing (AMP)
and is motivated by ideas from statistical physics [Krzakala et al., 2012]. Even though the result
from [Donoho et al., 2013] applies to the general discrete case for β ∗ , it requires the matrix X
to be spatially coupled, a property that in particular does not hold for X with iid standard
Gaussian entries. Furthermore the required sample size for the algorithm to work is only guaranteed to be sublinear in p, a sample size potentially much bigger than the information-theoretic
2

limit for recovery under sufficiently small noise (n = 1). In the present paper, where β ∗ satisfies
the Q-rationality assumption, we propose a polynomial-time algorithm which applies for a large
class of continuous distributions for the iid entries of X, including the normal distribution, and
provably works even when n = 1.
The algorithm we propose is inspired by the algorithm introduced in [Lagarias and Odlyzko, 1985]
which solves, in polynomial time, a certain version of the so-called Subset-Sum problem. To
be more specific, consider the following NP-hard algorithmic problem.
Given p ∈ Z>0 and
P
y, x1 , x2 , . . . , xp ∈ Z>0 the goal is to find a ∅ =
6 S ⊂ [p] with y = i∈S xi when at least one
such set S is assumed to exist. Over 30 years ago, this problem received a lot of attention
in the field of cryptography, based on the belief that the problem would be hard to solve in
many “real” instances. This would imply that several already built public key cryptosystems,
called knapsack public key cryptosystems, could be considered safe from attacks [Lempel, 1979],
[Merkle and Hellman, 1978]. This belief though was proven wrong by several papers in the early
80s, see for example [Shamir, 1982]. Motivated by this line of research, Lagarias and Odlyzko
in [Lagarias and Odlyzko, 1985], and a year later Frieze in [Frieze, 1986], using a cleaner and
shorter argument, proved the same surprising fact: if x1 , x2 , . . . , xp follow an iid uniform distri1
1
2
2
bution on [2 2 (1+ǫ)p ] := {1, 2, 3, . . . , 2 2 (1+ǫ)p } for some ǫ > 0 then there exists a polynomial-in-p
time algorithm which solves the subset-sum problem whp as p → +∞. In other words, even
though the problem is NP-hard in the worst-case, assuming a quadratic-in-p number of bits for
the coordinates of x, the algorithmic complexity of the typical such problem is polynomial in
p. The successful efficient algorithm is based on an elegant application of a seminal algorithm
in the computational study of lattices called the Lenstra-Lenstra-Lovasz (LLL) algorithm, introduced in [Lenstra et al., 1982]. This algorithm receives as an input a basis {b1 , . . . , bm } ⊂ Zm
of a full-dimensional lattice L and returns in time polynomial in m and maxi=1,2,...,m log kbi k∞ a
m
non-zero vector ẑ in the lattice, such that kẑk2 ≤ 2 2 kzk2 , for all z ∈ L \ {0}.
Besides its significance in cryptography, the result of [Lagarias and Odlyzko, 1985] and [Frieze, 1986]
enjoys an interesting linear regression interpretation as well. One can show that under theP
iid uni1
(1+ǫ)p2
2
form in [2
] assumption for x1 , x2 , . . . , xp , there exists exactly one set S with y = i∈S xi
whp as p tends to infinity. Therefore if β ∗ is the indicator
vector of this unique set S, that is
P
∗
βi = 1(i ∈ S) for i = 1, 2, . . . , p, we have that y = i xi βi = hx, βi, where x := (x1 , x2 , . . . , xp ),
has a unique binary solution β = β ∗ . Furthermore using only the knowledge of y, x as input
to the Lagarias-Odlyzko algorithm we obtain a polynomial in p time algorithm which recovers
exactly β ∗ whp as p → +∞. Written in this form, and given our earlier discussion on highdimensional linear regression, this statement is equivalent to the statement that the noiseless
high-dimensional linear regression problem with binary β ∗ and X generated with iid elements
1
2
from Unif[2 2 (1+ǫ)p ] is polynomial-time solvable even with one sample (n = 1), whp as p grows to
infinity. The main focus of this paper is to extend this result to β ∗ satisfying the Q-rationality
assumption, continuous distributions on the iid entries of X and non-trivial noise levels.
It should be noted that last year the algorithm in [Lagarias and Odlyzko, 1985] has inspired a
new algorithm, which appeared in [Andoni et al., 2017], for solving a generalization of the phase
retrieval problem, called the correspondence retrieval problem. In this problem, k distinct but
unknown vectors x1 , . . . , xk ∈ Rd are to be recovered from the unordered collection of linear measurements hwi , x1 i, . . . , hwi , xk i for n known vectors w1 , . . . , wn with iid standard Gaussian entries.
The authors establish that an algorithm, using similar ideas to [Lagarias and Odlyzko, 1985], is
able to recover the order of the measurements and, therefore, the vectors (xi )i=1,...,k with n = d+1.
3

Besides being inspired by the algorithm in [Lagarias and Odlyzko, 1985], the authors only apply and do not attempt to generalize the algorithm from [Lagarias and Odlyzko, 1985]. The
generalization of the algorithm of [Lagarias and Odlyzko, 1985] to an arbitrary integer-valued
β ∗ , non-necessarily uniform integer entries for X and non-zero noise level is the main technical
contribution of the present paper and a key step towards establishing our main result.

Summary of the Results
We propose a polynomial time algorithm for high-dimensional linear regression problem and
establish a general result for its performance. We show that if the entries of X ∈ Rn×p are
iid from an arbitrary continuous distribution with bounded density and finite expected value,
β ∗ satisfies the Q-rationality assumption, kβ ∗ k∞ ≤ R for some R > 0, and W is either an
adversarial vector with infinity norm at most σ or has iid mean-zero entries with variance at
most σ 2 , then under some explicitly stated assumption on the parameters n, p, σ, R, Q our algorithm recovers exactly the vector β ∗ in time which is polynomial in n, p, log( σ1 ), log R, log Q,
whp as p tends to infinity. As a corollary, we show that for any Q and R our algorithm can
infer correctly β ∗ , when σ is at most exponential in − (p2 /2 + (2 + p) log(QR)), even from one
observation (n = 1). We show that for general n our algorithm can tolerate noise level σ which
is exponential in − ((2n + p)2 /2n + (2 + p/n) log(QR)). We complement our results with the
information-theoretic limits of our problem. We show that in the case of Gaussian white noise
W , a noise level which is exponential in −p log(QR)/n cannot be tolerated. This allows us to
conclude that in the regime n = o (p/ log p) and RQ = 2ω(p) our algorithm tolerates the optimal
information theoretic level of noise.
The algorithm we propose receives as input real-valued data Y, X but importantly it truncates
in the first step the data by keeping the first N bits after zero of every entry. In particular,
this allows the algorithm to perform only finite-precision artihmetic operations. Here N is
a parameter of our algorithm chosen by the algorithm designer. For our recovery results it is
chosen to be polynomial in p and log( σ1 ).
A crucial step towards our main result is the extension of the Lagarias-Odlyzko algorithm
[Lagarias and Odlyzko, 1985], [Frieze, 1986] to not necessarily binary, integer vectors β ∗ ∈ Zp , for
measurement matrix X ∈ Zn×p with iid entries not necessarily from the uniform distribution, and
finally, for non-zero noise vector W . As in [Lagarias and Odlyzko, 1985] and [Frieze, 1986], the
algorithm we construct depends crucially on building an appropriate lattice and applying the LLL
algorithm on it. There is though an important additional step in the algorithm presented in the
present paper compared with the algorithm in [Lagarias and Odlyzko, 1985] and [Frieze, 1986].
The latter algorithm is proven to recover a non-zero integer multiple λβ ∗ of the underlying
binary vector β ∗ . Then since β ∗ is known to be binary, the exact recovery becomes a matter
of renormalizing out the factor λ from every non-zero coordinate. On the other hand, even if
we establish in our case the corresponding result and recover a non-zero integer multiple of β ∗
whp, this last renormalizing step would be impossible as the ground truth vector is not assumed
to be binary. We address this issue as following. First we notice that the renormalization step
remains valid if the greatest common divisor of the elements of β ∗ is 1. Under this assumption
from any non-zero integer multiple of β ∗ , λβ ∗ we can obtain the vector itself by observing that
the greatest common divisor of λβ ∗ equals to λ, and computing λ by using for instance the
Euclid’s algorithm. We then generalize our recovery guarantee to arbitrary β ∗ . We do this
4

by first translating implicitly the vector β ∗ with a random integer vector Z via translating
our observations Y = Xβ ∗ + W by XZ to obtain Y + XZ = X(β ∗ + Z) + W . We then
prove that the elements of β ∗ + Z have greatest common divisor equal to unity with probability
tending to one. This last step is based on an analytic number theory argument which slightly
extends a beautiful result from probabilistic number theory (see for example, Theorem 332 in
[Hardy and Wright, 1975]) according to which
lim PP,Q∼Unif{1,2,...,m},P ⊥⊥Q [gcd (P, Q) = 1] =

m→+∞

6
,
π2

where P ⊥
⊥ Q refers to P, Q being independent random variables. This result is not of clear origin
in the literature, but possibly it is attributed to Chebyshev, as mentioned in [Erdos and Lorentz, 1985].
A key implication of this result for us is the fact that the limit above is strictly positive.

Notation
Let Z∗ denote Z \ {0}. For k ∈ Z>0 we set [k] := {1, 2, . . . , k}
vector with all entries equal to 1. For a vector x ∈ Rd we
the diagonal matrix with Diagd×d (x)ii = xi , for i ∈ [d]. For
1
P
d
p p
corresponding notation for Lp -norm be kxkp :=
i=1 |xi |

and 1k the k-dimensional column
define Diagd×d (x) ∈ Rd×d to be
1 ≤ p < ∞ and x ∈ Rd let the
and for p = ∞ the corresponding

notation for L∞ -norm be kxk∞ = maxi=1,...,d |xi |. Given two vectors x, y ∈ Rd the Euclidean inner
P
product notation is denoted by hx, yi := di=1 xi yi . By log : R>0 → R we refer the logarithm
with base 2.
lattice L ⊆ Zk generated by a set of linearly independent b1 , . . . , bk ∈ Zk is defined as
PThe
{ ki=1 zi bi |z1 , z2 , . . . , zk ∈ Z}. Throughout the paper we use the following asymptotic notation:
for two real-valued sequences an , bn , n ∈ Z>0 , we say
|an |
= 0,
n |bn |
|bn |
lim
= 0,
n |an |
|an |
< +∞,
lim sup
|bn |
n
|bn |
< +∞
lim sup
|an |
n
an = O(bn ) and an = Ω(bn ).

an = o(bn ) if lim
an = ω(bn ) if
an = O(bn ) if
an = Ω(bn ) if
an = Θ(bn ) if

Finally, we say that a sequence of events {Ap }p∈N holds with high probability (whp) as p → +∞
if
lim P (Ap ) = 1.
p→+∞

5

2

Main Results

2.1

Extended Lagarias-Odlyzko algorithm

Let n, p, R ∈ Z>0 . Given X ∈ Zn×p , β ∗ ∈ (Z ∩ [−R, R])p and W ∈ Zn , set Y = Xβ ∗ + W .
From the knowledge of Y, X the goal is to infer exactly β ∗ . For this task we propose the
following algorithm which is an extension of the algorithm in [Lagarias and Odlyzko, 1985] and
[Frieze, 1986]. For realistic purposes the values of R, kW k∞ is not assumed to be known exactly.
As a result, the following algorithm, besides Y, X, receives as an input a number R̂ ∈ Z>0 which
is an estimated upper bound in absolute value for the entries of β ∗ and a number Ŵ ∈ Z>0 which
is an estimated upper bound in absolute value for the entries of W .
Algorithm 1: Extended Lagarias-Odlyzko (ELO) Algorithm

1

2
3
4
5

6
7

Input: (Y, X, R̂, Ŵ ), Y ∈ Zn , X ∈ Zn×p , R̂, Ŵ ∈ Z>0 .
Output: βˆ∗ an estimate of β ∗
Generate a random vector Z ∈ {R̂ + 1, R̂ + 2, . . . , 2R̂ + log p}p with iid entries uniform in
{R̂ + 1, R̂ + 2, . . . , 2R̂ + log p}
Set Y1 = Y + XZ.
For each i = 1, 2, . .. , n, if (Y1 )i = 0 set (Y2 )i = 1 and otherwise set (Y2 )i = (Y1 )i .
√
p
√
Set m = 2n+⌈ 2 ⌉+3 p R̂⌈ p⌉ + Ŵ ⌈ n⌉ .

Output ẑ ∈ R2n+p from running the LLL basis reduction algorithm on the lattice
generated by the columns of the following (2n + p) × (2n + p) integer-valued matrix,


mX −mDiagn×n (Y2 ) mIn×n
0p×n
0p×n 
Am :=  Ip×p
(1)
0n×p
0n×n
In×n
Compute g = gcd (ẑn+1 , ẑn+2 , . . . , ẑn+p ) , using the Euclid’s algorithm.
If g 6= 0, return βˆ∗ = g1 (ẑn+1 , ẑn+2 , . . . , ẑn+p )t − Z. Otherwise, return βˆ∗ = 0p×1 .

We explain here informally the steps of the (ELO) algorithm and briefly sketch the motivation
behind each one of them. In the first and second steps the algorithm translates Y by XZ where
Z is a random vector with iid elements chosen uniformly from {R̂ + 1, R̂ + 2, . . . , 2R̂ + log p}. In
that way β ∗ is translated implicitly to β = β ∗ + Z because Y1 = Y + XZ = X(β ∗ + Z) + W . As
we will establish using a number theoretic argument, gcd (β) = 1 whp as p → +∞ with respect
to the randomness of Z, even though this is not necessarily the case for the original β ∗ . This
is an essential requirement for our technique to exactly recover β ∗ and steps six and seven to
be meaningful. In the third step the algorithm gets rid of the zero observations. The minor
modification of the noise level affects the observations in a negligible way.
The fourth and fifth steps of the algorithm provide a basis for a specific lattice in 2n + p
dimensions. The lattice is built with the knowledge of the input and Y2 , the modified Y . The
algorithm in step five calls the LLL basis reduction algorithm to run for the columns of Am
as initial basis for the lattice. The fact that Y has been modified to be non-zero on every
coordinate is essential here so that Am is full-rank and the LLL basis reduction algorithm,
6

defined in [Lenstra et al., 1982], can be applied,. This application of the LLL basis reduction
algorithm is similar to the one used in [Frieze, 1986] with one important modification. In order
to deal here with multiple equations and non-zero noise, we use 2n+ p dimensions instead of 1 + p
in [Frieze, 1986]. Following though a similar strategy as in [Frieze, 1986], it can be established
that the n + 1 to n + p coordinates of the output of the algorithm, ẑ ∈ Z2n+p , correspond to a
vector which is a non-zero integer multiple of β, say λβ for λ ∈ Z∗ , w.h.p. as p → +∞.
This is an important part in the analysis and it is heavily based on the fact that the matrix
Am , which generates the lattice, has its first n rows multiplied by the “large enough” and appropriately chosen integer m which is defined in step four. It can be shown that this property
of Am implies that any vector z in the lattice with “small enough” L2 norm necessarily satisfies
(zn+1 , zn+2 , . . . , zn+p ) = λβ for some λ ∈ Z∗ whp as p → +∞. In particular, using that ẑ is guar2n+p
anteed to satisfy kẑk2 ≤ 2 2 kzk2 for all non-zero z in the lattice, it can be derived that ẑ has
a “small enough” L2 norm and therefore indeed satisfies the desired property whp as p → +∞.
Assuming now the validity of the gcd (β) = 1 property, step six finds in polynomial time this
unknown integer λ that corresponds to ẑ, because gcd (ẑn+1 , ẑn+2 , . . . , ẑn+p ) = gcd (λβ) = λ.
Finally step seven scales out λ from every coordinate and then subtracts the known random
vector Z, to output exactly β ∗ .
Of course the above is based on an informal reasoning. Formally we establish the following
result.
Theorem 2.1. Suppose
(1) X ∈ Zn×p is a matrix with iid entries generated according to a distribution D on Z which
for some N ∈ Z>0 and constants C, c > 0, assigns at most 2cN probability on each element
d

of Z and satisfies E[|V |] < C2N , for V = D;

(2) β ∗ ∈ (Z ∩ [−R, R])p , W ∈ Zn ;
(3) Y = Xβ ∗ + W .
N

Suppose furthermore that R̂ ≥ R, kW k∞ = o( 2n ) and




1
(2n + p) 2n + log n + p + 4 log p + 2 max{log R̂, log (kW k∞ + 1)} + 4n log (cnp) − Nn = −∞.
lim
p→+∞ 2
(2)
For any Ŵ ≥ kW k∞ the algorithm ELO with input (Y, X, R̂, Ŵ ) outputs exactly β ∗ whp as
p → +∞ and terminates in time at most polynomial in n, p, N, log R̂ and log Ŵ .
The proof of Theorem 2.1 is in Section 3.
Remark 2.2. In the statement of Theorem 2.1 the only parameters that are assumed to grow
to infinity are p and whichever other parameters among n, R, kW k∞ , N are implied to grow to
infinity because of (2). Note in particular that n can remain bounded, including the case n = 1,
if N grows fast enough.
Remark 2.3. It can be easily checked that the assumptions of Theorem 2.1 are satisfied for
p2
2
n = 1, N = (1 + ǫ) p2 , R = 1, D = Unif{1, 2, . . . , 2(1+ǫ) 2 } and W = 0. Under these assumptions,
the Theorem’s implication is a generalization of the result from [Lagarias and Odlyzko, 1985] and
[Frieze, 1986] to the case β ∗ ∈ {−1, 0, 1}p .
7

2.2

Applications to High-Dimensional Linear Regression

The Model
We first define the Q-rationality assumption.
Definition 2.4. Let p, Q ∈ Z>0 . We say that a vector β ∈ Rp satisfies the Q-rationality
assumption if for all i ∈ [p], βi∗ = KQi , for some Ki ∈ Z.
The high-dimensional linear regression model we consider is as follows.
Assumptions 1. Let n, p, Q ∈ Z>0 and R, σ > 0. Suppose
(1) measurement matrix X ∈ Rn×p with iid entries generated according to a continuous distrid
bution C which has a bounded density and satisfies E[|V |] < +∞, where V = C;
(2) ground truth vector β ∗ satisfies β ∗ ∈ [−R, R]p and the Q-rationality assumption;
(3) Y = Xβ ∗ + W for some noise vector W ∈ Rn . It is assumed that either kW k∞ ≤ σ or W
has iid entries with mean zero and variance at most σ 2 , depending on the context.
Objective: Based on the knowledge of Y and X the goal is to recover β ∗ using an efficient
algorithm and using the smallest number n of samples possible. The recovery should occur with
high probability (w.h.p), as p diverges to infinity.

The Lattice-Based Regression (LBR) Algorithm
As mentioned in the Introduction, we propose an algorithm to solve the regression problem, which
we call the Lattice-Based Regression (LBR) algorithm. The exact knowledge of Q, R, kW k∞ is
not assumed. Instead the algorithm receives as an input, additional to Y and X, Q̂ ∈ Z>0 which
is an estimated multiple of Q, R̂ ∈ Z>0 which is an estimated upper bound in absolute value for
the entries of β ∗ and Ŵ ∈ R>0 which is an estimated upper bound in absolute value for the entries
of the noise vector W or their standard deviation. Furthermore an integer number N ∈ Z>0 is
given to the algorithm as an input, which, as we will explain, corresponds to a truncation in the
N
data in the first step of the algorithm. Given x ∈ R and N ∈ Z>0 let xN = sign(x) ⌊2 2N|x|⌋ , which
corresponds to the operation of keeping the first N bits after zero of a real number x.
Algorithm 2: Lattice Based Regression (LBR) Algorithm

1
2

3

Input: (Y, X, N, Q̂, R̂, Ŵ ), Y ∈ Zn , X ∈ Zn×p and N, Q̂, R̂, Ŵ ∈ Z>0 .
Output: βˆ∗ an estimate of β ∗
Set YN = ((Yi )N )i∈[n] and XN = ((Xij )N )i∈[n],j∈[p].
Set (βˆ1 )∗ to be the output of the ELO algorithm with input:

return βˆ∗ =

1 ˆ ∗
(β1 ) .
Q̂




N
N
N
2 Q̂YN , 2 XN , Q̂R̂, 2Q̂ 2 Ŵ + R̂p .

We now explain informally the steps of the algorithm. In the first step, the algorithm truncates
each entry of Y and X by keeping only its first N bits after zero, for some N ∈ Z>0 . This in
8

particular allows to perform finite-precision operations and to call the ELO algorithm in the next
step which is designed for integer input. In the second step, the algorithm naturally scales up
the truncated data to integer values, that is it scales YN by 2N Q̂ and XN by 2N . The reason
for the additional multiplication of the observation vector Y by Q̂ is necessary to make sure the
ground truth vector β ∗ can be treated as integer-valued. To see this notice that Y = Xβ ∗ + W
and YN , XN being “close” to Y, X imply
2N Q̂YN = 2N XN (Q̂β ∗ ) + “extra noise terms” + 2N Q̂W.
Therefore, assuming the control of the magnitude of the extra noise terms, by using the Qrationality assumption and that Q̂ is estimated to be a multiple of Q, the new ground truth
vector becomes Q̂β ∗ which is integer-valued. The final step of the algorithm consist of rescaling
now the output of Step 2, to an output which is estimated to be the original β ∗ . In the next
subsection, we turn this discussion into a provable recovery guarantee.

Recovery Guarantees for the LBR algorithm
We state now our main result, explicitly stating the assumptions on the parameters, under which
the LBR algorithm recovers exactly β ∗ from bounded but adversarial noise W .
Theorem 2.5.A. Under Assumption 1 and assuming W ∈ [−σ, σ]n for
 some σ ≥ 0, the following
holds. Suppose Q̂ is a multiple of Q, R̂ ≥ R, σ = o( n1Q̂ ), N ≥ 2 log npQ̂R and






1
N
(2n + p) 2n + p + 2 log Q̂ + 2 log 2 σ + R̂p + 10 log(np) − nN = −∞.
(3)
lim
p→+∞ 2
For any Ŵ ≥ σ, the LBR algorithm with input (Y, X, N, Q̂, R̂, Ŵ ) terminates with βˆ∗ = β ∗ whp
as p tends to infinity and in time polynomial in n, p, N, log R̂, log Ŵ and log Q̂.
The proof of Theorem 2.5.A is in Section 4.
Now suppose that instead of an adversarially chosen bounded deterministic noise vector W ,
we assume that W has iid entries, independent also from X, which follow a distribution with mean
zero and variance at most σ 2 . Then by using a standard union bound and Markov inequality we
have
n
X
1
E [W12 ]
√
√
P (kW k∞ ≤ npσ) ≥ 1 −
=
1
−
.
P (|Wi | > npσ) ≥ 1 − n
2
npσ
p
i=1
√
Therefore, conditional on the high probability event kW k∞ ≤ npσ, we can apply Theorem
√
2.5.A with npσ instead of σ. This establishes the following result handling random noise W .
Theorem 2.5.B. Under Assumption 1 and assuming W ∈ Rn is a vector with iid entries generating according to an, independent from X, distribution W on R with mean zero and variance
at most σ 2 for some σ ≥ 0 the following holds. Suppose that Q̂ is a multiple of Q, R̂ ≥ R,
σ = o( 3 1 1 ), N ≥ 2 log npQ̂R and
n 2 p 2 Q̂





 √
1
N
lim
npσ + R̂p + 10 log(np) − nN = −∞. (4)
(2n + p) 2n + p + 2 log Q̂ + 2 log 2
p→+∞ 2
√
For any Ŵ ≥ npσ the LBR algorithm with input (Y, X, N, Q̂, R̂, Ŵ ) terminates with βˆ∗ = β ∗
whp as p tends to infinity and in time polynomial in n, p, N, log R̂, log Ŵ and log Q̂.
9

Noise tolerance of the LBR algorithm
The limit assumptions (2) and (4) might make it hard to build an intuition for the regime that
the LBR algorithm provably works. For this reason, in this subsection we state a Proposition
explicitly mentioning the level of noise that the LBR algorithm can tolerate with n samples.
First note that in the above statements of Theorem 2.5.A and Theorem 2.5.B the only parameters that are assumed to grow are p and whichever other parameter is implied to grow because
of (2) and (4). Therefore, importantly, n does not necessarily grow to infinity, if for example
N, σ1 grow appropriately with p. That means that Theorem 2.5.A and Theorem 2.5.B imply
non-trivial guarantees for arbitrary
sample size n. The
h
i proposition below shows that if σ is at
(2n+p)2
2n+p
most exponential in −(1 + ǫ)
+ ( n ) log (RQ) for some ǫ > 0, then for appropriately
2n
chosen truncation level N the LBR algorithm recovers exactly the vector β ∗ with n samples. In
particular, with one sample (n = 1) LBR algorithm tolerates noise level up to exponential in
−(1 + ǫ) [p2 /2 + p log(QR)] for some ǫ > 0. On the other hand, if n = Θ(p) and log (RQ) = o(p),
the LBR algorithm tolerates noise level up to exponential in −O(p).
Proposition 2.6. Under Assumption 1 and assuming W ∈ Rn is a vector with iid entries
generating according to an, independent from X, distribution W on R with mean zero and
2
variance
some σ ≥ 0, the following holds. Suppose for some ǫ > 0, σ ≤
 at most σ for 
−(1+ǫ)

(2n+p)2

+( 2n+p ) log(RQ)

2n
n
2
and N satisfying

. Then the LBR algorithm with input Y, X,Q̂ = Q, R̂ = R, Ŵ∞ = 1

 


1
(2n + p)2
2n + p
log
≥ N ≥ (1 + ǫ)
+(
) log (RQ) ,
σ
2n
n

(5)

terminates with βˆ∗ = β ∗ whp as p tends to infinity and in time polynomial in n, p, N, log R̂, log Ŵ
and log Q̂.
The proof of Proposition 2.6 is in Section 5.
It is worth noticing that in the noisy case (σ > 0) the above Proposition requires the truncation level N to be upper bounded by log( σ1 ), which implies the potential counter-intuitive
conclusion that revealing more bits of the data after some point “hurts” the performance of the
recovery mechanism. Note that this is actually justified as handling arbitrary noise of absolute
value at most
 of the order σ implies that the only bits that remain unaffected by the noise are the
1
first log σ bits of every sample. In particular, any bit in a later position could have potentially
been altered by the noise.

Information Theoretic Bounds
In this subsection, we discuss the maximum level of noise that can be tolerated informationtheoretically in recovering a vector β ∗ ∈ [−R, R]p satisfying the Q-rationality assumption. Using
a standard Gaussian Communication Channel result we establish the result that under a Gaussian white noise, any successful recovery mechanism can tolerate a noise level which is at most
exponentially small in − [p log (QR) /n].
Proposition 2.7. Suppose
10

• X ∈ Rn×p is a vector with iid entries following a continuous distribution C with E[|V |] <
d
+∞, where V = C.
• β ∗ ∈ [−R, R]p satisfies the Q-rationality assumption
• W ∈ Rn has iid N(0, σ 2 ) entries and
• Y = Xβ ∗ + W
− 21
 2p log(2QR+1)
n
. Then there is no mechanism which,
−1
Suppose furthermore that σ > R(np)3 2
whp as p → +∞, recovers exactly β ∗ with knowledge of Y, X, Q, R, σ. That is, for any function
βˆ∗ = βˆ∗ (Y, X, Q, R, σ) there exist a β ∗ ∈ [−R, R]p which satisfies the Q-rationality assumption
for which


lim sup P βˆ∗ = β ∗ < 1.
p→+∞

The proof of Proposition 2.7 is in Section 5.

Sharp Optimality of the LBR Algorithm
Now we compare the performance of the LBR algorithm, as stated in Proposition 2.6, with the
information theoretic result of Proposition 2.7 to reveal an optimality regime for the algorithm
with respect to the noise it can tolerate. We focus on the high-dimensional case n = o( logp p )
ω(p)
and RQ
. Then based
 on Proposition 2.6 the amount of noise that can be tolerated is
 = 2
−(1+ǫ)

p2
p
+2n+2p+(2+ n
) log(RQ)
2n

, for an arbitrary ǫ > 0. Since n = o( logp p ) and RQ = 2ω(p) this
p
simplifies asymptotically to 2−(1+ǫ)[ n log(RQ)] , for an arbitrary ǫ > 0. Comparing this with the
result of Proposition 2.7 the following sharp result is established.
2

n
Proposition 2.8. Under Assumptions
σ 2 ) entries the
 1where W ∈ R is a vector with iid N(0,
p log(RQ)
and ǫ > 0:
following holds. Suppose that n = o logp p and RQ = 2ω(p) . Then for σ0 := 2− n

• if σ > σ01−ǫ ,then the w.h.p. exact recovery of β ∗ from the knowledge of Y, X, Q, R, σ is
impossible information theoretically.
• if σ < σ01+ǫ , then the w.h.p. exact recovery of β ∗ from the knowledge of Y, X, Q, R, σ is
possible in polynomial time by the LBR algorithm.
The proof of Proposition 2.8 is in Section 5.

3

Proof of Theorem 2.1
N

1
Proof. Since kW k∞ = o( 2n ) we can choose δ = δp such that kW k∞ ≤ 13 δ2N and ω( np
)≤δ≤
1
o( n ).

Lemma 3.1. For all i ∈ [n], |(Y2)i | ≥ 12 δ2N , whp as p → +∞.
11

Proof. First observe Y1 := Y + XZ = X(β ∗ + Z) + W and therefore from the definition of Y2 ,
Y2 = X (β ∗ + Z) + W1 for some W1 ∈ Zn with kW1 k∞ ≤ kW k∞ + 1. Letting β = β ∗ + Z we
obtain that for all i ∈ [n], (Y2 )i = hX (i) , βi + (W1)i , where X (i) is the i-th row of X, and therefore
(Y2 )i ≥ |

p
X
j=1

Xij βj | − kW1 k∞ ≥ |

p
X
j=1

Xij βj | − kW k∞ − 1.

Furthermore R̂ ≥ R implies β ∈ [1, 3R̂ + log p]p . P
We claim that conditional on β ∈ [1, 3R̂ + p]p , | pj=1 Xij βj | ≥ δ2N for all i = 1, . . . , n, w.h.p.
as p → +∞, with respect to the randomness of X. Note that this last inequality alongside with
our hypothesis that for p large enough kW k∞ ≤ 31 δ2N implies for all i, |(Y2 )i | ≥ 32 δ2N − 1 w.h.p.
1
as p → +∞. From (2) for large enough p we have, nN > n log(np), or N > log(np) or np
> 2−N .
1
) we obtain δ = ω(2−N ). Thus for large p, 23 δ2N − 1 > 12 δ2N and therefore for
Hence as δ = ω( np
all i, |(Y2 )i | ≥ 21 δ2N w.h.p. as p → +∞. It suffices then to prove the claim to establish Lemma
3.1.
In order to prove the claim, observe that for large enough p,
!
!
p
p
n
n
X
X
X
[
Xij βj | < δ2N
Xij βj | < δ2N } ≤
P |
P
{|
i=1

j=1

=

i=1

j=1

n
X

X

P

i=1 k∈Z∩[−δ2N ,δ2N ]

≤ n(2δ2N + 1)

c
2N

p
X
j=1

Xij βj = k

!

≤ 3cnδ → 0,

P
where we have used that given β1 6= 0 for i ∈ [p] and k ∈ Z the event { pj=1 Xij βj = k}
implies that the random variable Xi1 takes a specific value, conditional on the realization of the
remaining elements Xi2 , . . . , Xip involved in the equations. Therefore by our assumption on the
iid distribution generating the entries of X, each of these events has probability at most c/2N .
Note that the choice of β1 , as opposed to choosing some βi with i > 1, was arbitrary in this
argument. The last inequality uses that δ = ω(2−N ) and the final convergence step is justified
from our assumption δ = o( n1 ).
Next we use a number-theoretic lemma, which is an extension of a standard result in analytic
number theory according to which
6
lim PP,Q∼Unif{1,2,...,m},P ⊥⊥Q [gcd (P, Q) = 1] = 2 ,
m→+∞
π
where P ⊥
⊥ Q refers to P, Q being independent random variables.
Lemma 3.2. Suppose q1 , q2 , q ∈ Z>0 with q → +∞ and max{q1 , q2 } = o(q 2 ). Then


6
2
2
+ oq (1) .
|{(a, b) ∈ Z ∩ ([q1 , q1 + q] × [q2 , q2 + q]) : gcd(a, b) = 1}| = q
π2

In other words, if we choose independently one uniform integer in [q1 , q1 +q] and another uniform
integer in [q2 , q2 + q] the probability that these integers are relatively prime approaches π62 , as
q → +∞.
12

Proof. We call an integer n ∈ Z>0 square-free if it is not divisible by the square of a positive
integer number other than 1. The Mobius function µ : Z>0 → {−1, 0, 1} is defined to be


 1, n is square-free with an even number of prime factors
µ(n) = −1, n is square-free with an odd number of prime factors


0,
otherwise

From now on we ease the notation by always referring for this proof to positive integer variables. A standard property for the Mobius function (see Theorem 263 in [Hardy and Wright, 1975])
states that for all n ∈ Z>0 ,
(
X
1, n = 1
µ(d) =
0, otherwise
1≤d≤n,d|n
Therefore using the above identity and switching the order of summation we obtain
|(a, b) ∈ [q1 , q1 + q] × [q2 , q2 + q], gcd(a, b) = 1|


X
X

=
µ(d)
(a,b)∈[q1 ,q1 +q]×[q2 ,q2 +q]

=

X

1≤d≤max{q1 ,q2 }+q

1≤d≤gcd(a,b),d|gcd(a,b)



X



(a,b)∈[q1 ,q1 +q]×[q2 ,q2 +q],d|gcd(a,b)



µ(d) .

Now introducing the change of variables a = kd, b = ld for some k, l ∈ Z>0 and observing that
the number of integer numbers in an interval of length x > 0 are x + O(1), we obtain


X
X


µ(d)

q +q q
q +q
q1
≤k≤ 1d , d2 ≤l≤ 2d
d

1≤d≤max{q1 ,q2 }+q




2
q
+ O(1) µ(d)
=
d
1≤d≤max{q1 ,q2 }+q
 

q 
X
q 2
=
µ(d) + O(1)µ(d)
µ(d) + O
d
d
X

1≤d≤max{q1 ,q2 }+q

Now using |µ(d)| ≤ 1 for all d ∈ Z>0 , for n ∈ Z>0 ,
n
X
1
d=1

d

= O(log n)

and that by Theorem 287 in [Hardy and Wright, 1975] for n ∈ Z>0 ,
n
X
µ(d)
d=1

d2

=

1
6
+ on (1) = 2 + on (1)
ζ(2)
π
13

we conclude that the last quantity equals


1
max{q1 , q2 } + q
6
2
+ O(log(max{q1 , q2 } + q)) +
+ oq (1) .
q
π2 q
q2
Recalling the assumption q1 , q2 = o(q 2 ) the proof is complete.
Claim 3.3. The greatest common divisor of the coordinates of β := β ∗ + Z equals to 1, w.h.p.
with respect to the randomness of Z as p → +∞.
Proof. Each coordinate of β is a uniform and independent choice of a positive integer from an
interval of length 2R̂ + log p with starting point in [R̂ − R + 1, R̂ + R + 1], depending on the value
of βi∗ ∈ [−R, R]. Note though that Lemma 3.2 applies for arbitrary q1 , q2 ∈ [R̂ − R + 1, R̂ + R + 1]
and q = 2R̂ + log p since q1 , q2 = o(q 2 ) and q → +∞. from this we conclude that the probability
any two specific coordinates of β have greatest common divisor 1 approaches π62 , as p → +∞.
But the probability the greatest common divisor of all the coordinates is not one implies that
the greatest common divisor of the 2i − 1 and 2i coordinate is not one, for every i = 1, 2, . . . ⌊ 2p ⌋.
Hence using the independence among the values of the coordinates, we conclude that the greatest
common divisor of the coordinates of β is not one with probability at most
⌊ p2 ⌋

6
→ 0, as p → ∞.
1 − 2 + op (1)
π
Given a vector z ∈ R2n+p , define zn+1:p := (zn+1 , . . . , zn+p )t .

Claim 3.4. The outcome of Step 5 of the algorithm, ẑ, satisfies
• kẑk2 < m
• ẑn+1:n+p = qβ, for some q ∈ Z∗ , w.h.p as p → +∞.
Proof. Call Lm the lattice generated by the columns of the (2n + p) × (2n + p) integer-valued
matrix Am defined in the algorithm; that is Lm := {Am z|z ∈ Z2n+p }. Notice that as Y2 is nonzero
at every coordinate, the lattice Lm is full-dimensional and the columns of Am define a basis for
Lm . Finally, an important vector in Lm is z0 ∈ Lm which is

 

β
0n×1
z0 := Am  1n  =  β  ∈ Lm .
(6)
W1
W1
Consider the shortest vector problem on Lm

(S2 ) min
kzk2
s.t. z ∈ Lm ,
If z ∗ is an optimal solution of (S2 ) we obtain
q
√
√
∗
kz k2 ≤ kz0 k2 = kβk22 + kW1 k22 ≤ kβk∞ p + kW1 k∞ n.
14

and therefore given our assumptions on β, W

√
√
p + (kW k∞ + 1) n.
kz ∗ k2 ≤ 3R̂ + log p
Using that R̂ ≥ 1 this implies

 √
√ 
kz ∗ k2 ≤ 4p R̂ p + (kW k∞ + 1) n .

The LLL guarantee and the observation above imply that
 √
√ 
2n+p
2n+p
kẑk2 ≤ 2 2 kz ∗ k2 ≤ 2 2 +2 p R̂ p + (kW k∞ + 1) n := m0 .

(7)

 √
√ 
Recall Ŵ ≥ max{kW k∞ , 1}. Since m ≥ 2
p R̂ p + Ŵ∞ n , we obtain m > m0 and
hence kẑk2 < m. This establishes the first part of the Claim.
For the second part, given (7) and that ẑ is non-zero it suffices to establish that under the
conditions of our Theorem there is no non-zero vector in Lm \ {z ∈ Lm |zn+1:n+p = qβ, q ∈ Z∗ }
with L2 norm less than m0 , w.h.p. as p → +∞. By definition for any z ∈ Lm there exists
x ∈ Z2n+p such that z = Am x. We write x = (x1 , x2 , x3 )t where x1 ∈ Zp , x2 , x3 ∈ Zn . Then
 

m Xx1 − Diagn×n (Y )x2 + x3
.
z=
x1
x3
n+ p2 +3

Note that x1 = zn+1:n+p .
We first establish that for any z ∈ Lm the condition kzk2 ≤ m0 implies necessarily
Xx1 − Diagn×n (Y )x2 + x3 = 0.

(8)

and in particular z = (0, x1 , x3 ). If not, as it is an integer-valued vector, kXx1 − Diagn×n (Y )x2 +
x3 ||2 ≥ 1 and therefore
m ≤ mkXx1 − Diagn×n (Y )x2 + x3 k2 ≤ kzk2 ≤ m0 ,
a contradiction as m > m0 . Hence, (8) holds and z = (0, x1 , x3 ).
Now we claim that it suffices to show that there is no non-zero vector in Lm \{z ∈ Lm |zn+1:n+p =
qβ, q ∈ Z} with L2 norm less than m0 , w.h.p. as p → +∞. Note that in this claim the coefficient
q is allowed to take the zero value as well. The reason it suffices to prove this weaker statement
is that any non-zero z ∈ Lm with kzk2 ≤ m0 necessarily satisies that zn+1:n+p 6= 0 w.h.p. as
p → +∞ and therefore the case q = 0 is not possible whp as p → +∞. To see this, we use the
decomposition and recall that x1 = zn+1:n+p . Therefore it suffices to establish that there is no
triplet x = (0, x2 , x3 )t ∈ Z2n+p with x2 , x3 ∈ Zn for which the vector z = Am x ∈ Lm is non-zero
and kzk2 ≤ m0 , w.h.p. as p → +∞. To prove this, we consider by contradiction such a triplet
x = (0, x2 , x3 ). From (8) it necessarily holds Diagn×n (Y )x2 = x3 , or equivalently
for all i ∈ [n], Yi (x2 )i = (x3 )i .
15

(9)

From Lemma 3.1 and (9) we obtain that
1
for all i ∈ [n], δ2N |(x2 )i | ≤ |(x3 )i |
2

(10)

whp as p → +∞. Since z is assumed to be non-zero and z = Am x = (0, 0, x3 ) there exists i ∈ [n]
with (x3 )i 6= 0. Using (9) we obtain (x2 )i 6= 0 as well. Therefore for this value of i it must be
simultaneously true that |(x2 )i | ≥ 1 and |(x3 )i | ≤ m0 . Plugging these inequalities to (10) for this
value of i, we conclude
1 N
δ2 ≤ m0
2
1 N
2
for sufficiently large p. Therefore for sufficiently large p, np
2 ≤ m0 , or
Recall that δ ≥ np
N ≤ log(np) + log m0 .
Plugging in the value of m0 we conclude that for sufficiently large p,
 √
√ 
2n + p
N ≤ log(np) +
+ log p + log R̂ p + (kW k∞ + 1) n + log 4.
2

This can be checked to contradict our hypothesis (2) and the proof of the claim is complete.
Therefore it suffices to establish that whp as p → +∞ there is no triplet (x1 , x2 , x3 ) with
(a) x1 ∈ Zp , x2 , x3 ∈ Zn ;
(b) kx1 k22 + kx3 k22 ≤ m0 ;
(c) Xx1 − Diagn×n (Y )x2 + x3 = 0;
(d) ∀q ∈ Z : x1 6= qβ ∗ .
We first claim that any such triplet (x1 , x2 , x3 ) satifies w.h.p.
kx2 k∞ = O(

m0 n2 p3
).
δ

To see this fix i = 1, 2, . . . , n and denote by X (i) the i-th row of X. By (c),
0 = (Xx1 − Diagn×n (Y )x2 + x3 )i = hX (i) , x1 i − Yi (x2 )i + (x3 )i ,
and therefore by triangle inequality
|Yi (x2 )i | = |hX (i) , x1 i − (x3 )i | ≤ |hX (i) , x1 i| + |(x3 )i |.

(11)

But observe that for all i ∈ [n], kX (i) k∞ ≤ kXk∞ ≤ (np)2 2N w.h.p. as p → +∞. Indeed using a
union bound, Markov’s inequality and our assumption on the distribution D of the entries of X,


P kXk∞ > (np)2 2N ≤ npP |X11 | > (np)2 2N ≤
16

1
C
E[|X
|]
≤
,
11
2N np
np

which establishes the claim. Using this, Lemma 3.1 and (11) we conclude that for all i ∈ [n] whp
as p → +∞
1
|(x2 )i | δ2N ≤ (2N p(np)2 + 1)m0
2
which in particular implies
m0 n2 p3
),
|(x2 )i | ≤ O(
δ
whp as p → +∞.
Now we claim that for any fixed triplet (x1 , x2 , x3 ) it also holds

cn
P Xx1 − Diagn×n (Y )x2 + x3 = 0 ≤ nN .
2

(12)

To see this note that for any i ∈ [n], Yi = hX (i) , βi + Wi where X (i) is the i-th row of X. In
particular, Xx1 − Diagn×n (Y )x2 + x3 = 0 implies for all i ∈ [n],
hX (i) , x1 i − Yi (x2 )i = (x3 )i


or hX (i) , x1 i − hX (i) , βi + Wi (x2 )i = (x3 )i
or hX (i) , x1 − (x2 )i βi = (x3 )i − (x2 )i Wi

Hence using independence between rows of X,
n
 Y

P Xx1 − Diagn×n (Y )x2 − x3 = 0 =
P hX (i) , x1 − (x2 )i βi = (x3 )i − (x2 )i Wi

(13)

i=1

But because of (d) for all i, x1 − (x2 )i β 6= 0. In particular, hX (i) , x1 − (x2 )i βi = (x3 )i − (x2 )i Wi
constraints at least one of the entries of X (i) to get a specific value with respect to the rest of
the elements of the row which has probability at most 2cN by the independence assumption on
the entries of X. This observation with (13) implies (12).
Now, we establish that indeed there are no such triplets, w.h.p. as p → +∞. Recall the
standard fact that for any r > 0 there are at most O((2r + 1)n ) vectors in Zn with L∞ -norm
at most r. Using this, (12) and a union bound over all the integer vectors (x1 , x2 , x3 ) with
2 3
kx1 k22 + kx3 k22 ≤ m0 , kx2 k∞ = O( m0 nδ p ) we conclude that the probability that there exist a
triplet (x1 , x2 , x3 ) satisfying (a), (b), (c), (d) is at most of the order


m0 n2 p3 n n+p cn
,
) m0
(C0
δ
2nN
for some C0 > 0. Plugging in the value of m0 we conclude that the probability is at most of the
order
h √
C0
√ i2n+p
1
2
2 3
2 2 (2n+p) +n log(cn p )+n log( δ )+(2+log p)(2n+p) R̂ p + (kW k∞ + 1) n
.
2nN

17

1
) we obtain log( Cδ0 ) ≤ log(np) for large p, and therefore the last
Now recalling that δ = ω( np
bound becomes at most of the order
h √
√ i2n+p
1
2
2 2 (2n+p) +4n log(cnp)+(2+log p)(2n+p) R̂ p + (kW k∞ + 1) n
.
2nN

We claim that the last quantity converges to zero because of our assumption (2). Indeed the
logarithm of the above quantity equals

 √
√ 
1
(2n + p) 2n + p + 4 + 2 log p + 2 log R̂ p + (kW k∞ + 1) n + 4n log(cnp) − nN.
2
Finally using the crude bound that for a, b > 0 with a ≥ 2, log(a + b) ≤ log(2 max{a, b}) and
√
that R̂ p ≥ 2 and log p ≥ 4 + log 2, for large enough p, we obtain that the last quantity for large
enough p is upper bounded by


1
(2n + p) 2n + log n + p + 4 log p + 2 max{log R̂, log (kW k∞ + 1)} + 4n log(cnp) − nN
2

which by our assumption (2) converges to −∞. This completes the proof of claim 3.4.

Now we prove Theorem 2.1. First with respect to time complexity, it suffices to analyze Step
5 and Step 6. For step 5 we have from [Lenstra et al., 1982] that it runs in time polynomial in
n, p, log kAm k∞ which indeed is polynomial in n, p, N and log R̂, log Ŵ . For step 6, recall that the
Euclid algorithm to compute the greatest common divisor of p numbers with norm bounded by
kẑk∞ takes time which is polynomial in p, log kẑk∞ . But from Claim 3.4 we have that kẑk∞ < m
and therefore the time complexity is polynomial in p, log m and therefore again polynomial in
n, p, N and log R̂, log Ŵ .
Finally we prove that the ELO algorithm outputs exactly β ∗ w.h.p. We obtain from Claim
3.4 that ẑn+1:n+p = qβ for β = β ∗ + Z and some q ∈ Z∗ w.h.p. We claim that the g computed in
Step 6 is this non-zero integer q w.h.p. To see it notice that from Claim 3.3 gcd(β) = 1 w.h.p.
and therefore the g computed in Step 6 satisfies w.h.p.
g = gcd(ẑn+1:n+p ) = gcd(qβ) = qgcd(β) = q.
Hence we obtain w.h.p.
ẑn+1:n+p = gβ = g (β ∗ + Z)
or whp as p → +∞

1
β ∗ = ẑn+1:n+p − Z,
g
which implies based on Step 7 and the fact that g = q 6= 0 that indeed the output of the algorithm
is β ∗ w.h.p. The proof of Theorem 2.1 is complete.

4

Proof of Theorem 2.5.A

Proof. We first analyze the algorithm with respect to time complexity. It suffices to analyze step 2 as step 1 runs clearly in polynomial time N, n, p. Step 2 runs the ELO algorithm. From Theorem 2.1 we obtain that the ELO algorithm terminates in polynomial time in
18



 

n, p, N, log Q̂R̂ , log 2Q̂ 2N Ŵ + R̂p . As the last quantity is indeed polynomial in n, p, N, log R̂, log Q̂, log
we are done.
Now we prove that βˆ∗ = β ∗ , w.h.p. as p → +∞. Notice that it suffices to show that the
∗
= β ∗ whp
output of Step 3 of the LBR algorithm is exactly Q̂β ∗ , as then step 4 gives βˆ∗ = Q̂β
Q̂
as p → +∞.
We first establish that
2N Q̂YN = 2N XN Q̂β ∗ + W0
(14)

for some W0 ∈ Zn with kW0 k∞ + 1 ≤ 2Q̂ 2N σ + Rp . We have Y = Xβ ∗ + W , with kW k∞ ≤ σ.
From the way YN is defined, kY − YN k∞ ≤ 2−N . Hence for W ′ = W + YN − Y which satisfies
kW ′ k∞ ≤ 2−N + σ we obtain
YN = Xβ ∗ + W ′ .
Similarly since kX − XN k∞ ≤ 2−N and kβ ∗ k∞ ≤ R we obtain k (X − XN ) β ∗ k∞ ≤ 2−N Rp, and
therefore for W ′′ = W ′ + (X − XN ) β ∗ which satisfies kW ′′ k∞ ≤ 2−N + σ + 2−N Rp we obtain,
YN = XN β ∗ + W ′′
or equivalently
2N YN = 2N XN β ∗ + W ′′′ ,
where W ′′′ := 2N W ′′ which satisfies kW ′′′ k∞ ≤ 1 + 2N σ + Rp. Multiplying with Q̂ we obtain


2N Q̂YN = 2N XN Q̂β ∗ + W0 ,
where W0 := Q̂W ′′′ which satisfies



kW0 k∞ ≤ Q̂ 1 + 2N σ + Rp ≤ 2Q̂ 2N σ + Rp − 1.

This establishes (14).
We now apply Theorem 2.1
for Y = Q̂2N YN , X = 2N XN , β ∗ = Q̂β ∗ , W = W0 , R = Q̂R,

R̂ = Q̂R̂, Ŵ = 2Q̂ 2N σ + Rp and the chosen our truncation level N.
We fist check the assumption (1), (2), (3) of Theorem 2.1. We start with assumption (1).
From the definition of XN we have that 2N XN ∈ Zn×p and that for all i ∈ [n], j ∈ [p],
|(2N XN )ij | ≤ 2N |Xij |.
Therefore for C = E[|X1,1 |] < ∞ and arbitrary i ∈ [n], j ∈ [p],
E[|(2N XN )ij |] ≤ 2N E[|Xij |] = C2N ,
as we wanted. Furthermore, if f is the density function of the distribution D of the entries of X,
let c := kf k∞ < ∞, which is finite by our hypothesis. Now observe for arbitrary i ∈ [n], j ∈ [p],
N



P (2 XN )ij = k = P



k
k+1
≤ Xij ≤ N
N
2
2



19

=

Z

k+1
2N
k
2N

f (u)du ≤ kf k∞

Z

k+1
2N
k
2N

du =

c
.
2N

This verifies assumption (1) of Theorem 2.1. For assumption (2), notice that Q̂β ∗ is integer
valued, as Q̂ is assumed to be a mutliple of Q and β ∗ satisfies the Q-rationality property. Furthermore clearly
kQ̂β ∗ k∞ ≤ Q̂R.
For the noise part we have by (14) W0 = 2N Q̂YN − 2N XN Q̂β ∗ and therefore W0 ∈ Zn as all the
quantities 2N Q̂YN , 2N XN and Q̂β ∗ are integer-valued. Finally, assumption (3) follows from (14).
Now we check the assumptions
on the parameters from Theorem 2.1. We obtain from (14)

N
that kW k∞ ≤ 2Q̂ 2 σ + Rp . Using that σ = o( n1Q̂ ) and 2 log(npQ̂R) ≤ N we obtain
2N
2 N
2N
) + 2 2 = o( ).
n
n
n

Q̂R ≤ Q̂R̂ is verified and kW k∞ ≤ 2Q̂ 2N σ + Rp = Ŵ is also verified. The last step consists
of verifying (2) using (3). Plugging in our parameter choice it suffices to prove that the limit
kW k∞ = o(

 
(2n + p) 
N
2n + log n + p + 4 log p + 2 max{log(Q̂R̂), log(2Q̂ 2 σ + Rp )} + 4n log(cnp) − nN
lim
p→+∞
2
exists and is equal to −∞. Using that R̂ ≤ 2N σ + R̂p and R ≤ R̂ it suffices to show after
elementary algebraic manipulations that



(2n + p) 
2n + p + 4 log(np) + 2 log 2 + 2 log Q̂ + 2 log 2N σ + R̂p +4n log(cnp)−nN = −∞.
p→+∞
2
lim

Using now that for p sufficiently large

(2n + p)
(2n + p)
(2 log 2 + 4 log np) + 4n log(cnp) <
[10 log(np)] for all n ∈ Z>0 ,
2
2
it suffices to show



(2n + p) 
2n + p + 2 log Q̂ + 2 log 2N σ + R̂p + 10 log(np) − nN = −∞.
p→+∞
2
lim

which is exactly assumption (3). This completes the proof of Theorem 2.5.A.

5
5.1

Rest of the Proofs
Proof of Proposition 2.6

Proof. We apply Theorem 2.5.B. Since the model assumptions are identical we only need to check
the parameter assumptions of Theorem 2.5.B. We easily check that R̂ = R, the noise satisfies
√
1
σ ≤ 1 and finally Q̂ = Q. Both npσ = o( nQ
) and N ≥ 2 log (npQR) follow directly from

√
our assumption (5). Finally for assumption (4) we use N ≤ log σ1 to obtain 2N σ np + Rp ≤
2log(np)+log(Rp) . Using this it suffices to show


1
(2n + p) (2n + p + 2 log Q + 2 (log(np) + log(Rp)) + 10 log(np)) − nN = −∞.
lim
p→+∞ 2
20

which is implied if we establish
(2n + p)2
+ 7(2n + p) log(np) + (2n + p) log(RQ) − nN = −∞.
p→+∞
2
lim

Notice though that as ǫ > 0, for sufficiently large p, 7(2n + p) log(np) <
Therefore it suffices to have

ǫ (2n+p)2
,
2
2

for all n ∈ Z>0 .

ǫ (2n + p)2
+ (2n + p) log(RQ) − nN = −∞.
lim (1 + )
p→+∞
2
2
But (5) implies
ǫ (2n + p)2
ǫ (2n + p)2
(1 + )
+ (2n + p) log(RQ) − nN ≤ −
.
2
2
2
2
Clearly though
lim sup −
p→+∞

ǫ (2n + p)2
= −∞.
2
2

This completes the proof of Proposition 2.6.

5.2

Proof of Proposition 2.7

Proof. We first establish that kXk∞ ≤ (np)2 whp as p → +∞. By a union bound and Markov
inequality



1
2
E[|X11 |] = o(1).
P
max |Xij | > (np) ≤ npP |X11 | > (np)2 ≤
i∈[n],j∈[p]
np

Therefore with high probability kXk∞ ≤ (np)2 . Consider the set T (R, Q) of all the vectors
β ∗ ∈ [−R, R]p satisfying the Q-rationality assumption. The entries of these vectors are of the
form Qa for some a ∈ Z with |a| ≤ RQ. In particular |T (R, Q)| = (2QR + 1)p . Now because the
entries of X are continuously distributed, all Xβ ∗ with β ∗ ∈ T (R, Q) are distinct with probability
1. Furthermore by the above each one of them has L2 norm satisfies
kXβ ∗ k22 ≤ np2 kXk2∞ kβ ∗ k2∞ ≤ R2 n5 p6 < R2 (np)6 ,
w.h.p. as p → +∞.
Now we establish the proposition by contradiction. Suppose there exist a recovery mechanism
that can recover w.h.p. any such vector β ∗ after observing Y = Xβ ∗ + W ∈ Rn , where W has
n iid N(0, σ 2 ) entries. In the language of information theory such a recovery guarantee implies
that the Gaussian channel with power constraint R2 (np)6 and noise variance σ 2 needs to have
capacity at least
log |T (R, Q)|
p log (2QR + 1)
=
.
n
n
2
On the other hand, the capacity of
 this Gaussian channel with power R and noise variance Σ is
1
R
known to be equal to 2 log 1 + Σ2 (see for example Theorem 10.1.1 in [Cover and Thomas, 2006]).
In particular our Gaussian communication channel has capacity


R2 (np)6
1
log 1 +
.
2
σ2
21

From this we conclude


1
R2 (np)6
p log (2QR + 1)
,
≤ log 1 +
n
2
σ2
which implies
σ 2 ≤ R2 (np)6
or

1
2

2p log(2QR+1)
n

−1

,

 2p log(2QR+1)
− 21
n
,
σ ≤ R(np)3 2
−1

which completes the proof of the Proposition.

5.3

Proof of Proposition 2.8

Proof. The second part, where σ < σ01+ǫ , follows from Proposition 2.6 and the discussion above
the statement of the Proposition 2.8 which imply that LBR algorithms is succesfully working in
that regime.
For the first part it suffices to establish that under our assumptions for p sufficiently large,
 2p log(2QR+1)
− 21
n
σ01−ǫ > R(np)3 2
−1
.

Since n = o( logp p ) implies n = o(p) we obtain that for p sufficiently large,
2

2p log(2QR+1)
n

1

− 1 > 22(1− 2 ǫ)

p log(2QR+1)
n

which equivalently gives

or

 2p log(2QR+1)
− 21
p log(2QR+1)
1
n
n
< 2−(1− 2 ǫ)
2
−1

 2p log(2QR+1)
− 21
p log(2QR+1)
1
n
n
< R(np)3 2−(1− 2 ǫ)
R(np)3 2
−1
.

Therefore it suffices to show

1

R(np)3 2−(1− 2 ǫ)

p log(2QR+1)
n

≤ σ01−ǫ = 2−(1−ǫ)

p log(QR)
n

or equivalently by taking logarithms and performing elementary algebraic manipulations,

1
ǫ
ǫ
p log(2 +
) + p log RQ.
n log R + 3n log(np) ≤ 1 −
2
RQ
2

The condition n = o( logp p ) implies for sufficiently large p, n log(np) ≤ 4ǫ p and n log R ≤ 2ǫ p log QR.
Using both of these inequalities we conclude that for sufficiently large p,
ǫ
n log R + 3n log(np) ≤ p log QR
2

1
ǫ
ǫ
p log(2 +
) + p log RQ.
≤ 1−
2
RQ
2
This completes the proof.

22

References
[Andoni et al., 2017] Andoni, A., Hsu, D. J., Shi, K., and Sun, X. (2017). Correspondence
retrieval. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam,
The Netherlands, 7-10 July 2017, pages 105–126.
[Bora et al., 2017] Bora, A., Jalal, A., Price, E., and Dimakis, A. G. (2017). Compressed sensing
using generative models. In Proceedings of the 34th International Conference on Machine
Learning, ICML 2017, pages 537–546.
[Borno, 2011] Borno, M. A. (2011). Reduction in solving some integer least squares problems.
arXiv Preprint.
[Brunel and Boutros, 1999] Brunel, L. and Boutros, J. (1999). Euclidean space lattice decoding
for joint detection in cdma systems. In Proceedings of the 1999 IEEE Information Theory and
Communications Workshop (Cat. No. 99EX253).
[Candes et al., 2006] Candes, E. J., Romberg, J. K., and Tao, T. (2006). Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied
Mathematics, 59(8):1207–1223.
[Chen et al., 2001] Chen, S. S., Donoho, D. L., and Saunders, M. A. (2001). Atomic decomposition by basis pursuit. SIAM Rev., 43(1):129–159.
[Cover and Thomas, 2006] Cover, T. M. and Thomas, J. A. (2006). Elements of Information
Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience.
[Donoho, 2006] Donoho, D. L. (2006). Compressed sensing. IEEE Transactions on information
theory, 52(4):1289–1306.
[Donoho et al., 2013] Donoho, D. L., Javanmard, A., and Montanari, A. (2013). Informationtheoretically optimal compressed sensing via spatial coupling and approximate message passing. IEEE Transactions on Information Theory, 59(11):7434–7464.
[Donoho and Tanner, 2006] Donoho, D. L. and Tanner, J. (2006). Counting faces of randomlyprojected polytopes when then projection radically lowers dimension.
[Erdos and Lorentz, 1985] Erdos, P. and Lorentz, G. (1985). On the probability that n and g(n)
are relatively prime. Acta Arith., 5:524–531.
[Foucart and Rauhut, 2013] Foucart, S. and Rauhut, H. (2013). A mathematical introduction to
compressive sensing. Springer.
[Frieze, 1986] Frieze, A. M. (1986). On the lagarias-odlyzko algorithm for the subset sum problem. SIAM J. Comput., 15:536–539.
[Gamarnik and Zadik, 2017a] Gamarnik, D. and Zadik, I. (2017a). High dimensional linear regression with binary coefficients: Mean squared error and a phase transition. Conference on
Learning Theory (COLT).
23

[Gamarnik and Zadik, 2017b] Gamarnik, D. and Zadik, I. (2017b). Sparse high dimensional
linear regression: Algorithmic barrier and a local search algorithm.
[Hardy and Wright, 1975] Hardy, G. and Wright, E. (1975). An Introduction to the Theory of
Numbers. Oxford Science Publications, fifth edition edition.
[Hassibi and Boyd, 1998] Hassibi, A. and Boyd, S. (1998). Integer parameter estimation in linear
models with applications to gps. IEEE Transactions on Signal Processing.
[Hassibi and Vikalo, 2002] Hassibi, B. and Vikalo, H. (2002). On the expected complexity of
integer least-squares problems. In 2002 IEEE International Conference on Acoustics, Speech,
and Signal Processing.
[Krzakala et al., 2012] Krzakala, F., Mézard, M., Sausset, F., Sun, Y. F., and Zdeborová, L.
(2012). Statistical-physics-based reconstruction in compressed sensing. Phys. Rev. X, 2:021005.
[Lagarias and Odlyzko, 1985] Lagarias, J. C. and Odlyzko, A. M. (1985). Solving low-density
subset sum problems. Journal of the ACM (JACM), 32(1):229–246.
[Lempel, 1979] Lempel, A. (1979). Cryptology in transition. ACM Comput. Surv., 11(4):285–
303.
[Lenstra et al., 1982] Lenstra, A. K., Lenstra, H. W., and Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534.
[Merkle and Hellman, 1978] Merkle, R. and Hellman, M. (1978). Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 24(5):525–530.
[Shamir, 1982] Shamir, A. (1982). A polynomial time algorithm for breaking the basic merklehellman cryptosystem. In 23rd Annual Symposium on Foundations of Computer Science (sfcs
1982), pages 145–152.
[Wainwright, 2009] Wainwright, M. J. (2009). Sharp thresholds for high-dimensional and noisy
sparsity recovery using constrained quadratic programming (lasso). IEEE transactions on
information theory, 55(5):2183–2202.

24

