Under-determined linear systems and ℓq-optimization thresholds

الأصل · EN

Recent studies of under-determined linear systems of equations with sparse solutions showed a great practical and theoretical efficiency of a particular technique called ℓ₁-optimization. Seminal works CRT,DOnoho06CS rigorously confirmed it for the first time. Namely, CRT,DOnoho06CS showed, in a statistical context, that ℓ₁ technique can recover sparse solutions of under-determined systems even when the sparsity is linearly proportional to the dimension of the system. A followup DonohoPol then precisely characterized such a linearity through a geometric approach and a series of workStojnicCSetam09,StojnicUpper10,StojnicEquiv10 reaffirmed statements of DonohoPol through a purely probabilistic approach. A theoretically interesting alternative to ℓ₁ is a more general version called ℓq (with an essentially arbitrary q). While ℓ₁ is typically considered as a first available convex relaxation of sparsity norm ℓ₀, ℓq,0≤ q≤ 1, albeit non-convex, should technically be a tighter relaxation of ℓ₀. Even though developing polynomial (or close to be polynomial) algorithms for non-convex problems is still in its initial phases one may wonder what would be the limits of an ℓq,0≤ q≤ 1, relaxation even if at some point one can develop algorithms that could handle its non-convexity. A collection of answers to this and a few realted questions is precisely what we present in this paper.