# Guessing Efficiently for Constrained Subspace Approximation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 55 references that are in the map.
- First posted on arXiv 29 Apr 2025.

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

- [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)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Greedy Column Subset Selection: New Bounds and Distributed Algorithms](https://mlsanity.com/paper/1605.08795/) (2016)
- [Input Sparsity and Hardness for Robust Subspace Approximation](https://mlsanity.com/paper/1510.06073/) (2015)
- [How to Solve Fair k-Center in Massive Data Models](https://mlsanity.com/paper/2002.07682/) (2020)
- [The Fine-Grained Hardness of Sparse Linear Regression](https://mlsanity.com/paper/2106.03131/) (2021)
- [Sparse PCA through Low-rank Approximations](https://mlsanity.com/paper/1303.0551/) (2013)
- [Regularized Weighted Low Rank Approximation](https://mlsanity.com/paper/1911.06958/) (2019)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [On Optimal Coreset Construction for Euclidean (k,z)-Clustering](https://mlsanity.com/paper/2211.11923/) (2022)
- [Approximate Sparse Linear Regression](https://mlsanity.com/paper/1609.08739/) (2016)
- [Fast Algorithms for ℓp-Regression](https://mlsanity.com/paper/2211.03963/) (2022)
- [Fair Column Subset Selection](https://mlsanity.com/paper/2306.04489/) (2023)
- [Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorization](https://mlsanity.com/paper/2306.01869/) (2023)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)

## Abstract (arXiv)

In this paper we study constrained subspace approximation problem. Given a set of n points a1,ldots,an in ℝd, the goal of the em subspace approximation problem is to find a k dimensional subspace that best approximates the input points. More precisely, for a given p≥ 1, we aim to minimize the pth power of the ℓp norm of the error vector (|a1-bmPa1|,ldots,|an-bmPan|), where bmP denotes the projection matrix onto the subspace and the norms are Euclidean. In constrained subspace approximation (CSA), we additionally have constraints on the projection matrix bmP. In its most general form, we require bmP to belong to a given subset S that is described explicitly or implicitly. We introduce a general framework for constrained subspace approximation. Our approach, that we term coreset-guess-solve, yields either (1+varepsilon)-multiplicative or varepsilon-additive approximations for a variety of constraints. We show that it provides new algorithms for partition-constrained subspace approximation with applications to it fair subspace approximation, k-means clustering, and projected non-negative matrix factorization, among others. Specifically, while we reconstruct the best known bounds for k-means clustering in Euclidean spaces, we improve the known results for the remainder of the problems.