A note on column subset selection

Pierre Youssef

Research output: Contribution to journalArticlepeer-review

Abstract

Given a matrix U, using a deterministic method, we extract a "large" submatrix of (whose columns are obtained by normalizing those of U) and control its smallest and largest singular value. We apply this result to the study of contact points of the unit ball of a finite normed space 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.

Original languageEnglish (US)
Pages (from-to)6431-6447
Number of pages17
JournalInternational Mathematics Research Notices
Volume2014
Issue number23
DOIs
StatePublished - 2014

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'A note on column subset selection'. Together they form a unique fingerprint.

Cite this