Name
Abstract | ||
|---|---|---|
We propose a generic and simple technique called dyadic rounding for rounding real vectors to zero-one vectors, and show its several applications in approximating singular vectors of matrices by zero-one vectors, cut decompositions of matrices, and norm optimization problems. Our rounding technique leads to the following consequences. 1 Given any A∈ℝm ×n, there exists z∈{0, 1}n such that $$ \frac{\left\|Az\right\|_{q}}{\left\|z\right\|_{p}} \geq \Omega\left(p^{1 - \frac{1}{p}} (\log n)^{\frac{1}{p} - 1}\right) \left\|A\right\|_{p \mapsto q}, $$ where $\left\|A\right\|_{p \mapsto q} = \max_{x \neq 0} \left\|Ax\right\|_{q} / \left\|x\right\|_{p}$. Moreover, given any vector v∈ℝn we can round it to a vector z∈{0, 1}n with the same approximation guarantee as above, but now the guarantee is with respect to $\left\|Av\right\|_{q}/\left\|Av\right\|_{p}$ instead of $\left\|A\right\|_{p \mapsto q}$. Although stated for p ↦q norm, this generalizes to the case when $\left\|Az\right\|_{q}$ is replaced by any norm of z. 2 Given any A∈ℝm ×n, we can efficiently find z∈{0, 1}n such that $$ \frac{\left\|Az\right\|}{\left\|z\right\|} \geq \frac{\sigma_{1}(A)}{2 \sqrt{2 \log n}}, $$ where σ1(A) is the top singular value of A. Extending this, we can efficiently find orthogonalz1, z2, …, zk∈{0, 1}n such that $$ \frac{\left\|Az_{i}\right\|}{\left\|z_{i}\right\|} \geq \Omega\left(\frac{\sigma_{k}(A)}{\sqrt{k \log n}}\right), \quad \text{for all $i \in[k]$}. $$ We complement these results by showing that they are almost tight. 3 Given any A∈ℝm ×n of rank r, we can approximate it (under the Frobenius norm) by a sum of O(r log2m log2n) cut-matrices, within an error of at most $\left\|A\right\|_{F}/\text{poly}(m, n)$. In comparison, the Singular Value Decomposition uses r rank-1 terms in the sum (but not necessarily cut matrices) and has zero error, whereas the cut decomposition lemma by Frieze and Kannan in their algorithmic version of Szemerédi's regularity partition [9,10] uses only O(1/ε2) cut matrices but has a large ${\epsilon} \sqrt{mn} \left\|A\right\|_{F}$ error (under the cut norm). Our algorithm is deterministic and more efficient for the corresponding error range. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-31594-7_24 | ICALP |
Keywords | Field | DocType |
q norm,zero-one rounding,frobenius norm,norm optimization problem,singular vector,mapsto q,cut matrix,cut decomposition,log n,corresponding error range,cut norm,cut decomposition lemma,rounding,matrix norms,singular value decomposition | Singular value decomposition,Discrete mathematics,Combinatorics,Singular value,Matrix (mathematics),Matrix norm,Rounding,Omega,Partition (number theory),Mathematics | Conference |
Volume | ISSN | Citations |
7391 | 0302-9743 | 1 |
PageRank | References | Authors |
0.35 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amit Deshpande | 1 | 676 | 40.91 |
| Ravindran Kannan | 2 | 3893 | 850.76 |
| Nikhil Srivastava | 3 | 262 | 16.09 |