Document Open Access Logo

Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings

Authors Yi Li, David P. Woodruff

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.39.pdf
  • Filesize: 498 kB
  • 11 pages

Document Identifiers

Author Details

Yi Li
David P. Woodruff

Cite AsGet BibTex

Yi Li and David P. Woodruff. Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 39:1-39:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.39

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.
Keywords
  • data streams
  • sketching
  • matrix norms
  • subspace embeddings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137-147, 1999. Google Scholar
  2. Alexandr Andoni and Huy L. Nguyen. Eigenvalues of a matrix in the streaming model. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1729-1737, 2013. Google Scholar
  3. Alexandr Andoni, Huy L. Nguyên, Yury Polyanskiy, and Yihong Wu. Tight lower bound for linear sketches of moments. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 25-32, 2013. Google Scholar
  4. Marc Bury and Chris Schwiegelshohn. Sublinear estimation of weighted matchings in dynamic data streams. In the Proceedings of ESA, 2015. Google Scholar
  5. Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Commun. ACM, 55(6):111-119, 2012. Google Scholar
  6. Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 205-214, 2009. Google Scholar
  7. Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 81-90, 2013. Google Scholar
  8. Amit Deshpande, Madhur Tulsiani, and Nisheeth K. Vishnoi. Algorithms and hardness for subspace approximation. In SODA, pages 482-496, 2011. Google Scholar
  9. Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems 25, pages 2348-2356. 2012. Google Scholar
  10. Yuri Ingster and I. A. Suslina. Nonparametric Goodness-of-Fit Testing Under Gaussian Models. Springer, 1st edition, 2002. Google Scholar
  11. Robert Krauthgamer and Ori Sasson. Property testing of data dimensionality. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pages 18-27, 2003. Google Scholar
  12. Rafał Latała. Estimates of moments and tails of Gaussian chaoses. Ann. Probab., 34(6):2315-2331, 2006. Google Scholar
  13. Chao Li and Gerome Miklau. Measuring the achievable error of query sets under differential privacy. CoRR, abs/1202.3399, 2012. Google Scholar
  14. Yi Li, Huy L. Nguyen, and David P. Woodruff. On sketching matrix norms and the top singular vector. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1562-1581, 2014. Google Scholar
  15. Yi Li, Huy L. Nguyen, and David P. Woodruff. Turnstile streaming algorithms might as well be linear sketches. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 174-183, 2014. Google Scholar
  16. Yi Li, Zhengyu Wang, and David P. Woodruff. Improved testing of low rank matrices. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'14, New York, NY, USA - August 24-27, 2014, pages 691-700, 2014. Google Scholar
  17. Yi Li and David P. Woodruff. A tight lower bound for high frequency moment estimation with small error. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, pages 623-638, 2013. Google Scholar
  18. Yi Li and David P. Woodruff. On approximating functions of the singular values in a stream. In STOC, 2016. Google Scholar
  19. Xiangrui Meng and Michael W. Mahoney. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 91-100, 2013. Google Scholar
  20. Cameron Musco and Christopher Musco. Stronger approximate singular value decomposition via the block lanczos and power methods. CoRR, abs/1504.05477, 2015. Google Scholar
  21. Jelani Nelson and Huy L. Nguyen. OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 117-126, 2013. Google Scholar
  22. Jelani Nelson and Huy L. Nguyên. Lower bounds for oblivious subspace embeddings. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 883-894, 2014. Google Scholar
  23. Eric Price and David P. Woodruff. Applications of the shannon-hartley theorem to data streams and sparse recovery. In Proceedings of the 2012 IEEE International Symposium on Information Theory, ISIT 2012, Cambridge, MA, USA, July 1-6, 2012, pages 2446-2450, 2012. Google Scholar
  24. Oded Regev. Personal communication, 2014. Google Scholar
  25. Terence Tao. Topics in Random Matrix Theory. Graduate studies in mathematics. American Mathematical Society, 2012. Google Scholar
  26. Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 1st edition, 2008. Google Scholar
  27. Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Yonina C. Eldar and Gitta Kutyniok, editors, Compressed Sensing, pages 210-268. Cambridge University Press, 2012. Cambridge Books Online. URL: http://dx.doi.org/10.1017/CBO9780511794308.006.
  28. Karl Wimmer, Yi Wu, and Peng Zhang. Optimal query complexity for estimating the trace of a matrix. CoRR, abs/1405.7112, 2014. Google Scholar
  29. David P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact