Approximating Matrices and Convex Bodies

Omer Friedland, Pierre Youssef

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)2519-2537
Number of pages19
JournalInternational Mathematics Research Notices
Volume2019
Issue number8
DOIs
StatePublished - 2019

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Approximating Matrices and Convex Bodies'. Together they form a unique fingerprint.

  • Cite this