An Elementary Proof of the Restricted Invertibility Theorem

Abstract

We give an elementary proof of a generalization of Bourgain and Tzafriri's Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace.

submitted to Israel J. Math

Cited by in corpus (3)

• Minimal sequences and the Kadison-Singer problem
• A few remarks on sampling of signals with small spectrum
• Invertibility threshold for $H^{\infty }$ trace algebras, and effective matrix inversions