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

David Gamarnik, Eren C. Kizildag, Ilias ZadikIEEE Trans. Information Theory 2021 · DOI

TL;DR

This paper tackles the challenge of inferring a high-dimensional regression vector ($\beta^*$) from limited linear measurements, even in the presence of noise. The authors introduce novel algorithms that leverage lattice basis reduction and integer relation detection, achieving efficient recovery without relying on traditional sparsity assumptions. This work is significant because it demonstrates that accurate inference is possible even with a single measurement, bridging a gap where prior methods failed and showing no statistical-computational gap exists for certain types of $\beta^*$.

What Problem Does This Paper Address?

The paper addresses the high-dimensional linear regression (HDR) problem, where we aim to recover a feature vector $\beta^* \in \mathbb{R}^p$ from $n$ linear measurements $Y = X\beta^*$ (or $Y = X\beta^* + W$ in the noisy case). The core challenge lies in the "large $p$, small $n$" regime, where $p$ (number of features) is much larger than $n$ (number of samples). In this scenario, the system is underdetermined, making recovery impossible without additional assumptions on $\beta^*$.

The dominant approach in the literature has been to assume $\beta^*$ is sparse (has few non-zero entries). While this has led to successful algorithms like LASSO and Basis Pursuit, these methods struggle when $n$ is very small (e.g., $n=1$) or when $\beta^*$ has a different structure. This paper aims to overcome these limitations by proposing a new regularization strategy based on the "mixed-support assumption" for $\beta^*$. This assumption allows $\beta^*$ to have entries that are either rational numbers with a common denominator or irrational numbers supported on a rationally independent set. This is a more general assumption than sparsity and is motivated by real-world applications like GPS and geodesy. The paper also investigates the single-sample ($n=1$) regime, where sparsity-based methods are known to fail, and aims to show that recovery is still computationally feasible.

Methods

The paper's core contribution lies in its novel algorithmic approaches that combine two powerful mathematical tools:

  • Lattice Basis Reduction (specifically, the LLL algorithm): This algorithm is used to find short vectors in a lattice. The authors construct specific lattices whose properties allow them to recover information about $\beta^*$.
  • Integer Relation Detection (specifically, the PSLQ algorithm): This algorithm finds linear combinations of numbers that result in zero. The authors leverage this to identify relationships between the observed data and the unknown $\beta^*$.

The paper proposes several algorithms tailored to different settings:

  • Extended Lagarias-Odlyzko (ELO) Algorithm: For the noisy, Q-rational setting, this algorithm extends the classical Lagarias-Odlyzko subset-sum algorithm. It involves generating random vectors, constructing a specific lattice, and applying LLL.
  • Lattice-Based Regression (LBR) Algorithm: This algorithm builds upon ELO for the noisy, Q-rational case, incorporating data truncation to handle finite-precision computations.
  • Joint Integer Relation and Subset Sum Algorithm (JIRSS): For the noiseless setting with irrational $\beta^*$ and integer-valued measurement matrices, this algorithm combines integer relation detection and a modified subset-sum approach.
  • Irrational High-Dimensional Regression (IHDR) Algorithm: For the noiseless setting with irrational $\beta^*$ and continuous-valued measurement matrices, this algorithm uses integer relation detection on a set derived from the data.
  • Mixed Irrational-Rational Regression (MIRR) and MIRR-C Algorithms: These algorithms handle the noiseless setting with mixed-support $\beta^*$, combining JIRSS and LBR (or IHDR for continuous matrices) to recover both rational and irrational components of $\beta^*$.

A key novelty is the application of these lattice-based techniques to the HDR problem under these specific structural assumptions on $\beta^*$, particularly in the challenging single-sample regime.

Datasets

Not discussed in the paper. The paper focuses on theoretical guarantees for algorithms operating on synthetic data generated according to specified distributions.

Key Insights and Ideas

  • Beyond Sparsity: The paper demonstrates that sparsity is not the only structural assumption that can enable efficient recovery in high-dimensional settings. The "mixed-support assumption" (rational entries with a common denominator, or rationally independent irrational entries) provides a viable alternative.
  • Single-Sample Recovery is Possible: A major takeaway is that accurate recovery of $\beta^*$ is achievable even with just one measurement ($n=1$), provided $\beta^*$ has the mixed-support structure and other parameters are within certain bounds. This challenges the notion that more samples are always fundamentally required for inference in HDR.
  • Algorithmic Connection: The work reveals a deep algorithmic connection between high-dimensional regression, integer relation detection, randomized subset-sum, and approximate shortest vector problems, all of which can be elegantly tackled using lattice-based methods.
  • No Statistical-Computational Gap: For the specific settings studied (e.g., Q-rationality in the noisy case, mixed-support in the noiseless case), the paper shows that what is information-theoretically possible to recover can also be achieved computationally efficiently, implying no inherent gap between statistical limits and algorithmic capabilities.
  • Noise Tolerance: For the noisy Q-rational case, the proposed algorithm achieves near information-theoretically optimal noise tolerance, drawing parallels to the capacity of Gaussian channels.

Key Results

  • Noiseless Recovery: Efficient polynomial-time algorithms are proposed for recovering $\beta^*$ with mixed-support (rational and irrational entries) from linear measurements, even with a single sample ($n=1$), under various assumptions on the measurement matrix $X$.
  • Noisy Recovery: For Q-rational $\beta^*$, a polynomial-time algorithm is presented that recovers $\beta^*$ from noisy measurements, also achieving single-sample recovery ($n=1$) under specific parameter conditions.
  • Noise Optimality: The noisy algorithm demonstrates near information-theoretically optimal noise tolerance for large $Q$ and Gaussian noise.
  • Phase Retrieval Application: The techniques are extended to the phase retrieval problem, enabling efficient recovery of complex-valued vectors from magnitude-only measurements, even with a single sample.
  • Algorithmic Guarantees: The paper provides formal performance guarantees (high probability recovery) for all proposed algorithms, specifying the conditions on parameters (e.g., $N$, $R$, $Q$, $\sigma$) under which they succeed.

Limitations and Future Work

  • Parameter Dependence: The performance guarantees and the required sample size/truncation level ($N$) often depend on parameters like $R$ (bound on $\beta^*$), $Q$ (common denominator), and $\sigma$ (noise level). The paper provides explicit bounds, but practical implementation might require careful tuning or estimation of these parameters.
  • Computational Model: The paper discusses different computational models (floating-point vs. real-valued arithmetic). While the algorithms are polynomial in the relevant parameters, the exact complexity can depend on the chosen model, especially for irrational entries.
  • Generalization of Support: While the mixed-support assumption is more general than sparsity, it still imposes specific structures on $\beta^*$. Extending the methods to more arbitrary or complex supports of $\beta^*$ remains an open area.
  • Future Work: The authors suggest that their work reveals algorithmic connections that can be further explored. The extension to more generalized observation models in phase retrieval is also mentioned. The paper also hints at the possibility of analyzing models with sparsity alongside the mixed-support assumption.

Summary updated

BibTeX
@article{gamarnik2021inference,
  author = {David Gamarnik and Eren C. Kizildag and Ilias Zadik},
  title = {{Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection}},
  journal = {IEEE Trans. Information Theory},
  year = {2021},
  doi = {10.1109/tit.2021.3113921},
}
Figure