Optimal Column-Based Low-Rank Matrix Reconstruction

Venkatesan Guruswami, Ali Kemal Sinop

Introduction

Low-rank matrix approximation is a cornerstone of modern data analysis, typically solved via Singular Value Decomposition (SVD). However, SVD produces "eigen-features" that are linear combinations of all original features, often stripping away the physical interpretability of the data. The Column Subset Selection Problem (CSSP) addresses this by seeking a small subset of the original columns that can approximate the data nearly as well as the SVD. This paper establishes the optimal theoretical trade-off between the number of columns selected ($r$) and the resulting approximation error.

The Column Subset Selection Problem

Given a matrix $X \in \mathbb{R}^{m \times n}$, we want to find $r$ columns whose span captures as much of the variance of $X$ as possible. Specifically, we aim for a $(1+\epsilon)$ approximation of the best rank-$k$ approximation in the Frobenius norm. Prior to this work, achieving a $(1+\epsilon)$ ratio often required $O(k^2)$ or $O(k \log k)$ columns. This paper proves that $r \approx k/\epsilon$ columns are sufficient and necessary, providing a tight bound that closes a long-standing gap in the literature.

Methodology: Volume Sampling and Schur-concavity

The authors base their approach on Volume Sampling, a technique where subsets of columns are chosen with probability proportional to the squared volume of the parallelepiped they span.

The core technical innovation is the use of Majorization and Schur-concavity. They prove that the ratio of specific symmetric polynomials (which relate to the eigenvalues of the matrix) is Schur-concave. This mathematical property allows them to formally prove that the approximation error is bounded by a specific ratio: $\sqrt{\frac{r+1}{r-k+1}}$. This formalizes the intuition that the "hardest" matrices to approximate are those where the singular values are nearly uniform.

Key Results and Algorithmic Efficiency

The primary contribution is the achievement of an optimal trade-off between the subset size $r$ and the approximation ratio. As shown in the comparison table below, this work provides the first deterministic algorithm to reach the $1+\epsilon$ bound with $r = k + \frac{k}{\epsilon} - 1$ columns.

Table 1: Performance and running time of various column selection algorithms compared to this work.

The paper introduces two main algorithms to find these columns:

  1. Deterministic: A derandomized version of volume sampling using conditional expectations that runs in $O(rnm^\omega \log m)$ time.
  2. Randomized: A faster sampling algorithm using binary search to pick indices, running in $O(rnm^2)$ time.

Optimality and Theoretical Impact

Beyond providing a new upper bound, the authors prove its optimality. By constructing a specific "block diagonal" matrix, they demonstrate that no algorithm can do significantly better than their $\frac{r+1}{r+1-k}$ ratio. They also extend existing lower bounds to show that even if you are allowed to use the full span of the $r$ selected columns (rather than just a rank-$k$ projection within that span), you still cannot beat the $1+\epsilon$ limit with fewer than $k/\epsilon$ columns.

Limitations and Future Work

While the algorithms are polynomial, the deterministic version involves matrix multiplication exponents ($\omega$), which can be slow for truly massive "big data" applications. Additionally, the results are specifically for the Frobenius norm; different bounds might apply to the Spectral norm or other error metrics. As a theoretical paper, it also does not address the numerical stability of implementing volume sampling on floating-point hardware, which can be a concern when dealing with very small singular values.

Summary updated

Abstract

We prove that for any real-valued matrix $X \in \R^{m \times n}$, and positive integers $r \ge k$, there is a subset of $r$ columns of $X$ such that projecting $X$ onto their span gives a $\sqrt{\frac{r+1}{r-k+1}}$-approximation to best rank-$k$ approximation of $X$ in Frobenius norm. We show that the trade-off we achieve between the number of columns and the approximation ratio is optimal up to lower order terms. Furthermore, there is a deterministic algorithm to find such a subset of columns that runs in $O(r n m^{\omega} \log m)$ arithmetic operations where $\omega$ is the exponent of matrix multiplication. We also give a faster randomized algorithm that runs in $O(r n m^2)$ arithmetic operations.
BibTeX
@inproceedings{guruswami2012optimal,
  author = {Venkatesan Guruswami and Ali Kemal Sinop},
  title = {{Optimal Column-Based Low-Rank Matrix Reconstruction}},
  booktitle = {SODA},
  year = {2012},
  url = {https://openreview.net/forum?id=HQxB6gjEeVz},
}
Figure