Lifting \(\ell_q\)-optimization thresholds

Abstract

In this paper we look at a connection between the \(\ell_q,0\leq q\leq 1\), optimization and under-determined linear systems of equations with sparse solutions. The case \(q=1\), or in other words \(\ell_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 \cite{CRT,DOnoho06CS} appeared. While current understanding of \(\ell_1\) optimization-linear systems connection is fairly known, much less so is the case with a general \(\ell_q,0<q<1\), optimization. In our recent work \cite{StojnicLqThrBnds10} we provided a study in this direction. As a result we were able to obtain a collection of lower bounds on various \(\ell_q,0\leq q\leq 1\), optimization thresholds. In this paper, we provide a substantial conceptual improvement of the methodology presented in \cite{StojnicLqThrBnds10}. 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 \(\ell_q\) optimization can in fact provide a better performance than \(\ell_1\), a fact long believed to be true due to a tighter optimization relaxation it provides to the original \(\ell_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 \(\ell_q,0<q<1\), optimization in a reasonable (if not polynomial) time.