Meshes that trap random subspaces

Abstract

In our recent work \cite{StojnicCSetam09,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 ${\ell }_1$-optimization technique when used for solving such systems. As one of the tools we used a probabilistic result of Gordon \cite{Gordon88}. 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.

References in corpus (6)

• Algorithmic linear dimension reduction in the l_1 norm for sparse vectors
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Block-length dependent thresholds in block-sparse compressed sensing
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• A rigorous geometry-probability equivalence in characterization of ${\ell }_1$-optimization
• Optimality of ${\ell }_2/{\ell }_1$-optimization block-length dependent thresholds

Cited by in corpus (1)

• The Gaussian min-max theorem in the Presence of Convexity