  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.
