2013/06/17 by Mihailo Stojnic, Stojnic, Mihailo
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #cs.IT #math.IT #math.OC
paper · pdf · doi:10.48550/arxiv.1306.3778
acknowledgement footnote added arXiv admin note: text overlap with arXiv:1303.7289
openalex publication_date 2013/06/17 · arxiv created 2015/07/16 · arxiv updated 2015/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we look at a particular problem related to under-determined linear systems of equations with sparse solutions. ℓ1-minimization is a fairly successful polynomial technique that can in certain statistical scenarios find sparse enough solutions of such systems. Barriers of ℓ1 performance are typically referred to as its thresholds. Depending if one is interested in a typical or worst case behavior one then distinguishes between the weak thresholds that relate to a typical behavior on one side and the sectional and strong thresholds that relate to the worst case behavior on the other side. Starting with seminal works \citeCRT,DonohoPol,DOnoho06CS a substantial progress has been achieved in theoretical characterization of ℓ1-minimization statistical thresholds. More precisely, \citeCRT,DOnoho06CS presented for the first time linear lower bounds on all of these thresholds. Donoho's work \citeDonohoPol (and our own \citeStojnicCSetam09,StojnicUpper10) went a bit further and essentially settled the ℓ1's weak thresholds. At the same time they also provided fairly good lower bounds on the values on the sectional and strong thresholds. In this paper, we revisit the sectional thresholds and present a simple mechanism that can be used to create solid upper bounds as well. The method we present relies on a seemingly simple but substantial progress we made in studying Hopfield models in \citeStojnicHopBnds10.