2013/03/29 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.1304.0003
In our recent work \citeStojnicCSetam09,StojnicUpper10 we considered solving under-determined systems of linear equations with sparse solutions. In a large dimensional and statistical context we proved results related to performance of a polynomial ℓ1-optimization technique when used for solving such systems. As one of the tools we used a probabilistic result of Gordon \citeGordon88. In this paper we revisit this classic result in its core form and show how it can be reused to in a sense prove its own optimality.