Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm

David Gamarnik, Ilias Zadik

We consider a sparse high dimensional regression model where the goal is to recover a $k$-sparse unknown vector ${\beta }^{\ast }$ from $n$ noisy linear observations of the form $Y=Xβ^*+W \in \…