We study a spectral generalization of classical combinatorial graph spanners
to the spectral setting. Given a set of vectors $V\Re^d$, we say a
set $UV$ is an $\alpha$-spectral spanner if for all $vV$ there is
a probability distribution $\mu_v$ supported on $U$ such that $$vv^ıntercal
\alpha\cdotE_u\sim\mu_v uu^ıntercal.$$ We show that any set
$V$ has an $O(d)$-spectral spanner of size $O(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 $O(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.
Description
[1807.11648] Composable Core-sets for Determinant Maximization Problems via Spectral Spanners
%0 Journal Article
%1 indyk2018composable
%A Indyk, Piotr
%A Mahabadi, Sepideh
%A Gharan, Shayan Oveis
%A Rezaei, Alireza
%D 2018
%K computation sets theory
%T Composable Core-sets for Determinant Maximization Problems via Spectral
Spanners
%U http://arxiv.org/abs/1807.11648
%X We study a spectral generalization of classical combinatorial graph spanners
to the spectral setting. Given a set of vectors $V\Re^d$, we say a
set $UV$ is an $\alpha$-spectral spanner if for all $vV$ there is
a probability distribution $\mu_v$ supported on $U$ such that $$vv^ıntercal
\alpha\cdotE_u\sim\mu_v uu^ıntercal.$$ We show that any set
$V$ has an $O(d)$-spectral spanner of size $O(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 $O(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.
@article{indyk2018composable,
abstract = {We study a spectral generalization of classical combinatorial graph spanners
to the spectral setting. Given a set of vectors $V\subseteq \Re^d$, we say a
set $U\subseteq V$ is an $\alpha$-spectral spanner if for all $v\in V$ there is
a probability distribution $\mu_v$ supported on $U$ such that $$vv^\intercal
\preceq \alpha\cdot\mathbb{E}_{u\sim\mu_v} uu^\intercal.$$ We show that any set
$V$ has an $\tilde{O}(d)$-spectral spanner of size $\tilde{O}(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 $\tilde{O}(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.},
added-at = {2020-01-13T20:08:12.000+0100},
author = {Indyk, Piotr and Mahabadi, Sepideh and Gharan, Shayan Oveis and Rezaei, Alireza},
biburl = {https://www.bibsonomy.org/bibtex/2b271a89a815ab1994d9b38f6978dc09f/kirk86},
description = {[1807.11648] Composable Core-sets for Determinant Maximization Problems via Spectral Spanners},
interhash = {ff04a8b0a5ffd6706ed4bb429029d845},
intrahash = {b271a89a815ab1994d9b38f6978dc09f},
keywords = {computation sets theory},
note = {cite arxiv:1807.11648Comment: To appear in SODA 2020},
timestamp = {2020-01-13T20:08:12.000+0100},
title = {Composable Core-sets for Determinant Maximization Problems via Spectral
Spanners},
url = {http://arxiv.org/abs/1807.11648},
year = 2018
}