Lifting ℓ₁-optimization strong and sectional thresholds

Original · EN

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 CRT,DonohoPol. Namely, working in a statistical scenario, CRT,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 ℓ₁-minimization. In our own series of work StojnicCSetam09,StojnicUpper10,StojnicEquiv10 we also provided a collection of mathematical results related to these problems. While, Donoho's work DonohoPol,DonohoUnsigned established (and our own work StojnicCSetam09,StojnicUpper10,StojnicEquiv10 reaffirmed) the typical or the so-called weak threshold behavior of ℓ₁-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 ℓ₁-minimization.