An Elementary Approach to the Problem of Column Selection in a Rectangular Matrix

摘要

The problem of extracting a well conditioned submatrix from any rectangular matrix (with e.g. normalized columns) has been a subject of extensive research with applications to machine learning (rank revealing factorization, sparse solutions to least squares regression problems, clustering,;;;), optimisation (low stretch spanning trees,;;•), and is also connected with problems in functional and harmonic analysis (Bourgain-Tzafriri restricted invertibility problem). In this paper, we provide a deterministic algorithm which extracts a submatrix Xs from any matrix X with guaranteed individual lower and upper bounds on each singular value of X_s. We are also able to deduce a slightly weaker (up to a log) version of the Bourgain-Tzafriri theorem as an immediate side result. We end the paper with a description of how our method applies to the analysis of a large data set and how its numerical efficiency compares with the method of Spieman and Srivastava.