# On Socially Fair Low-Rank Approximation and Column Subset Selection

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 77 references that are in the map.
- First posted on arXiv 8 Dec 2024.

## Builds on (most cited first, 30 of 48)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Algorithmic decision making and the cost of fairness](https://mlsanity.com/paper/1701.08230/) (2017)
- [Fairness in Criminal Justice Risk Assessments: The State of the Art](https://mlsanity.com/paper/1703.09207/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Regression: Quantitative Definitions and Reduction-based Algorithms](https://mlsanity.com/paper/1905.12843/) (2019)
- [A Convex Framework for Fair Regression](https://mlsanity.com/paper/1706.02409/) (2017)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Active Sampling for Min-Max Fairness](https://mlsanity.com/paper/2006.06879/) (2020)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Probabilistic Fair Clustering](https://mlsanity.com/paper/2006.10916/) (2020)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Fair Hierarchical Clustering](https://mlsanity.com/paper/2006.10221/) (2020)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [Efficient fair PCA for fair representation learning](https://mlsanity.com/paper/2302.13319/) (2023)
- [Convex Formulations for Fair Principal Component Analysis](https://mlsanity.com/paper/1802.03765/) (2018)
- [Near Optimal Linear Algebra in the Online and Sliding Window Models](https://mlsanity.com/paper/1805.03765/) (2018)
- [Fast and Efficient MMD-based Fair PCA via Optimization over Stiefel Manifold](https://mlsanity.com/paper/2109.11196/) (2021)

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

- [Fair PCA, One Component at a Time](https://mlsanity.com/paper/2503.21563/) (2025)
- [Active Learning with Low-Rank Structure for Data Selection](https://mlsanity.com/paper/2606.16045/) (2026)

## Abstract (arXiv)

Low-rank approximation and column subset selection are two fundamental and related problems that are applied across a wealth of machine learning applications. In this paper, we study the question of socially fair low-rank approximation and socially fair column subset selection, where the goal is to minimize the loss over all sub-populations of the data. We show that surprisingly, even constant-factor approximation to fair low-rank approximation requires exponential time under certain standard complexity hypotheses. On the positive side, we give an algorithm for fair low-rank approximation that, for a constant number of groups and constant-factor accuracy, runs in 2poly(k) time rather than the na"ive npoly(k), which is a substantial improvement when the dataset has a large number n of observations. We then show that there exist bicriteria approximation algorithms for fair low-rank approximation and fair column subset selection that run in polynomial time.