Given a fixed matrix, the problem of column subset selectionudrequests a column submatrix that has favorable spectraludproperties. Most research from the algorithms andudnumerical linear algebra communities focuses on a variantudcalled rank-revealing QR, which seeks a well-conditionedudcollection of columns that spans the (numerical) range ofudthe matrix. The functional analysis literature containsudanother strand of work on column selection whose algorithmicudimplications have not been explored. In particular,uda celebrated result of Bourgain and Tzafriri demonstratesudthat each matrix with normalized columns containsuda large column submatrix that is exceptionally welludconditioned. Unfortunately, standard proofs of this resultudcannot be regarded as algorithmic. This paper presentsuda randomized, polynomial-time algorithm that producesudthe submatrix promised by Bourgain and Tzafriri. Theudmethod involves random sampling of columns, followed byuda matrix factorization that exposes the well-conditionedudsubset of columns. This factorization, which is due toudGrothendieck, is regarded as a central tool in modernudfunctional analysis. The primary novelty in this workudis an algorithm, based on eigenvalue minimization, forudconstructing the Grothendieck factorization. These ideasudalso result in an approximation algorithm for the (∞, 1)udnorm of a matrix, which is generally NP-hard to computeudexactly. As an added bonus, this work reveals a surprisingudconnection between matrix factorization and the famousudmaxcut semidefinite program.
展开▼
