# Column subset selection is NP-complete

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2017.

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

- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Smoothed Separable Nonnegative Matrix Factorization](https://mlsanity.com/paper/2110.05528/) (2021)
- [Fair Column Subset Selection](https://mlsanity.com/paper/2306.04489/) (2023)
- [Generalized Leverage Scores: Geometric Interpretation and Applications](https://mlsanity.com/paper/2206.08054/) (2022)
- [Moving Beyond Diversity: Visual Token Pruning as Subspace Reconstruction for Efficient VLMs](https://mlsanity.com/paper/2606.18681/) (2026)
- [Estimating leverage scores via rank revealing methods and randomization](https://mlsanity.com/paper/2105.11004/) (2021)
- [Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selection](https://mlsanity.com/paper/2106.06983/) (2021)
- [Syntactic vs Semantic Linear Abstraction and Refinement of Neural Networks](https://mlsanity.com/paper/2307.10891/) (2023)
- [A Statistical View of Column Subset Selection](https://mlsanity.com/paper/2307.12892/) (2023)

## Abstract (arXiv)

Let M be a real r× c matrix and let k be a positive integer. In the column subset selection problem (CSSP), we need to minimize the quantity |M-SA|, where A can be an arbitrary k× c matrix, and S runs over all r× k submatrices of M. This problem and its applications in numerical linear algebra are being discussed for several decades, but its algorithmic complexity remained an open issue. We show that CSSP is NP-complete.