A note on column subset selection

DOI10.1093/IMRN/RNT172MaRDI QIDQ2935162zbMATH OpenOpenAlexFDO

Authors Pierre Youssef

Publication date 22 December 2014

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.0976

zbMATH Keywords

restricted invertibility theorem

Mathematics Subject Classification ID

Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Local theory of Banach spaces (46B07) General (adjoints, conjugates, products, inverses, domains, ranges, etc.) (47A05)

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.

Recommendations

• On a new method for controlling the entire spectrum in the problem of column subset selection
• Restricted invertibility revisited
• An improved approximation algorithm for the column subset selection problem
• An elementary proof of the restricted invertibility theorem
• Subset selection for matrices with fixed blocks

Cited in

(14)

• Column subset selection, matrix factorization, and eigenvalue optimization
• On a new method for controlling the entire spectrum in the problem of column subset selection
• scientific article; zbMATH DE number 7307477 (Why is no real title available?)
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• scientific article; zbMATH DE number 6982912 (Why is no real title available?)
• An elementary proof of the restricted invertibility theorem
• Almost orthogonal submatrices of an orthogonal matrix
• Empirical column selection method in the simplex method
• Restricted invertibility revisited
• A note on subset selection for matrices
• Subset selection for matrices with fixed blocks
• Extracting a basis with fixed block inside a matrix
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Invertibility of sub-matrices and the octahedron width theorem

This page was built for publication: A note on column subset selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2935162)