2016/12/20 by Stojnic, Mihailo
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC) #Probability (math.PR)
paper · doi:10.48550/arxiv.1612.06516
In this paper we consider random linear under-determined systems with block-sparse solutions. A standard subvariant of such systems, namely, precisely the same type of systems without additional block structuring requirement, gained a lot of popularity over the last decade. This is of course in first place due to the success in mathematical characterization of an ℓ1 optimization technique typically used for solving such systems, initially achieved in \citeCRT,DOnoho06CS and later on perfected in \citeDonohoPol,DonohoUnsigned,StojnicCSetam09,StojnicUpper10. The success that we achieved in \citeStojnicCSetam09,StojnicUpper10 characterizing the standard sparse solutions systems, we were then able to replicate in a sequence of papers \citeStojnicCSetamBlock09,StojnicUpperBlock10,StojnicICASSP09block,StojnicJSTSP09 where instead of the standard ℓ1 optimization we utilized its an ℓ2/ℓ1 variant as a better fit for systems with block-sparse solutions. All of these results finally settled the so-called threshold/phase transitions phenomena (which naturally assume the asymptotic/large dimensional scenario). Here, in addition to a few novel asymptotic considerations, we also try to raise the level a bit, step a bit away from the asymptotics, and consider the finite dimensions scenarios as well.