A note on column subset selection

Understand

Given a matrix U, using a deterministic method, we extract a "large" submatrix of U'(whose columns are obtained by normalizing those of U) and estimate its smallest and largest singular value.

• We apply this result to the study of contact points of the unit ball with its maximal volume ellipsoid.
• We consider also the paving problem and give a deterministic algorithm to partition a matrix into almost isometric blocks recovering previous results of Bourgain-Tzafriri and Tropp.
• Finally, we partially answer a question raised by Naor about finding an algorithm in the spirit of Batson-Spielman-Srivastava's work to extract a "large" square submatrix of "small" norm.