{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:04Z","timestamp":1787337484061,"version":"build-2736575974"},"reference-count":74,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2018-T2-1-013"],"award-info":[{"award-number":["MOE2018-T2-1-013"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1750716"],"award-info":[{"award-number":["1750716"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1815840"],"award-info":[{"award-number":["CCF-1815840"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>This paper presents a systematic study of the space complexity of estimating the Schatten $p$-norms of an $n\\times n$ matrix in the turnstile streaming model. Both kinds of space complexities, bit complexity and sketching dimension, are considered. Furthermore, two sketching models, general linear sketching and bilinear sketching, are considered. When $p$ is not an even integer, we show that any one-pass algorithm with constant success probability requires near-linear space in terms of bits. This lower bound holds even for sparse matrices, i.e., matrices with $O(1)$ nonzero entries per row and per column. However, when $p$ is an even integer, we give for sparse matrices an upper bound which, up to logarithmic factors, is the same as estimating the $p$th moment of an $n$-dimensional vector. These results considerably strengthen lower bounds in previous work for arbitrary (not necessarily sparse) matrices. Similar near-linear lower bounds are obtained for Ky Fan norms, SVD entropy, eigenvalue shrinkers, and M-estimators, many of which could have been solvable in logarithmic space prior to this work. The results for general linear sketches give separations in the sketching complexity of Schatten $p$-norms with the corresponding vector $p$-norms, and rule out a table-lookup nearest-neighbor search for $p = 1$, making progress on a question of Andoni. The results for bilinear sketches are tight for the rank problem and nearly tight for $p\\geq 2$; the latter is the first general subquadratic upper bound for sketching the Schatten norms.<\/jats:p>","DOI":"10.1137\/17m1152255","type":"journal-article","created":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T11:10:27Z","timestamp":1573729827000},"page":"1643-1697","source":"Crossref","is-referenced-by-count":2,"title":["On Approximating Matrix Norms in Data Streams"],"prefix":"10.1137","volume":"48","author":[{"given":"Yi","family":"Li","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huy L.","family":"Nguy\u1ec5n","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,11,14]]},"reference":[{"key":"atypb1","unstructured":"Wasserstein,\n                      Distance vs. Total Variation Distance\n                      ,https:\/\/mathoverflow.net\/questions\/194803\/1-wasserstein-distance-v-s-total-variation-distance, 25 January 2015 (accessed 1 January 2019)."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.97.18.10101"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"A. Andoni,\n                      Nearest neighbor search in high-dimensional spaces\n                      , presented at the Barriers in Computational Complexity Workshop II, 2010,http:\/\/www.mit.edu\/~andoni\/nns-barriers.pdf.","DOI":"10.1007\/978-3-642-22993-0_1"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"A. Andoni, R. Krauthgamer, and K. Onak,\n                      Streaming algorithms via precision sampling\n                      , in Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), 2011, pp. 363-372.","DOI":"10.1109\/FOCS.2011.82"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"A. Andoni, R. Krauthgamer, and I. P. Razenshteyn,\n                      Sketching and embedding are equivalent for norms\n                      , in Proceedings of the 47th ACM Symposium on Theory of Computing (STOC), 2015, pp. 479-488.","DOI":"10.1145\/2746539.2746552"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"A. Andoni and H. L. Nguy\\ \u00ean,\n                      Eigenvalues of a matrix in the streaming model\n                      , in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '13), 2013, pp. 1729-1737,https:\/\/doi.org\/10.1137\/1.9781611973105.124.","DOI":"10.1137\/1.9781611973105.124"},{"key":"atypb8","first-page":"25","author":"Andoni A.","year":"2013","journal-title":"Berlin"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"G. A. Andrews, R. Askey, and R. Roy,\n                      Special Functions\n                      , Cambridge University Press, Cambridge, UK, 1999.","DOI":"10.1017\/CBO9781107325937"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"S. Assadi, S. Khanna, and Y. Li,\n                      On estimating maximum matching size in graph streams\n                      , in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '17), 2017, pp. 1723-1742,https:\/\/doi.org\/10.1137\/1.9781611974782.113.","DOI":"10.1137\/1.9781611974782.113"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis,\n                      Exponential separation of quantum and classical one-way communication complexity\n                      , in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), 2004, pp. 128-137.","DOI":"10.1145\/1007352.1007379"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"atypb13","first-page":"817","volume":"68","author":"Bozkurt \u015e. B.","year":"2012","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"atypb14","unstructured":"V. Braverman, S. R. Chestnut, R. Krauthgamer, and L. F. Yang,\n                      Sketches for Matrix Norms: Faster, Smaller and More General\n                      , preprint,https:\/\/arxiv.org\/abs\/1609.05885v1, 2016."},{"key":"atypb15","unstructured":"V. Braverman, J. Katzman, C. Seidell, and G. Vorsanger,\n                      An optimal algorithm for large frequency moments using ${O}(n^{1-2\/k})$ bits\n                      , in Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM), LIPIcs 28, K. Jansen et al., eds., Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2014, pp. 531-544."},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"M. Bury and C. Schwiegelshohn,\n                      Sublinear estimation of weighted matchings in dynamic data streams\n                      , in Proceedings of Algorithms-ESA 2015, 23rd Annual European Symposium, Patras, Greece, Lecture Notes in Comput. Sci., 9294, Springer, Berlin, 2015, pp. 263-274.","DOI":"10.1007\/978-3-662-48350-3_23"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184343"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"A. Chakrabarti, S. Khot, and X. Sun,\n                      Near-optimal lower bounds on the multi-party communication complexity of set disjointness\n                      , in Proceedings of the 18th Annual IEEE Conference on Computational Complexity, 2003, pp. 107-117.","DOI":"10.1109\/CCC.2003.1214414"},{"key":"atypb19","first-page":"693","author":"Charikar M.","year":"2002","journal-title":"Berlin"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"atypb21","first-page":"257","volume":"4","author":"Chatterjee S.","year":"2008","journal-title":"ALEA Lat. Am. J. Probab. Math. Stat."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"H. Y. Cheung, L. C. Lau, and K. M. Leung,\n                      Graph connectivities, network coding, and expander graphs\n                      , in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS '11), 2011, pp. 190-199.","DOI":"10.1109\/FOCS.2011.55"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/3019134"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"atypb25","unstructured":"M. S. Crouch and A. McGregor,\n                      Periodicity and cyclic shifts via linear sketches\n                      , in Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 14th International Workshop (APPROX 2011) and 15th International Workshop (RANDOM 2011), Princeton, NJ, L. A. Goldberg, K. Jansen, R. Ravi, and J. D. P. Rolim, eds., Springer, Berlin, 2011, pp. 158-170."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1561\/0100000004"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1038\/135917b0"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"A. Deshpande, M. Tulsiani, and N. K. Vishnoi,\n                      Algorithms and hardness for subspace approximation\n                      , in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11), 2011, pp. 482-496,https:\/\/doi.org\/10.1137\/1.9781611973082.39.","DOI":"10.1137\/1.9781611973082.39"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/140962097"},{"key":"atypb30","unstructured":"K. Driver and K. Jordan,\n                      Zeroes of the hypergeometric polynomials ${F}(-n,b;c;z)$\n                      , in Algorithms for Approximations IV: 2001 International Symposium, Huddersfield, UK, 2002, pp. 436-445."},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"P. Flajolet and G. N. Martin,\n                      Probabilistic counting\n                      , in Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1983, pp. 76-82.","DOI":"10.1109\/SFCS.1983.46"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"atypb33","unstructured":"S. Ganguly,\n                      A Lower Bound for Estimating High Moments of a Data Stream\n                      , preprint,https:\/\/arxiv.org\/abs\/1201.0253, 2011."},{"key":"atypb34","first-page":"542","author":"Ganguly S.","year":"2015","journal-title":"Berlin"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf,\n                      Exponential separations for one-way quantum communication complexity, with applications to cryptography\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), 2007, pp. 516-525.","DOI":"10.1145\/1250790.1250866"},{"key":"atypb36","unstructured":"M. Gavish and D. L. Donoho,\n                      Optimal Shrinkage of Singular Values\n                      , Tech. report 2014-08, Department of Statistics, Stanford University, 2014."},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"C. Gentry,\n                      Fully homomorphic encryption using ideal lattices\n                      , in Proceedings of the 41st ACM Symposium on Theory of Computing (STOC), 2009, pp. 169-178.","DOI":"10.1145\/1536414.1536440"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.3150\/bj\/1089206408"},{"key":"atypb39","unstructured":"R. L. Graham, D. E. Knuth, and O. Patashnik,\n                      Concrete Mathematics: A Foundation for Computer Science\n                      , 2nd ed., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-008-5054-x"},{"key":"atypb41","first-page":"2339","author":"Hardt M.","year":"2012","journal-title":"Curran Associates Inc."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"atypb43","first-page":"737","author":"Indyk P.","year":"2008","journal-title":"Philadelphia"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"P. Indyk and D. P. Woodruff,\n                      Optimal approximations of the frequency moments of data streams\n                      , in Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC0), 2005, pp. 202-208.","DOI":"10.1145\/1060590.1060621"},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"Y. Ingster and I. A. Suslina,\n                      Nonparametric Goodness-of-Fit Testing Under Gaussian Models\n                      , Springer, Berlin, 2002.","DOI":"10.1007\/978-0-387-21580-8"},{"key":"atypb46","first-page":"562","author":"Jayram T. S.","year":"2009","journal-title":"Berlin"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"H. Jowhari, M. Saglam, and G. Tardos,\n                      Tight bounds for ${L}_p$ samplers, finding duplicates in streams, and related problems\n                      , in Proceedings of the 30th ACM SIGMOD PODS Conference, 2011, pp. 49-58.","DOI":"10.1145\/1989284.1989289"},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"D. M. Kane, J. Nelson, E. Porat, and D. P. Woodruff,\n                      Fast moment estimation in data streams in optimal space\n                      , in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC '11), 2011, pp. 745-754.","DOI":"10.1145\/1993636.1993735"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"D. M. Kane, J. Nelson, and D. P. Woodruff,\n                      On the exact space complexity of sketching and streaming small norms\n                      , in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10), 2010, pp. 1161-1178,https:\/\/doi.org\/10.1137\/1.9781611973075.93.","DOI":"10.1137\/1.9781611973075.93"},{"key":"atypb50","first-page":"1","volume":"20","author":"Khetan A.","year":"2019","journal-title":"J. Mach. Learn. Res."},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1525"},{"key":"atypb52","unstructured":"R. Krauthgamer and O. Sasson,\n                      Property testing of data dimensionality\n                      , in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '03), 2003, pp. 18-27."},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1015957395"},{"key":"atypb54","first-page":"272","author":"Li C.","year":"2013","journal-title":"New York"},{"key":"atypb55","doi-asserted-by":"crossref","unstructured":"Y. Li, H. L. Nguyen, and D. P. Woodruff,\n                      Turnstile streaming algorithms might as well be linear sketches\n                      , in Proceedings of the 2014 ACM Symposium on Theory of Computing (STOC '14), 2014, pp. 174-183.","DOI":"10.1145\/2591796.2591812"},{"key":"atypb56","unstructured":"Y. Li and D. P. Woodruff,\n                      A tight lower bound for high frequency moment estimation with small error\n                      , in Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop (APPROX 2013) and 17th International Workshop (RANDOM 2013), Berkeley, CA, P. Raghavendra, S. Raskhodnikova, K. Jansen, and J. D. P. Rolim, eds., Springer, Berlin, 2013, pp. 623-638."},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"issue":"114","key":"atypb58","first-page":"507","volume":"72","author":"Mar\u010denko V. A.","year":"1967","journal-title":"S.)"},{"key":"atypb59","doi-asserted-by":"crossref","unstructured":"X. Meng and M. W. Mahoney,\n                      Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression\n                      , in Proceedings of the 2013 ACM Symposium on Theory of Computing (STOC '13), 2013, pp. 91-100.","DOI":"10.1145\/2488608.2488621"},{"key":"atypb60","doi-asserted-by":"crossref","unstructured":"M. Monemizadeh and D. P. Woodruff, 1\\em-pass relative-error ${L}_p$-sampling with applications, in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10), 2010, pp. 1143-1160,https:\/\/doi.org\/10.1137\/1.9781611973075.92.","DOI":"10.1137\/1.9781611973075.92"},{"key":"atypb61","unstructured":"J. Nelson and H. L. Nguyen,\n                      OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings\n                      , preprint,https:\/\/arxiv.org\/abs\/1211.1002, 2012."},{"key":"atypb62","doi-asserted-by":"crossref","unstructured":"E. Price and D. P. Woodruff,\n                      Applications of the Shannon-Hartley theorem to data streams and sparse recovery\n                      , in Proceedings of the 2012 IEEE International Symposium on Information Theory Proceedings (ISIT), 2012, pp. 2446-2450.","DOI":"10.1109\/ISIT.2012.6283954"},{"key":"atypb63","unstructured":"I. Razenshteyn,\n                      Personal communication\n                      , 2015."},{"key":"atypb64","unstructured":"R.D. Reiss,\n                      Approximate Distributions of Order Statistics: With Applications to Nonparametric Statistics\n                      , Springer Texts in Statistics, Springer-Verlag, New York, 2008."},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.01.010"},{"key":"atypb66","doi-asserted-by":"crossref","unstructured":"T. Sarl\u00f3s,\n                      Improved approximation algorithms for large matrices via random projections\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 143-152.","DOI":"10.1109\/FOCS.2006.37"},{"key":"atypb67","unstructured":"R. Sedgewick and P. Flajolet,\n                      An Introduction to the Analysis of Algorithms\n                      , Addison-Wesley, Boston, 1996."},{"key":"atypb68","first-page":"410","volume":"56","author":"Stevanovic D.","year":"2009","journal-title":"Acta Chim. Slov."},{"key":"atypb69","doi-asserted-by":"crossref","unstructured":"E. Verbin and W. Yu,\n                      The streaming complexity of cycle counting, sorting by reversals, and other problems\n                      , in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11), 2011, pp. 11-25,https:\/\/doi.org\/10.1137\/1.9781611973082.2.","DOI":"10.1137\/1.9781611973082.2"},{"key":"atypb70","doi-asserted-by":"crossref","unstructured":"R. Vershynin,\n                      Introduction to the non-asymptotic analysis of random matrices\n                      , in Compressed Sensing: Theory and Applications, Y. C. Eldar and G. Kutyniok, eds., Cambridge University Press, Cambridge, UK, 2011.","DOI":"10.1017\/CBO9780511794308.006"},{"key":"atypb71","unstructured":"Wolfram Research,\n                      Generalized Hypergeometric Function $_{3}F_{2}$: Integral Representation\n                      ,http:\/\/functions.wolfram.com\/HypergeometricFunctions\/Hypergeometric3F2\/07\/01\/01\/0001\/, 29 October 2001 (accessed 29 March 2015)."},{"key":"atypb72","unstructured":"D. Xia,\n                      Optimal Schatten-$q$ and Ky-Fan-$k$ Norm Rate of Low Rank Matrix Estimation\n                      , preprint,https:\/\/arxiv.org\/abs\/1403.6499, 2014."},{"key":"atypb73","doi-asserted-by":"publisher","DOI":"10.1016\/S0262-8856(96)01112-2"},{"key":"atypb74","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2008.06.023"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1152255","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:14Z","timestamp":1787335994000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1152255"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":74,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1152255"],"URL":"https:\/\/doi.org\/10.1137\/17m1152255","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}