We show that any n×m matrix A can be approximated in operator norm by a submatrix with a number of columns of order the stable rank of A. This improves on existing results by removing an extra logarithmic factor in the size of the extracted matrix. Our proof uses the recent solution of the Kadison-Singer problem. We also develop a sort of tensorization technique to deal with constraint approximation problems. As an application, we provide a sparsification result with equal weights and an optimal approximate John's decomposition for non-symmetric convex bodies. This enables us to show that any convex body in Rn is arbitrary close to another one having O(n) contact points and fills the gap left in the literature after the results of Rudelson and Srivastava by completely answering the problem. As a consequence, we also show that the method developed by Guédon, Gordon, and Meyer to establish the isomorphic Dvoretzky theorem yields to the best known result once we inject our improvements.
ASJC Scopus subject areas