Faster Subset Selection for Matrices and Applications

Details Faster Subset Selection for Matrices and Applications Faster Subset Selection for Matrices and Applications

2011-12-30

arxiv.org/abs/1201.0127v2

Computer Science

Data Structures and Algorithms

28 pages

Scientific paper

We study subset selection for matrices defined as follows: given a matrix $\matX \in \R^{n \times m}$ ($m > n$) and an oversampling parameter $k$ ($n \le k \le 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.

Affiliated with

Also associated with

No associations

Rating

Faster Subset Selection for Matrices and Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Faster Subset Selection for Matrices and Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Subset Selection for Matrices and Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-335497