On Sketching Quadratic Forms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2015
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914339200434176 |
|---|---|
| author | Andoni, Alexandr Chen, Jiecao Krauthgamer, Robert Qin, Bo Woodruff, David P. Zhang, Qin |
| author_facet | Andoni, Alexandr Chen, Jiecao Krauthgamer, Robert Qin, Bo Woodruff, David P. Zhang, Qin |
| contents | We undertake a systematic study of sketching a quadratic form: given an $n \times n$ matrix $A$, create a succinct sketch $\textbf{sk}(A)$ which can produce (without further access to $A$) a multiplicative $(1+ε)$-approximation to $x^T A x$ for any desired query $x \in \mathbb{R}^n$. While a general matrix does not admit non-trivial sketches, positive semi-definite (PSD) matrices admit sketches of size $Θ(ε^{-2} n)$, via the Johnson-Lindenstrauss lemma, achieving the "for each" guarantee, namely, for each query $x$, with a constant probability the sketch succeeds. (For the stronger "for all" guarantee, where the sketch succeeds for all $x$'s simultaneously, again there are no non-trivial sketches.)
We design significantly better sketches for the important subclass of graph Laplacian matrices, which we also extend to symmetric diagonally dominant matrices. A sequence of work culminating in that of Batson, Spielman, and Srivastava (SIAM Review, 2014), shows that by choosing and reweighting $O(ε^{-2} n)$ edges in a graph, one achieves the "for all" guarantee. Our main results advance this front.
$\bullet$ For the "for all" guarantee, we prove that Batson et al.'s bound is optimal even when we restrict to "cut queries" $x\in \{0,1\}^n$.
In contrast, previous lower bounds showed the bound only for {\em spectral-sparsifiers}.
$\bullet$ For the "for each" guarantee, we design a sketch of size $\tilde O(ε^{-1} n)$ bits for "cut queries" $x\in \{0,1\}^n$. We prove a nearly-matching lower bound of $Ω(ε^{-1} n)$ bits. For general queries $x \in \mathbb{R}^n$, we construct sketches of size $\tilde{O}(ε^{-1.6} n)$ bits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1511_06099 |
| institution | arXiv |
| publishDate | 2015 |
| record_format | arxiv |
| spellingShingle | On Sketching Quadratic Forms Andoni, Alexandr Chen, Jiecao Krauthgamer, Robert Qin, Bo Woodruff, David P. Zhang, Qin Data Structures and Algorithms We undertake a systematic study of sketching a quadratic form: given an $n \times n$ matrix $A$, create a succinct sketch $\textbf{sk}(A)$ which can produce (without further access to $A$) a multiplicative $(1+ε)$-approximation to $x^T A x$ for any desired query $x \in \mathbb{R}^n$. While a general matrix does not admit non-trivial sketches, positive semi-definite (PSD) matrices admit sketches of size $Θ(ε^{-2} n)$, via the Johnson-Lindenstrauss lemma, achieving the "for each" guarantee, namely, for each query $x$, with a constant probability the sketch succeeds. (For the stronger "for all" guarantee, where the sketch succeeds for all $x$'s simultaneously, again there are no non-trivial sketches.) We design significantly better sketches for the important subclass of graph Laplacian matrices, which we also extend to symmetric diagonally dominant matrices. A sequence of work culminating in that of Batson, Spielman, and Srivastava (SIAM Review, 2014), shows that by choosing and reweighting $O(ε^{-2} n)$ edges in a graph, one achieves the "for all" guarantee. Our main results advance this front. $\bullet$ For the "for all" guarantee, we prove that Batson et al.'s bound is optimal even when we restrict to "cut queries" $x\in \{0,1\}^n$. In contrast, previous lower bounds showed the bound only for {\em spectral-sparsifiers}. $\bullet$ For the "for each" guarantee, we design a sketch of size $\tilde O(ε^{-1} n)$ bits for "cut queries" $x\in \{0,1\}^n$. We prove a nearly-matching lower bound of $Ω(ε^{-1} n)$ bits. For general queries $x \in \mathbb{R}^n$, we construct sketches of size $\tilde{O}(ε^{-1.6} n)$ bits. |
| title | On Sketching Quadratic Forms |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/1511.06099 |