Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

A note on column subset selection

Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00811804
Contributor : Pierre Youssef <>
Submitted on : Thursday, April 11, 2013 - 10:32:45 AM
Last modification on : Thursday, March 19, 2020 - 12:26:02 PM
Long-term archiving on: : Monday, April 3, 2017 - 4:02:19 AM

File

A_note_on_column_subset_select...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00811804, version 1

Collections

Citation

Pierre Youssef. A note on column subset selection. 2012. ⟨hal-00811804⟩

Share

Metrics

Record views

214

Files downloads

390