English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the high-dimensional linear regression problem, where the algorithmic goal is to efficiently infer an unknown feature vector <inline-formula> <tex-math notation="LaTeX">$\beta ^{*}\in \mathbb {R}^{p}$ </tex-math></inline-formula> from its linear measurements, using a small number <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> of samples. Unlike most of the literature, we make no sparsity assumption on <inline-formula> <tex-math notation="LaTeX">$\beta ^{*}$ </tex-math></inline-formula>, but instead adopt a different regularization: In the noiseless setting, we assume <inline-formula> <tex-math notation="LaTeX">$\beta ^{*}$ </tex-math></inline-formula> consists of entries, which are either rational numbers with a common denominator <inline-formula> <tex-math notation="LaTeX">$Q\in \mathbb {Z}^{+}$ </tex-math></inline-formula> (referred to as <inline-formula> <tex-math notation="LaTeX">$Q-$ </tex-math></inline-formula>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&#x00E1;sz (LLL) lattice basis reduction algorithms, we propose a polynomial-time algorithm which provably recovers a <inline-formula> <tex-math notation="LaTeX">$\beta ^{*}\in \mathbb {R}^{p}$ </tex-math></inline-formula> enjoying the mixed-range assumption, from its linear measurements <inline-formula> <tex-math notation="LaTeX">$Y=X\beta ^{*}\in \mathbb {R}^{n}$ </tex-math></inline-formula> for a large class of distributions for the random entries of <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula>, even with one measurement (<inline-formula> <tex-math notation="LaTeX">$n=1$ </tex-math></inline-formula>). In the noisy setting, we propose a polynomial-time, lattice-based algorithm, which recovers a <inline-formula> <tex-math notation="LaTeX">$\beta ^{*}\in \mathbb {R}^{p}$ </tex-math></inline-formula> enjoying the <inline-formula> <tex-math notation="LaTeX">$Q-$ </tex-math></inline-formula>rationality property, from its noisy measurements <inline-formula> <tex-math notation="LaTeX">$Y=X\beta ^{*}+W\in \mathbb {R}^{n}$ </tex-math></inline-formula>, even from a single sample (<inline-formula> <tex-math notation="LaTeX">$n=1$ </tex-math></inline-formula>). We further establish that for large <inline-formula> <tex-math notation="LaTeX">$Q$ </tex-math></inline-formula>, 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 (<inline-formula> <tex-math notation="LaTeX">$n=1$ </tex-math></inline-formula>) 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.

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