2013/03/29 by Mihailo Stojnic, Stojnic, Mihailo · 11 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Applied mathematics #Computer science #Context (archaeology) #Core (optical fiber) #Discrete mathematics #Engineering #FOS: Computer and information sciences #FOS: Mathematics #Geometry #Information Theory (cs.IT) #Linear subspace #Mathematical analysis #Mathematical optimization #Mathematics #Optimization and Control (math.OC) #Polygon mesh #Polynomial #Probabilistic logic #Probability (math.PR) #Pure mathematics #Sparse and Compressive Sensing Techniques #Statistics #Tensor decomposition and applications #Theoretical computer science #Trap (plumbing) #Work (physics) #cs.IT #math.IT #math.OC #math.PR
paper · pdf · doi:10.48550/arxiv.1304.0003
published in arXiv (Cornell University) (Cornell University)
arxiv created 2013/03/29 · openalex publication_date 2013/03/29 · arxiv updated 2013/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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.