# Greedy Column Subset Selection: New Bounds and Distributed Algorithms

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2016.

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

- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Sequential Attention for Feature Selection](https://mlsanity.com/paper/2209.14881/) (2022)
- [PMSS: Pretrained Matrices Skeleton Selection for LLM Fine-tuning](https://mlsanity.com/paper/2409.16722/) (2024)
- [Fair Column Subset Selection](https://mlsanity.com/paper/2306.04489/) (2023)
- [Tight Bounds for Volumetric Spanners and Applications](https://mlsanity.com/paper/2310.00175/) (2023)
- [Generalized Leverage Scores: Geometric Interpretation and Applications](https://mlsanity.com/paper/2206.08054/) (2022)
- [Reweighted Solutions for Weighted Low Rank Approximation](https://mlsanity.com/paper/2406.02431/) (2024)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [Syntactic vs Semantic Linear Abstraction and Refinement of Neural Networks](https://mlsanity.com/paper/2307.10891/) (2023)
- [Entrywise error bounds for low-rank approximations of kernel matrices](https://mlsanity.com/paper/2405.14494/) (2024)
- [Guessing Efficiently for Constrained Subspace Approximation](https://mlsanity.com/paper/2504.20883/) (2025)

## Abstract (arXiv)

The problem of column subset selection has recently attracted a large body of research, with feature selection serving as one obvious and important application. Among the techniques that have been applied to solve this problem, the greedy algorithm has been shown to be quite effective in practice. However, theoretical guarantees on its performance have not been explored thoroughly, especially in a distributed setting. In this paper, we study the greedy algorithm for the column subset selection problem from a theoretical and empirical perspective and show its effectiveness in a distributed setting. In particular, we provide an improved approximation guarantee for the greedy algorithm which we show is tight up to a constant factor, and present the first distributed implementation with provable approximation factors. We use the idea of randomized composable core-sets, developed recently in the context of submodular maximization. Finally, we validate the effectiveness of this distributed algorithm via an empirical study.