2011/12/30 by Haim Avron, Avron, Haim, Christos Boutsidis +1 · 5 citations
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Matrix Theory and Algorithms #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.1201.0127
We study subset selection for matrices defined as follows: given a matrix \matX ∈ \Rn × m (m > n) and an oversampling parameter k (n ≤ k ≤ m), 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.