Faster Subset Selection for Matrices and Applications

Haim Avron, Christos Boutsidis

TL;DR

This paper tackles the problem of selecting a subset of $k$ columns from a matrix $\mathbf{X}$ (with more columns than rows) such that the pseudoinverse of the selected submatrix has the smallest possible norm. The authors introduce novel deterministic and randomized algorithms that achieve near-optimal approximation bounds, significantly improving upon existing methods. This work also reveals a surprising connection between matrix subset selection and the problem of finding low-stretch spanning trees in graphs.

What Problem Does This Paper Address?

The core problem is subset selection for matrices. Imagine you have a large dataset represented as a matrix $\mathbf{X}$, where each column is a feature and each row is an observation. Often, you want to work with a smaller, more manageable subset of these features (columns) while preserving as much of the original data's "information" as possible. Specifically, the authors focus on selecting $k$ columns (where $k$ is between the number of rows $n$ and the total number of columns $m$) such that the resulting $n \times k$ submatrix, when inverted (or more precisely, its pseudoinverse computed), has the smallest possible norm (either spectral or Frobenius). This is crucial for applications like low-rank matrix approximation, feature selection, and sparse regression, where the quality of the approximation directly depends on the chosen subset of columns. Existing methods often struggle with efficiency or achieving optimal approximation guarantees.

Methods

The paper presents several novel algorithms:

  • Deterministic Greedy Removal: Two algorithms (Algorithm 1 and Algorithm 2) employ a greedy strategy. Instead of selecting columns to keep, they iteratively remove columns that least impact the desired norm of the pseudoinverse. These algorithms leverage Singular Value Decomposition (SVD) and efficient SVD downdating techniques to achieve speedups.
  • Deterministic Greedy Selection: Algorithm 3 uses a different greedy approach, iteratively adding columns. It's based on a "Dual Set Spectral Sparsification" technique, which allows for simultaneous control over singular values.
  • Randomized Selection: Algorithm 4 uses a non-uniform random sampling strategy, inspired by matrix concentration bounds. This approach offers good approximation guarantees independent of specific matrix properties.
  • Volume Sampling: Algorithm 5 utilizes volume sampling, a technique related to maximizing the determinant of submatrices. This method is particularly interesting for its connection to graph problems.

What's new is the combination of these algorithmic strategies with SVD manipulation and the development of approximation bounds that are optimal up to constant factors. The paper also provides theoretical lower bounds to demonstrate the near-optimality of their algorithms.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and their performance guarantees for general matrices.

Key Insights and Ideas

  • Greedy Removal is Faster: The paper shows that a greedy strategy of removing columns can be significantly faster than selecting columns to keep, especially when leveraging SVD updates.
  • SVD is Key: Efficiently updating and manipulating SVDs is central to achieving the performance gains in the deterministic algorithms.
  • Graphs and Matrices are Linked: The most surprising insight is the direct correspondence between finding a low-stretch spanning tree in a graph and the Frobenius norm version of the subset selection problem. This connection opens doors for applying matrix techniques to graph problems and vice-versa.
  • Near-Optimal Bounds: The developed algorithms achieve approximation bounds that are theoretically optimal up to constant factors, meaning they are as good as possible in the worst case.

Key Results

  • Faster Algorithms: The proposed deterministic algorithms achieve approximation bounds comparable to or better than previous methods, with significantly reduced operation counts (e.g., factors of $n$ or $n^2$ faster in some cases).
  • Optimal Approximation Guarantees: For both spectral and Frobenius norms, the algorithms provide approximation bounds that are optimal up to constant factors.
  • Graph Connection: The paper establishes a formal link between low-stretch spanning trees and matrix subset selection, showing that finding a low-stretch spanning tree is equivalent to a specific instance of the Frobenius norm subset selection problem.
  • Lower Bounds: Theoretical lower bounds are derived, demonstrating that the upper bounds achieved by the proposed algorithms are indeed near-optimal.

Limitations and Future Work

  • Computational Complexity of Volume Sampling: While volume sampling is a powerful theoretical tool, efficiently sampling from it for arbitrary $k \ge n$ remains an open question.
  • Closing Gaps: The paper notes potential gaps between lower and upper bounds for certain parameter regimes (e.g., $k = \omega(n)$), suggesting room for further theoretical refinement.
  • Derandomization: The authors pose the question of whether the randomized algorithm (Theorem 3.11) can be derandomized.
  • Generalizing Rank Revealing: Extending rank-revealing factorization methods to sample arbitrary $k > n$ columns is also suggested as future work.
  • NP-Hardness: The NP-hardness of the Frobenius norm version of the subset selection problem is posed as an open question.

Summary updated

Abstract

We study the following problem of subset selection for matrices: given a matrix $\mathbf{X} \in \mathbb{R}^{n \times m}$ ($m > n$) and a sampling parameter $k$ ($n \le k \le m$), select a subset of $k$ columns from $\mathbf{X}$ such that the pseudoinverse of the sampled matrix has as small a 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.
BibTeX
@article{avron2013faster,
  author = {Haim Avron and Christos Boutsidis},
  title = {{Faster Subset Selection for Matrices and Applications}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2013},
  url = {https://openreview.net/forum?id=gqpGlxaOifJ},
}
Figure