A note on column subset selection

DOI10.1093/IMRN/RNT172zbMATH Open1318.46004arXiv1212.0976OpenAlexW3105179449MaRDI QIDQ2935162FDOQ2935162

Authors: Pierre Youssef 

Publication date: 22 December 2014

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

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.

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

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

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)

Cited In (13)

• Title not available (Why is that?)
• On a new method for controlling the entire spectrum in the problem of column subset selection
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• Title not available (Why is that?)
• An elementary proof of the restricted invertibility theorem
• 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
• Column subset selection, matrix factorization, and eigenvalue optimization

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)