Approximating matrices and convex bodies through Kadison-Singer

Omer Friedland, Pierre Youssef

Published 2016-05-12Version 1

We exploit the recent solution of the Kadison-Singer problem to show that any $n\times 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. We develop a sort of tensorization technique which allows to deal with a special kind of constraint approximation motivated by problems in convex geometry. As an application, we show that any convex body in $\mathbb{R}^n$ is arbitrary close to another one having $O(n)$ contact points. This fills the gap left in the literature after the results of Rudelson and Srivastava and completely answers the problem. As a consequence of this, we show that the method developed by Gu\'edon, Gordon and Meyer to establish the isomorphic Dvoretzky theorem yields to the best known result once we inject our improvement of Rudelson's theorem.