Faster subset selection for matrices and applications

DOI10.1137/120867287MaRDI QIDQ5413658zbMATH OpenOpenAlexFDO

Authors Haim Avron, Christos Boutsidis

Publication date 30 April 2014

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-means clusteringfeature selectionlow-rank approximationslow-stretch spanning treessparse approximationsubset selectionvolume sampling

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Combinatorial optimization (90C27)

Abstract: We study subset selection for matrices defined as follows: given a matrix $matXin{R}^{nimesm}$ ($m>n$) and an oversampling parameter $k$ ($nleklem$), select a subset of $k$ columns from $matX$ such that the pseudo-inverse of the subsampled matrix has as smallest norm as possible. In this work, we focus on the Frobenius and the spectral matrix norms. We describe several novel (deterministic and randomized) approximation algorithms for this problem with approximation bounds that are optimal up to constant factors. Additionally, we show that the combinatorial problem of finding a low-stretch spanning tree in an undirected graph corresponds to subset selection, and discuss various implications of this reduction.

Recommendations

• Subset selection for matrices with fixed blocks
• An improved approximation algorithm for the column subset selection problem
• Column subset selection via sparse approximation of SVD
• Subset selection in sparse matrices
• Column subset selection, matrix factorization, and eigenvalue optimization

Cited in

(38)

• Optimal column subset selection for image classification by genetic algorithms
• A branch-and-bound algorithm for the exact optimal experimental design problem
• Subset selection for matrices with fixed blocks
• Regularized greedy column subset selection
• Near-optimal discrete optimization for experimental design: a regret minimization approach
• Provable accelerated gradient method for nonconvex low rank optimization
• On a new method for controlling the entire spectrum in the problem of column subset selection
• Column subset selection problem is UG-hard
• Reverse iterative volume sampling for linear regression
• Fast Deterministic Selection
• An improved approximation algorithm for the column subset selection problem
• Column subset selection, matrix factorization, and eigenvalue optimization
• On computationally tractable selection of experiments in measurement-constrained regression models
• Extracting a basis with fixed block inside a matrix
• Subset selection in sparse matrices
• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• Gaussian process landmarking on manifolds
• Proportional volume sampling and approximation algorithms for \(A\)-optimal design
• A Local Search Framework for Experimental Design
• scientific article; zbMATH DE number 7307477 (Why is no real title available?)
• Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization
• Robust CUR Decomposition: Theory and Imaging Applications
• Lower bounds for column matrix approximations
• On the mean projection theorem for determinantal point processes
• Subset Selection and the Cone of Factor-Width-k Matrices
• A note on subset selection for matrices
• \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
• Interlacing polynomial method for the column subset selection problem
• Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
• Weighted least-squares approximation with determinantal point processes and generalized volume sampling
• Fast algorithms for maximizing the minimum eigenvalue in fixed dimension
• Bayesian D-optimal experimental designs via column subset selection
• Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows
• Approximating total effective resistance minimization with small budget
• Subset selection for matrices in spectral norm
• Approximating total effective resistance minimization with small budget
• Column subset selection via sparse approximation of SVD
• Subset selection for matrices

Describes a project that uses

Uses Software

• Blendenpik

This page was built for publication: Faster subset selection for matrices and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5413658)