# Composable Core-sets for Determinant Maximization Problems via Spectral Spanners

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2018.

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Core-sets for Fair and Diverse Data Summarization](https://mlsanity.com/paper/2310.08122/) (2023)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)
- [Composable Coresets for Determinant Maximization: Greedy is Almost Optimal](https://mlsanity.com/paper/2309.15286/) (2023)

## Abstract (arXiv)

We study a spectral generalization of classical combinatorial graph spanners to the spectral setting. Given a set of vectors Vsubseteq Red, we say a set Usubseteq V is an α-spectral spanner if for all v∈ V there is a probability distribution μv supported on U such that vv^intercal preceq α·mathbbEu~μv uu^intercal. We show that any set V has an tildeO(d)-spectral spanner of size tildeO(d) and this bound is almost optimal in the worst case. We use spectral spanners to study composable core-sets for spectral problems. We show that for many objective functions one can use a spectral spanner, independent of the underlying functions, as a core-set and obtain almost optimal composable core-sets. For example, for the determinant maximization problem we obtain an tildeO(k)k-composable core-set and we show that this is almost optimal in the worst case. Our algorithm is a spectral analogue of the classical greedy algorithm for finding (combinatorial) spanners in graphs. We expect that our spanners find many other applications in distributed or parallel models of computation. Our proof is spectral. As a side result of our techniques, we show that the rank of diagonally dominant lower-triangular matrices are robust under `small perturbations' which could be of independent interests.