  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.
