{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,11]],"date-time":"2023-11-11T00:24:18Z","timestamp":1699662258646},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2023,9,25]],"date-time":"2023-09-25T00:00:00Z","timestamp":1695600000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,9,25]],"date-time":"2023-09-25T00:00:00Z","timestamp":1695600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s00453-023-01172-6","type":"journal-article","created":{"date-parts":[[2023,9,25]],"date-time":"2023-09-25T09:02:25Z","timestamp":1695632545000},"page":"3957-3972","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Comparison of Matrix Norm Sparsification"],"prefix":"10.1007","volume":"85","author":[{"given":"Robert","family":"Krauthgamer","sequence":"first","affiliation":[]},{"given":"Shay","family":"Sapir","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,25]]},"reference":[{"key":"1172_CR1","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/11830924_26","volume-title":"Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques","author":"S Arora","year":"2006","unstructured":"Arora, S., Hazan, E., Kale, S.: A fast random sampling algorithm for sparsifying matrices. In: Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques, pp. 272\u2013279. Springer, New York (2006). https:\/\/doi.org\/10.1007\/11830924_26"},{"key":"1172_CR2","unstructured":"Achlioptas, D., Karnin, Z.S., Liberty, E.: Near-optimal entrywise sampling for data matrices. In: Advances in Neural Information Processing Systems, pp. 1565\u20131573 (2013). https:\/\/proceedings.neurips.cc\/paper\/2013\/hash\/6e0721b2c6977135b916ef286bcb49ec-Abstract.html"},{"issue":"2","key":"1172_CR3","doi-asserted-by":"publisher","first-page":"9-es","DOI":"10.1145\/1219092.1219097","volume":"54","author":"D Achlioptas","year":"2007","unstructured":"Achlioptas, D., McSherry, F.: Fast computation of low-rank matrix approximations. J ACM (JACM) 54(2), 9-es (2007). https:\/\/doi.org\/10.1145\/1219092.1219097","journal-title":"J ACM (JACM)"},{"key":"1172_CR4","doi-asserted-by":"publisher","unstructured":"Bakshi, A, Clarkson, K.L., Woodruff, D.P.: Low-rank approximation with 1\/$$\\epsilon $$$${}^{\\text{1\/3}}$$ matrix-vector products. In: 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1130\u20131143 (2022). https:\/\/doi.org\/10.1145\/3519935.3519988","DOI":"10.1145\/3519935.3519988"},{"key":"1172_CR5","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0653-8","volume-title":"Matrix Analysis","author":"R Bhatia","year":"1997","unstructured":"Bhatia, R.: Matrix Analysis. Graduate Texts in Mathematics, vol. 169. Springer-Verlag, New York (1997). https:\/\/doi.org\/10.1007\/978-1-4612-0653-8"},{"issue":"7","key":"1172_CR6","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1080\/00029890.2000.12005245","volume":"107","author":"R Bhatia","year":"2000","unstructured":"Bhatia, R.: Pinching, trimming, truncating, and averaging of matrices. Am. Math. Mon. 107(7), 602\u2013608 (2000)","journal-title":"Am. Math. Mon."},{"key":"1172_CR7","unstructured":"Braverman, V., Krauthgamer, R., Krishnan, A., Sapir, S.: Near-optimal entrywise sampling of numerically sparse matrices. In: Conference on Learning Theory, COLT, vol. 134, pp. 759\u2013773. Proceedings of Machine Learning Research. PMLR (2021). http:\/\/proceedings.mlr.press\/v134\/braverman21b.html"},{"issue":"1","key":"1172_CR8","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1080\/03081080290011674","volume":"50","author":"R Bhatia","year":"2002","unstructured":"Bhatia, R., Kahan, W., Li, R.-C.: Pinchings and norms of scaled triangular matrices. Linear Multilinear Algebra 50(1), 15\u201321 (2002)","journal-title":"Linear Multilinear Algebra"},{"issue":"6","key":"1172_CR9","doi-asserted-by":"publisher","first-page":"1704","DOI":"10.1137\/090772873","volume":"41","author":"J Batson","year":"2012","unstructured":"Batson, J., Spielman, D.A., Srivastava, N.: Twice-ramanujan sparsifiers. SIAM J Comput 41(6), 1704\u20131721 (2012). https:\/\/doi.org\/10.1137\/090772873","journal-title":"SIAM J Comput"},{"issue":"6","key":"1172_CR10","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1145\/2184319.2184343","volume":"55","author":"Emmanuel J Cand\u00e8s","year":"2012","unstructured":"Cand\u00e8s, Emmanuel J., Recht, Benjamin: Exact matrix completion via convex optimization. Commun. ACM 55(6), 111\u2013119 (2012). https:\/\/doi.org\/10.1145\/2184319.2184343","journal-title":"Commun. ACM"},{"issue":"10","key":"1172_CR11","doi-asserted-by":"publisher","first-page":"1493","DOI":"10.3182\/20090706-3-FR-2004.00249","volume":"42","author":"V Chandrasekaran","year":"2009","unstructured":"Chandrasekaran, V., Sanghavi, S., Parrilo, P.A., Willsky, A.S.: Sparse and low-rank matrix decompositions. IFAC Proc Vol 42(10), 1493\u20131498 (2009). https:\/\/doi.org\/10.3182\/20090706-3-FR-2004.00249","journal-title":"IFAC Proc Vol"},{"issue":"5","key":"1172_CR12","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1109\/TIT.2010.2044061","volume":"56","author":"Emmanuel J Cand\u00e8s","year":"2010","unstructured":"Cand\u00e8s, Emmanuel J., Tao, Terence: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inf. Theory 56(5), 2053\u20132080 (2010). https:\/\/doi.org\/10.1109\/TIT.2010.2044061","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"8","key":"1172_CR13","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/j.ipl.2011.01.010","volume":"111","author":"P Drineas","year":"2011","unstructured":"Drineas, P., Zouzias, A.: A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality. Inf. Process. Lett. 111(8), 385\u2013389 (2011). https:\/\/doi.org\/10.1016\/j.ipl.2011.01.010","journal-title":"Inf. Process. Lett."},{"key":"1172_CR14","first-page":"5269","volume":"31","author":"N Gupta","year":"2018","unstructured":"Gupta, N., Sidford, A.: Exploiting numerical sparsity for efficient learning: faster eigenvector computation and regression. Adv. Neural Inf. Process. Syst. 31, 5269\u20135278 (2018)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1172_CR15","unstructured":"Gittens, A., Tropp, J.A.: Error bounds for random matrix approximation schemes (2009). arXiv:0911.4108"},{"key":"1172_CR16","unstructured":"Kundu, A., Drineas, P.: A note on randomized element-wise matrix sparsification (2014). arXiv:1404.0320"},{"issue":"75","key":"1172_CR17","first-page":"1","volume":"18","author":"A Kundu","year":"2017","unstructured":"Kundu, A., Drineas, P., Magdon-Ismail, M.: Recovering PCA and sparse PCA via hybrid-($$l_1$$, $$l_2$$) sparse sampling of data elements. J. Mach. Learn. Res. 18(75), 1\u201334 (2017)","journal-title":"J. Mach. Learn. Res."},{"issue":"21","key":"1172_CR18","first-page":"1","volume":"20","author":"A Khetan","year":"2019","unstructured":"Khetan, A., Oh, S.: Spectrum estimation from a few entries. J. Mach. Learn. Res. 20(21), 1\u201355 (2019)","journal-title":"J. Mach. Learn. Res."},{"issue":"5","key":"1172_CR19","doi-asserted-by":"publisher","first-page":"2218","DOI":"10.1214\/16-AOS1525","volume":"45","author":"W Kong","year":"2017","unstructured":"Kong, W., Valiant, G.: Spectrum estimation from samples. Ann. Stat. 45(5), 2218\u20132247 (2017). https:\/\/doi.org\/10.1214\/16-AOS1525","journal-title":"Ann. Stat."},{"issue":"6","key":"1172_CR20","doi-asserted-by":"publisher","first-page":"2315","DOI":"10.1137\/16M1061850","volume":"47","author":"YT Lee","year":"2018","unstructured":"Lee, Y.T., Sun, H.: Constructing linear-sized spectral sparsification in almost-linear time. SIAM J. Comput 47(6), 2315\u20132336 (2018). https:\/\/doi.org\/10.1137\/16M1061850","journal-title":"SIAM J. Comput"},{"key":"1172_CR21","unstructured":"Li, Y., Woodruff, D.P.: Input-sparsity low rank approximation in schatten norm. In: Proceedings of the 37th International Conference on Machine Learning, ICML, vol. 119, pp. 6001\u20136009. Proceedings of machine learning research (2020). http:\/\/proceedings.mlr.press\/v119\/li20q.html"},{"issue":"3","key":"1172_CR22","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1093\/imaiai\/iav004","volume":"4","author":"NH Nguyen","year":"2015","unstructured":"Nguyen, N.H., Drineas, P., Tran, T.D.: Tensor sparsification via a bound on the spectral norm of random tensors. Inf. Inference J. IMA 4(3), 195\u2013229 (2015). https:\/\/doi.org\/10.1093\/imaiai\/iav004","journal-title":"Inf. Inference J. IMA"},{"key":"1172_CR23","unstructured":"Nie, F., Huang, H., Ding, C.H.Q.: Low-rank matrix recovery via efficient schatten p-norm minimization. In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (2012). http:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI12\/paper\/view\/5165"},{"issue":"1\u20133","key":"1172_CR24","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0012-365X(94)00115-Y","volume":"136","author":"P Pudl\u00e1k","year":"1994","unstructured":"Pudl\u00e1k, P., R\u00f6dl, V.: Some combinatorial-algebraic problems from complexity theory. Discrete Math. 136(1\u20133), 253\u2013279 (1994). https:\/\/doi.org\/10.1016\/0012-365X(94)00115-Y","journal-title":"Discrete Math."},{"issue":"3","key":"1172_CR25","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01076915","volume":"1","author":"SY Rotfel\u2019d","year":"1967","unstructured":"Rotfel\u2019d, S.Y.: Remarks on the singular numbers of a sum of completely continuous operators. Funct. Anal. Appl. 1(3), 95\u201396 (1967). https:\/\/doi.org\/10.1007\/BF01076915","journal-title":"Funct. Anal. Appl."},{"issue":"4","key":"1172_CR26","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1137\/08074489X","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D.A., Teng, S.-H.: Spectral sparsification of graphs. SIAM J. Comput. 40(4), 981\u20131025 (2011). https:\/\/doi.org\/10.1137\/08074489X","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1172_CR27","doi-asserted-by":"publisher","first-page":"285","DOI":"10.2140\/pjm.1976.66.285","volume":"66","author":"R Thompson","year":"1976","unstructured":"Thompson, R.: Convex and concave functions of singular values of matrix sums. Pac. J. Math. 66(1), 285\u2013290 (1976). https:\/\/doi.org\/10.2140\/pjm.1976.66.285","journal-title":"Pac. J. Math."},{"key":"1172_CR28","doi-asserted-by":"publisher","unstructured":"Valiant L.G.: Graph-theoretic arguments in low-level complexity. In: Mathematical Foundations of Computer Science, 6th Symposium, vol.\u00a053, pp. 162\u2013176. Lecture Notes in Computer Science. Springer (1977). https:\/\/doi.org\/10.1007\/3-540-08353-7_135","DOI":"10.1007\/3-540-08353-7_135"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01172-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01172-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01172-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,10]],"date-time":"2023-11-10T13:06:03Z","timestamp":1699621563000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01172-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,25]]},"references-count":28,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1172"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01172-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,25]]},"assertion":[{"value":"14 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}