Column subset selection, matrix factorization, and eigenvalue optimization
From MaRDI portal
Eigenvalues, singular values, and eigenvectors (15A18) Factorization of matrices (15A23) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Numerical computation of matrix norms, conditioning, scaling (65F35) Randomized algorithms (68W20) Analysis of algorithms (68W40) Semidefinite programming (90C22)
Abstract: Given a fixed matrix, the problem of column subset selection requests a column submatrix that has favorable spectral properties. Most research from the algorithms and numerical linear algebra communities focuses on a variant called rank-revealing {sf QR}, which seeks a well-conditioned collection of columns that spans the (numerical) range of the matrix. The functional analysis literature contains another strand of work on column selection whose algorithmic implications have not been explored. In particular, a celebrated result of Bourgain and Tzafriri demonstrates that each matrix with normalized columns contains a large column submatrix that is exceptionally well conditioned. Unfortunately, standard proofs of this result cannot be regarded as algorithmic. This paper presents a randomized, polynomial-time algorithm that produces the submatrix promised by Bourgain and Tzafriri. The method involves random sampling of columns, followed by a matrix factorization that exposes the well-conditioned subset of columns. This factorization, which is due to Grothendieck, is regarded as a central tool in modern functional analysis. The primary novelty in this work is an algorithm, based on eigenvalue minimization, for constructing the Grothendieck factorization. These ideas also result in a novel approximation algorithm for the norm of a matrix, which is generally {sf NP}-hard to compute exactly. As an added bonus, this work reveals a surprising connection between matrix factorization and the famous {sc maxcut} semidefinite program.
Recommendations
Cited in
(34)- Optimal column subset selection for image classification by genetic algorithms
- Empirical column selection method in the simplex method
- On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems
- On greedy randomized average block Kaczmarz method for solving large linear systems
- Perspectives on CUR decompositions
- Column subset selection problem is UG-hard
- scientific article; zbMATH DE number 6982912 (Why is no real title available?)
- Restricted invertibility revisited
- An improved approximation algorithm for the column subset selection problem
- Quantum query algorithms are completely bounded forms
- Extracting a basis with fixed block inside a matrix
- Randomized block Kaczmarz method with projection for solving least squares
- Quantum query algorithms are completely bounded forms
- Approximating sparsest cut in low rank graphs via embeddings from approximately low-dimensional spaces
- Low rank approximation of binary matrices: column subset selection and generalizations
- Tensor CUR decomposition under T-product and its perturbation
- Optimal and algorithmic norm regularization of random matrices
- scientific article; zbMATH DE number 7307477 (Why is no real title available?)
- Faster randomized block Kaczmarz algorithms
- Faster subset selection for matrices and applications
- Robust CUR Decomposition: Theory and Imaging Applications
- Solving sparse principal component analysis with global support
- Average block column action methods for solving least squares problems
- Interlacing polynomial method for the column subset selection problem
- Online randomized interpolative decomposition with \textit{a posteriori} error estimator for temporal PDE data reduction
- Stochastic dual coordinate descent with adaptive heavy ball momentum for linearly constrained convex optimization
- A greedy randomized average block projection method for linear feasibility problems
- Factorization norms and an inverse theorem for MaxCut
- A statistical view of column subset selection
- A two-level simultaneous orthogonal matching pursuit algorithm for simultaneous sparse approximation problems
- Subset selection for matrices
- Improved bounds on sample size for implicit matrix trace estimators
- Block Kaczmarz method with inequalities
- Model order reduction with oblique projections for large scale wave propagation
This page was built for publication: Column subset selection, matrix factorization, and eigenvalue optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4633911)
