# Column Subset Selection and Nystr"om Approximation via Continuous Optimization

arXiv: https://arxiv.org/abs/2304.09678 · HTML: https://mlsanity.com/paper/2304.09678/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2023.

## Built on by (most cited first, 1 of 1)

- [GRAFT: Gradient-Aware Fast MaxVol Technique for Dynamic Data Sampling](https://mlsanity.com/paper/2508.13653/) (2025)

## Abstract (arXiv)

We propose a continuous optimization algorithm for the Column Subset Selection Problem (CSSP) and Nystr"om approximation. The CSSP and Nystr"om method construct low-rank approximations of matrices based on a predetermined subset of columns. It is well known that choosing the best column subset of size k is a difficult combinatorial problem. In this work, we show how one can approximate the optimal solution by defining a penalized continuous loss function which is minimized via stochastic gradient descent. We show that the gradients of this loss function can be estimated efficiently using matrix-vector products with a data matrix X in the case of the CSSP or a kernel matrix K in the case of the Nystr"om approximation. We provide numerical results for a number of real datasets showing that this continuous optimization is competitive against existing methods.