Lifting ℓ1-optimization strong and sectional thresholds

In this paper we revisit under-determined linear systems of equations with sparse solutions. As is well known, these systems are among core mathematical problems of a very popular compressed sensing field. The popularity of the field as well as a substantial academic interest in linear systems with sparse solutions are in a significant part due to seminal results citeCRT,DonohoPol. Namely, working in a statistical scenario, citeCRT,DonohoPol provided substantial mathematical progress in characterizing relation between the dimensions of the systems and the sparsity of unknown vectors recoverable through a particular polynomial technique called ℓ1-minimization. In our own series of work citeStojnicCSetam09,StojnicUpper10,StojnicEquiv10 we also provided a collection of mathematical results related to these problems. While, Donoho's work citeDonohoPol,DonohoUnsigned established (and our own work citeStojnicCSetam09,StojnicUpper10,StojnicEquiv10 reaffirmed) the typical or the so-called weak threshold behavior of ℓ1-minimization many important questions remain unanswered. Among the most important ones are those that relate to non-typical or the so-called strong threshold behavior. These questions are usually combinatorial in nature and known techniques come up short of providing the exact answers. In this paper we provide a powerful mechanism that that can be used to attack the "tough" scenario, i.e. the strong threshold (and its a similar form called sectional threshold) of ℓ1-minimization.