Column subset selection, matrix factorization, and eigenvalue optimization
From MaRDI portal
Eigenvalues, singular values, and eigenvectors (15A18) Factorization of matrices (15A23) Randomized algorithms (68W20) Analysis of algorithms (68W40) Semidefinite programming (90C22) Numerical computation of matrix norms, conditioning, scaling (65F35) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)
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)- Approximating sparsest cut in low rank graphs via embeddings from approximately low-dimensional spaces
- On greedy randomized average block Kaczmarz method for solving large linear systems
- scientific article; zbMATH DE number 7307477 (Why is no real title available?)
- Column subset selection problem is UG-hard
- An improved approximation algorithm for the column subset selection problem
- Optimal column subset selection for image classification by genetic algorithms
- Optimal and algorithmic norm regularization of random matrices
- Average block column action methods for solving least squares problems
- scientific article; zbMATH DE number 6982912 (Why is no real title available?)
- Low rank approximation of binary matrices: column subset selection and generalizations
- Improved bounds on sample size for implicit matrix trace estimators
- Perspectives on CUR decompositions
- Robust CUR Decomposition: Theory and Imaging Applications
- A greedy randomized average block projection method for linear feasibility problems
- Model order reduction with oblique projections for large scale wave propagation
- Empirical column selection method in the simplex method
- Stochastic dual coordinate descent with adaptive heavy ball momentum for linearly constrained convex optimization
- Faster randomized block Kaczmarz algorithms
- On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems
- Restricted invertibility revisited
- Interlacing polynomial method for the column subset selection problem
- Factorization norms and an inverse theorem for MaxCut
- Quantum query algorithms are completely bounded forms
- Tensor CUR decomposition under T-product and its perturbation
- Extracting a basis with fixed block inside a matrix
- Quantum query algorithms are completely bounded forms
- Randomized block Kaczmarz method with projection for solving least squares
- Subset selection for matrices
- A statistical view of column subset selection
- Block Kaczmarz method with inequalities
- Online randomized interpolative decomposition with \textit{a posteriori} error estimator for temporal PDE data reduction
- A two-level simultaneous orthogonal matching pursuit algorithm for simultaneous sparse approximation problems
- Solving sparse principal component analysis with global support
- Faster subset selection for matrices and applications
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)
