Box constrained ℓ₁ optimization in random linear systems -- asymptotics

2016/12/20 by Stojnic, Mihailo
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC) #Probability (math.PR)

paper · doi:10.48550/arxiv.1612.06835

Abstract

In this paper we consider box constrained adaptations of ℓ₁ 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 ℓ₁ adaptations (to which we will refer as the binary ℓ₁ and box ℓ₁) 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.

Related

• Box constrained ℓ₁ optimization in random linear systems -- finite dimensions
• Random linear systems with sparse solutions -- asymptotics and large deviations
• Partial ℓ₁ optimization in random linear systems -- phase transitions and large deviations
• Random linear systems with sparse solutions -- finite dimensions
• Partial ℓ₁ optimization in random linear systems -- finite dimensions