REVIEW 4 cited by
Box constrained $\ell_1$ optimization in random linear systems -- asymptotics
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
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.
Forward citations
Cited by 4 Pith papers
-
Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view
Optimal spectral initializers at the theoretical phase retrieval threshold sit in flat landscape regions, so roughly 15% oversampling is needed for reliable descending algorithms.
-
Controlled Loosening-up (CLuP) -- achieving exact MIMO ML in polynomial time
CLuP, an iterative convex optimization algorithm, is claimed to achieve MIMO ML detection performance in polynomial time, but the claim rests on heuristic random duality arguments and an empirical iteration count.
-
Complexity analysis of the Controlled Loosening-up (CLuP) algorithm
Using Random Duality Theory, the paper argues that the CLuP algorithm reaches near-optimal MIMO ML detection in a small, dimension-independent number of quadratic-programming iterations.
-
Starting CLuP with polytope relaxation
CLuP-plt, a CLuP detector variant that starts from a box-constrained least-squares solution, reaches near-ML error rates within three to five iterations in the tested MIMO settings.
Discussion (0). Continue with ORCID to comment.