License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.39
URN: urn:nbn:de:0030-drops-66620
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6662/
Li, Yi ;
Woodruff, David P.
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings
Abstract
We consider the following oblivious sketching problem: given epsilon in (0,1/3) and n >= d/epsilon^2, design a distribution D over R^{k * nd} and a function f: R^k * R^{nd} -> R}, so that for any n * d matrix A, Pr_{S sim D} [(1-epsilon) |A|_{op} <= f(S(A),S) <= (1+epsilon)|A|_{op}] >= 2/3, where |A|_{op} = sup_{x:|x|_2 = 1} |Ax|_2 is the operator norm of A and S(A) denotes S * A, interpreting A as a vector in R^{nd}. We show a tight lower bound of k = Omega(d^2/epsilon^2) for this problem. Previously, Nelson and Nguyen (ICALP, 2014) considered the problem of finding a distribution D over R^{k * n} such that for any n * d matrix A, Pr_{S sim D}[forall x, (1-epsilon)|Ax|_2 <= |SAx|_2 <= (1+epsilon)|Ax|_2] >= 2/3, which is called an oblivious subspace embedding (OSE). Our result considerably strengthens theirs, as it (1) applies only to estimating the operator norm, which can be estimated given any OSE, and (2) applies to distributions over general linear operators S which treat A as a vector and compute S(A), rather than the restricted class of linear operators corresponding to matrix multiplication. Our technique also implies the first tight bounds for approximating the Schatten p-norm for even integers p via general linear sketches, improving the previous lower bound from k = Omega(n^{2-6/p}) [Regev, 2014] to k = Omega(n^{2-4/p}). Importantly, for sketching the operator norm up to a factor of alpha, where alpha - 1 = \Omega(1), we obtain a tight k = Omega(n^2/alpha^4) bound, matching the upper bound of Andoni and Nguyen (SODA, 2013), and improving the previous k = Omega(n^2/\alpha^6) lower bound. Finally, we also obtain the first lower bounds for approximating Ky Fan norms.
BibTeX - Entry
@InProceedings{li_et_al:LIPIcs:2016:6662,
author = {Yi Li and David P. Woodruff},
title = {{Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {39:1--39:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-018-7},
ISSN = {1868-8969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6662},
URN = {urn:nbn:de:0030-drops-66620},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.39},
annote = {Keywords: data streams, sketching, matrix norms, subspace embeddings}
}
|
Keywords: |
|
data streams, sketching, matrix norms, subspace embeddings |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
06.09.2016 |
