English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study a spectral generalization of classical combinatorial graph spannersto the spectral setting. Given a set of vectors $V\subseteq \Re^d$, we say aset $U\subseteq V$ is an $\alpha$-spectral spanner if for all $v\in V$ there isa 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 thisbound 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 almostoptimal composable core-sets. For example, for the determinant maximizationproblem we obtain an $\tilde{O}(k)^k$-composable core-set and we show that thisis almost optimal in the worst case.  Our algorithm is a spectral analogue of the classical greedy algorithm forfinding (combinatorial) spanners in graphs. We expect that our spanners findmany other applications in distributed or parallel models of computation. Ourproof is spectral. As a side result of our techniques, we show that the rank ofdiagonally dominant lower-triangular matrices are robust under `smallperturbations' which could be of independent interests.

Composable Core-sets for Determinant Maximization Problems via Spectral Spanners