{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T21:55:43Z","timestamp":1758405343954,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,12,9]],"date-time":"2015-12-09T00:00:00Z","timestamp":1449619200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,8]]},"abstract":"<jats:p>Many fast graph algorithms begin by preprocessing the graph to improve its sparsity. A common form of this is spectral sparsification, which involves removing and reweighting the edges of the graph while approximately preserving its spectral properties. This task has a more general linear algebraic formulation in terms of approximating sums of rank-one matrices. This article considers a more general task of approximating sums of symmetric, positive semidefinite matrices of arbitrary rank. We present two deterministic, polynomial time algorithms for solving this problem. The first algorithm applies the pessimistic estimators of Wigderson and Xiao, and the second involves an extension of the method of Batson, Spielman, and Srivastava. These algorithms have several applications, including sparsifiers of hypergraphs, sparse solutions to semidefinite programs, sparsifiers of unique games, and graph sparsifiers with various auxiliary constraints.<\/jats:p>","DOI":"10.1145\/2746241","type":"journal-article","created":{"date-parts":[[2015,12,14]],"date-time":"2015-12-14T14:19:41Z","timestamp":1450102781000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Sparse Sums of Positive Semidefinite Matrices"],"prefix":"10.1145","volume":"12","author":[{"given":"Marcel K. De Carli","family":"Silva","sequence":"first","affiliation":[{"name":"University of Waterloo"}]},{"given":"Nicholas J. A.","family":"Harvey","sequence":"additional","affiliation":[{"name":"University of British Columbia, Canada"}]},{"given":"Cristiane M.","family":"Sato","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]}],"member":"320","published-online":{"date-parts":[[2015,12,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.985947"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(94)90357-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250823"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_2_1_7_1","volume-title":"Karger","author":"Bencz\u00far Andr\u00e1s A.","year":"2002","unstructured":"Andr\u00e1s A. Bencz\u00far and David R . Karger . 2002 . Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs . Available at http:\/\/arxiv.org\/abs\/cs\/0207078 Andr\u00e1s A. Bencz\u00far and David R. Karger. 2002. Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs. Available at http:\/\/arxiv.org\/abs\/cs\/0207078"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.21"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.37236\/3128"},{"key":"e_1_2_1_10_1","volume-title":"Sato","author":"de Carli Silva Marcel K.","year":"2011","unstructured":"Marcel K. de Carli Silva , Nicholas J. A. Harvey , and Cristiane M . Sato . 2011 . Sparse Sums of Positive Semidefinite Matrices . Available at http:\/\/arxiv.org\/abs\/1107.0088v1 Marcel K. de Carli Silva, Nicholas J. A. Harvey, and Cristiane M. Sato. 2011. Sparse Sums of Positive Semidefinite Matrices. Available at http:\/\/arxiv.org\/abs\/1107.0088v1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993647"},{"key":"e_1_2_1_12_1","volume-title":"Harvey","author":"Fung Wai Shing","year":"2010","unstructured":"Wai Shing Fung and Nicholas J. A . Harvey . 2010 . Graph Sparsification by Edge-Connectivity and Random Spanning Trees . Available at http:\/\/arxiv.org\/abs\/1005.0265v1 Wai Shing Fung and Nicholas J. A. Harvey. 2010. Graph Sparsification by Edge-Connectivity and Random Spanning Trees. Available at http:\/\/arxiv.org\/abs\/1005.0265v1"},{"key":"e_1_2_1_13_1","unstructured":"Ashish Goel Michael Kapralov and Sanjeev Khanna. 2010. Graph Sparsification via Refinement Sampling. Available at http:\/\/arxiv.org\/abs\/1004.4915  Ashish Goel Michael Kapralov and Sanjeev Khanna. 2010. Graph Sparsification via Refinement Sampling. Available at http:\/\/arxiv.org\/abs\/1004.4915"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1031049"},{"key":"e_1_2_1_15_1","unstructured":"Ramesh Hariharan and Debmalya Panigrahi. 2010a. A General Framework for Graph Sparsification. Available at http:\/\/arxiv.org\/abs\/1004.4080  Ramesh Hariharan and Debmalya Panigrahi. 2010a. A General Framework for Graph Sparsification. Available at http:\/\/arxiv.org\/abs\/1004.4080"},{"key":"e_1_2_1_16_1","unstructured":"Ramesh Hariharan and Debmalya Panigrahi. 2010b. A Linear-Time Algorithm for Sparsification of Unweighted Graphs. Available at http:\/\/arxiv.org\/abs\/1005.0670  Ramesh Hariharan and Debmalya Panigrahi. 2010b. A Linear-Time Algorithm for Sparsification of Unweighted Graphs. Available at http:\/\/arxiv.org\/abs\/1005.0670"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(94)00175-8"},{"key":"e_1_2_1_18_1","volume-title":"Johnson","author":"Horn Roger A.","year":"1990","unstructured":"Roger A. Horn and Charles R . Johnson . 1990 . Matrix Analysis. Cambridge University Press , Cambridge, MA. Roger A. Horn and Charles R. Johnson. 1990. Matrix Analysis. Cambridge University Press, Cambridge, MA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11496915_12"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/090762671"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.25"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","author":"Koutis Ioannis","year":"2012","unstructured":"Ioannis Koutis , Alex Levin , and Richard Peng . 2012 . Improved spectral sparsification and numerical algorithms for SDD matrices . In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912) . 266--277. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.STACS.2012.266 10.4230\/LIPIcs.STACS.2012.266 Ioannis Koutis, Alex Levin, and Richard Peng. 2012. Improved spectral sparsification and numerical algorithms for SDD matrices. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912). 266--277. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.STACS.2012.266"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195447"},{"key":"e_1_2_1_26_1","unstructured":"Laszlo Lov\u00e1sz. 2001. Semidefinite Programs and Combinatorial Optimization. Available at https:\/\/www.cs. elte.hu\/lovasz\/semidef.ps.  Laszlo Lov\u00e1sz. 2001. Semidefinite Programs and Combinatorial Optimization. Available at https:\/\/www.cs. elte.hu\/lovasz\/semidef.ps."},{"key":"e_1_2_1_27_1","first-page":"134","article-title":"The Lov\u00e1sz bound and some generalizations","volume":"3","author":"McEliece Robert J.","year":"1978","unstructured":"Robert J. McEliece , Eugene R. Rodemich , and Howard C. Rumsey , Jr. 1978 . The Lov\u00e1sz bound and some generalizations . Journal of Combinatorics, Information, and System Sciences 3 , 3, 134 -- 152 . Robert J. McEliece, Eugene R. Rodemich, and Howard C. Rumsey, Jr. 1978. The Lov\u00e1sz bound and some generalizations. Journal of Combinatorics, Information, and System Sciences 3, 3, 134--152.","journal-title":"Journal of Combinatorics, Information, and System Sciences"},{"volume-title":"Finite","author":"Newman Ilan","key":"e_1_2_1_28_1","unstructured":"Ilan Newman and Yuri Rabinovich . 2010. Finite Volume Spaces and Sparsification. Available at http:\/\/arxiv. org\/abs\/ 1002 .3541 Ilan Newman and Yuri Rabinovich. 2010. Finite Volume Spaces and Sparsification. Available at http:\/\/arxiv. org\/abs\/1002.3541"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081080290011692"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jfan.1998.3384"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2011-10863-3"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1056072"},{"key":"e_1_2_1_35_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency.","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver . 2003 . Combinatorial Optimization: Polyhedra and Efficiency. Vol. B: Matroids, Trees, Stable Sets. Springer-Verlag, Berlin, Germany. Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Vol. B: Matroids, Trees, Stable Sets. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-011-0194-2"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_39_1","series-title":"Lecture Notes in Mathematics","volume-title":"Geometric Aspects of Functional Analysis","author":"Srivastava Nikhil","unstructured":"Nikhil Srivastava . 2012. On contact points of convex bodies . In Geometric Aspects of Functional Analysis . Lecture Notes in Mathematics , vol. 2050 . Springer, Heidelberg , Germany , 393--412. DOI:http:\/\/dx.doi.org\/ 10.1007\/978-3-642-29849-3_25 10.1007\/978-3-642-29849-3_25 Nikhil Srivastava. 2012. On contact points of convex bodies. In Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 2050. Springer, Heidelberg, Germany, 393--412. DOI:http:\/\/dx.doi.org\/ 10.1007\/978-3-642-29849-3_25"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Joel Tropp. 2012. User-Friendly Tools for Random Matrices: An Introduction. Manuscript.  Joel Tropp. 2012. User-Friendly Tools for Random Matrices: An Introduction. Manuscript.","DOI":"10.21236\/ADA576100"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a003"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v18-2579"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_71"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746241","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2746241","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:44Z","timestamp":1750227404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746241"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,9]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2,8]]}},"alternative-id":["10.1145\/2746241"],"URL":"https:\/\/doi.org\/10.1145\/2746241","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2015,12,9]]},"assertion":[{"value":"2011-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}