# Fair Column Subset Selection

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 51 references that are in the map.
- First posted on arXiv 7 Jun 2023.

## Builds on (most cited first, 11 of 11)

- [AI Fairness 360: An Extensible Toolkit for Detecting, Understanding, and Mitigating Unwanted Algorithmic Bias](https://mlsanity.com/paper/1810.01943/) (2018)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Algorithmic Fairness](https://mlsanity.com/paper/2001.09784/) (2020)
- [FA*IR: A Fair Top-k Ranking Algorithm](https://mlsanity.com/paper/1706.06368/) (2017)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [Convex Formulations for Fair Principal Component Analysis](https://mlsanity.com/paper/1802.03765/) (2018)
- [Provable Deterministic Leverage Score Sampling](https://mlsanity.com/paper/1404.1530/) (2014)
- [Greedy Column Subset Selection: New Bounds and Distributed Algorithms](https://mlsanity.com/paper/1605.08795/) (2016)
- [Column subset selection is NP-complete](https://mlsanity.com/paper/1701.02764/) (2017)
- [Greedy Column Subset Selection for Large-scale Data Sets](https://mlsanity.com/paper/1312.6838/) (2013)
- [Modification-Fair Cluster Editing](https://mlsanity.com/paper/2112.03183/) (2021)

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

- [Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights](https://mlsanity.com/paper/2410.12913/) (2024)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [Guessing Efficiently for Constrained Subspace Approximation](https://mlsanity.com/paper/2504.20883/) (2025)
- [On the Hardness of Approximation of the Fair k-Center Problem](https://mlsanity.com/paper/2602.16688/) (2026)

## Abstract (arXiv)

The problem of column subset selection asks for a subset of columns from an input matrix such that the matrix can be reconstructed as accurately as possible within the span of the selected columns. A natural extension is to consider a setting where the matrix rows are partitioned into two groups, and the goal is to choose a subset of columns that minimizes the maximum reconstruction error of both groups, relative to their respective best rank-k approximation. Extending the known results of column subset selection to this fair setting is not straightforward: in certain scenarios it is unavoidable to choose columns separately for each group, resulting in double the expected column count. We propose a deterministic leverage-score sampling strategy for the fair setting and show that sampling a column subset of minimum size becomes NP-hard in the presence of two groups. Despite these negative results, we give an approximation algorithm that guarantees a solution within 1.5 times the optimal solution size. We also present practical heuristic algorithms based on rank-revealing QR factorization. Finally, we validate our methods through an extensive set of experiments using real-world data.