2013/06/17 by Mihailo Stojnic, Stojnic, Mihailo
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC) #cs.IT #math.IT #math.OC
paper · pdf · doi:10.48550/arxiv.1306.3976
arXiv admin note: substantial text overlap with arXiv:1306.3774, arXiv:1306.3770
arxiv created 2013/06/17 · arxiv updated 2013/06/19
In this paper we look at a connection between the ℓq,0≤ q≤ 1, optimization and under-determined linear systems of equations with sparse solutions. The case q=1, or in other words ℓ1 optimization and its a connection with linear systems has been thoroughly studied in last several decades; in fact, especially so during the last decade after the seminal works \citeCRT,DOnoho06CS appeared. While current understanding of ℓ1 optimization-linear systems connection is fairly known, much less so is the case with a general ℓq,0<q<1, optimization. In our recent work \citeStojnicLqThrBnds10 we provided a study in this direction. As a result we were able to obtain a collection of lower bounds on various ℓq,0≤ q≤ 1, optimization thresholds. In this paper, we provide a substantial conceptual improvement of the methodology presented in \citeStojnicLqThrBnds10. Moreover, the practical results in terms of achievable thresholds are also encouraging. As is usually the case with these and similar problems, the methodology we developed emphasizes their a combinatorial nature and attempts to somehow handle it. Although our results' main contributions should be on a conceptual level, they already give a very strong suggestion that ℓq optimization can in fact provide a better performance than ℓ1, a fact long believed to be true due to a tighter optimization relaxation it provides to the original ℓ0 sparsity finding oriented original problem formulation. As such, they in a way give a solid boost to further exploration of the design of the algorithms that would be able to handle ℓq,0<q<1, optimization in a reasonable (if not polynomial) time.