Box constrained $\ell_1$ optimization in random linear systems -- asymptotics

Mihailo Stojnic

Published 2016-12-20Version 1

In this paper we consider box constrained adaptations of $\ell_1$ optimization heuristic when applied for solving random linear systems. These are typically employed when on top of being sparse the systems' solutions are also known to be confined in a specific way to an interval on the real axis. Two particular $\ell_1$ adaptations (to which we will refer as the \emph{binary} $\ell_1$ and \emph{box} $\ell_1$) will be discussed in great detail. Many of their properties will be addressed with a special emphasis on the so-called phase transitions (PT) phenomena and the large deviation principles (LDP). We will fully characterize these through two different mathematical approaches, the first one that is purely probabilistic in nature and the second one that connects to high-dimensional geometry. Of particular interest we will find that for many fairly hard mathematical problems a collection of pretty elegant characterizations of their final solutions will turn out to exist.