{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:06:08Z","timestamp":1750309568182,"version":"3.41.0"},"reference-count":83,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T00:00:00Z","timestamp":1743033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-2104528"],"award-info":[{"award-number":["CCF-2104528"]}]},{"name":"NSF","award":["CCF-2112665"],"award-info":[{"award-number":["CCF-2112665"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"<jats:p>\n            We consider the problem of approximating a\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(d \\times d\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            covariance matrix\n            <jats:italic>M<\/jats:italic>\n            with a rank-\n            <jats:italic>k<\/jats:italic>\n            matrix under\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((\\varepsilon ,\\delta)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -differential privacy. We present and analyze a complex variant of the Gaussian mechanism and obtain upper bounds on the Frobenius norm of the difference between the matrix output by this mechanism and the best rank-\n            <jats:italic>k<\/jats:italic>\n            approximation to\n            <jats:italic>M<\/jats:italic>\n            . Our analysis provides improvements over previous bounds, particularly when the spectrum of\n            <jats:italic>M<\/jats:italic>\n            satisfies natural structural assumptions. The novel insight is to view the addition of Gaussian noise to a matrix as a continuous-time matrix Brownian motion. This viewpoint allows us to track the evolution of eigenvalues and eigenvectors of the matrix, which are governed by stochastic differential equations discovered by Dyson. These equations enable us to upper bound the Frobenius distance between the best rank-\n            <jats:italic>k<\/jats:italic>\n            approximation of\n            <jats:italic>M<\/jats:italic>\n            and that of a Gaussian perturbation of\n            <jats:italic>M<\/jats:italic>\n            as an integral that involves inverse eigenvalue gaps of the stochastically evolving matrix, as opposed to a sum of perturbation bounds obtained via Davis-Kahan-type theorems. Subsequently, again using the Dyson Brownian motion viewpoint, we show that the eigenvalues of the matrix\n            <jats:italic>M<\/jats:italic>\n            perturbed by Gaussian noise have large gaps with high probability. These results also contribute to the analysis of low-rank approximations under average-case perturbations, and to an understanding of eigenvalue gaps for random matrices, both of which may be of independent interest.\n          <\/jats:p>\n          <jats:p\/>","DOI":"10.1145\/3716496","type":"journal-article","created":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T07:41:52Z","timestamp":1738827712000},"page":"1-88","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5228-1313","authenticated-orcid":false,"given":"Oren","family":"Mangoubi","sequence":"first","affiliation":[{"name":"Mathematical Sciences, Worcester Polytechnic Institute, Worcester, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0255-1119","authenticated-orcid":false,"given":"Nisheeth K.","family":"Vishnoi","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, United States"}]}],"member":"320","published-online":{"date-parts":[[2025,3,27]]},"reference":[{"issue":"2","key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"9\u2013es","DOI":"10.1145\/1219092.1219097","article-title":"Fast computation of low-rank matrix approximations","volume":"54","author":"Achlioptas Dimitris","year":"2007","unstructured":"Dimitris Achlioptas and Frank McSherry. 2007. Fast computation of low-rank matrix approximations. Journal of the ACM 54, 2 (2007), 9\u2013es.","journal-title":"Journal of the ACM"},{"key":"e_1_3_2_3_2","article-title":"Differentially private covariance estimation","volume":"32","author":"Amin Kareem","year":"2019","unstructured":"Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskii. 2019. Differentially private covariance estimation. Advances in Neural Information Processing Systems 32 (2019), 1\u201310.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_4_2","volume-title":"An Introduction to Random Matrices","author":"Anderson Greg W.","year":"2010","unstructured":"Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni. 2010. An Introduction to Random Matrices. Vol. 118. Cambridge University Press."},{"issue":"4","key":"e_1_3_2_5_2","first-page":"2648","article-title":"Extreme gaps between eigenvalues of random matrices","volume":"41","author":"Arous G\u00e9rard Ben","year":"2013","unstructured":"G\u00e9rard Ben Arous and Paul Bourgade. 2013. Extreme gaps between eigenvalues of random matrices. Annals of Probability 41, 4 (2013), 2648\u20132681.","journal-title":"Annals of Probability"},{"issue":"4","key":"e_1_3_2_6_2","first-page":"2648","article-title":"Extreme gaps between eigenvalues of random matrices","volume":"41","author":"Arous G\u00e9rard Ben","year":"2013","unstructured":"G\u00e9rard Ben Arous and Paul Bourgade. 2013. Extreme gaps between eigenvalues of random matrices. Annals of Probability 41, 4 (2013), 2648\u20132681.","journal-title":"Annals of Probability"},{"key":"e_1_3_2_7_2","first-page":"1","volume-title":"Proceedings of KDD Cup and Workshop 2007","author":"Bennett James","year":"2007","unstructured":"James Bennett and Stan Lanning. 2007. The Netflix Prize. In Proceedings of KDD Cup and Workshop 2007. ACM, New York, NY, USA, 1\u20134."},{"key":"e_1_3_2_8_2","volume-title":"Matrix Analysis","author":"Bhatia Rajendra","year":"2013","unstructured":"Rajendra Bhatia. 2013. Matrix Analysis. Vol. 169. Springer Science & Business Media."},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1109\/FOCS.2012.67","volume-title":"Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science","author":"Blocki Jeremiah","year":"2012","unstructured":"Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. 2012. The Johnson-Lindenstrauss transform itself preserves differential privacy. In Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE, 410\u2013419."},{"key":"e_1_3_2_10_2","first-page":"1283","volume-title":"Annales Scientifiques de l\u2019Ecole Normale Superieure","author":"Blomer Valentin","year":"2017","unstructured":"Valentin Blomer, Jean Bourgain, Maksym Radziwi\u0142\u0142, and Zeev Rudnick. 2017. Small gaps in the spectrum of the rectangular billiard. In Annales Scientifiques de l\u2019Ecole Normale Superieure, Vol. 50. Societe Mathematique de France, 1283\u20131300."},{"key":"e_1_3_2_11_2","first-page":"128","volume-title":"Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems","author":"Blum Avrim","year":"2005","unstructured":"Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. 2005. Practical privacy: The SuLQ framework. In Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 128\u2013138."},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","DOI":"10.1017\/9781108755528","volume-title":"Foundations of Data Science","author":"Blum Avrim","year":"2020","unstructured":"Avrim Blum, John Hopcroft, and Ravindran Kannan. 2020. Foundations of Data Science. Cambridge University Press."},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/3-540-17171-1_2","article-title":"Spectral fluctuations of classically chaotic quantum systems","volume":"263","author":"Bohigas Oriol","year":"1986","unstructured":"Oriol Bohigas, Marie-Joya Giannoni, and Charles Schmit. 1986. Spectral fluctuations of classically chaotic quantum systems. Quantum Chaos and Statistical Nuclear Physics 263 (1986), 18\u201340.","journal-title":"Quantum Chaos and Statistical Nuclear Physics"},{"issue":"1","key":"e_1_3_2_14_2","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/s00220-016-2627-6","article-title":"The eigenvector moment flow and local quantum unique ergodicity","volume":"350","author":"Bourgade Paul","year":"2017","unstructured":"Paul Bourgade and H.-T. Yau. 2017. The eigenvector moment flow and local quantum unique ergodicity. Communications in Mathematical Physics 350, 1 (2017), 231\u2013278.","journal-title":"Communications in Mathematical Physics"},{"key":"e_1_3_2_15_2","first-page":"7950","article-title":"Covariance-aware private mean estimation without private covariance estimation","volume":"34","author":"Brown Gavin","year":"2021","unstructured":"Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. 2021. Covariance-aware private mean estimation without private covariance estimation. Advances in Neural Information Processing Systems 34 (2021), 7950\u20137964.","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"2","key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1093\/qmath\/hax047","article-title":"Gaps between zeros of the Riemann zeta-function","volume":"69","author":"Bui H. M.","year":"2018","unstructured":"H. M. Bui and M. B. Milinovich. 2018. Gaps between zeros of the Riemann zeta-function. Quarterly Journal of Mathematics 69, 2 (2018), 403\u2013423.","journal-title":"Quarterly Journal of Mathematics"},{"key":"e_1_3_2_17_2","first-page":"989","article-title":"Near-optimal differentially private principal components","volume":"25","author":"Chaudhuri Kamalika","year":"2012","unstructured":"Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha. 2012. Near-optimal differentially private principal components. Advances in Neural Information Processing Systems 25 (2012), 989\u2013997.","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"3","key":"e_1_3_2_18_2","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/s00220-024-04944-5","article-title":"The lower tail of q-pushTASEP","volume":"405","author":"Corwin Ivan","year":"2024","unstructured":"Ivan Corwin and Milind Hegde. 2024. The lower tail of q-pushTASEP. Communications in Mathematical Physics 405, 3 (2024), 64.","journal-title":"Communications in Mathematical Physics"},{"issue":"11","key":"e_1_3_2_19_2","first-page":"1","article-title":"Chaos, complexity, and random matrices","volume":"2017","author":"Cotler Jordan","year":"2017","unstructured":"Jordan Cotler, Nicholas Hunter-Jones, Junyu Liu, and Beni Yoshida. 2017. Chaos, complexity, and random matrices. Journal of High Energy Physics 2017, 11 (2017), 1\u201360.","journal-title":"Journal of High Energy Physics"},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719192","volume-title":"Lanczos Algorithms for Large Symmetric Eigenvalue Computations: Vol. I: Theory","author":"Cullum Jane K.","year":"2002","unstructured":"Jane K. Cullum and Ralph A. Willoughby. 2002. Lanczos Algorithms for Large Symmetric Eigenvalue Computations: Vol. I: Theory. SIAM."},{"issue":"4","key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1109\/JSTSP.2016.2539100","article-title":"An overview of low-rank matrix recovery from incomplete observations","volume":"10","author":"Davenport Mark A.","year":"2016","unstructured":"Mark A. Davenport and Justin Romberg. 2016. An overview of low-rank matrix recovery from incomplete observations. IEEE Journal of Selected Topics in Signal Processing 10, 4 (2016), 608\u2013622.","journal-title":"IEEE Journal of Selected Topics in Signal Processing"},{"issue":"1","key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0707001","article-title":"The rotation of eigenvectors by a perturbation. III","volume":"7","author":"Davis Chandler","year":"1970","unstructured":"Chandler Davis and William Morton Kahan. 1970. The rotation of eigenvectors by a perturbation. III. SIAM Journal on Numerical Analysis 7, 1 (1970), 1\u201346.","journal-title":"SIAM Journal on Numerical Analysis"},{"key":"e_1_3_2_23_2","first-page":"486","volume-title":"Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Dwork Cynthia","year":"2006","unstructured":"Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006. Our data, ourselves: Privacy via distributed noise generation. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques. 486\u2013503."},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/11681878_14","volume-title":"Proceedings of the Theory of Cryptography Conference","author":"Dwork Cynthia","year":"2006","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Theory of Cryptography Conference. 265\u2013284."},{"issue":"3","key":"e_1_3_2_25_2","first-page":"211","article-title":"The algorithmic foundations of differential privacy.","volume":"9","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork and Aaron Roth. 2014. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science 9, 3-4 (2014), 211\u2013407.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_3_2_26_2","first-page":"11","volume-title":"Proceedings of the 46th Annual ACM Symposium on Theory of Computing","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. 2014. Analyze Gauss: Optimal bounds for privacy-preserving principal component analysis. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing. 11\u201320."},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","DOI":"10.1063\/1.1704008","article-title":"Random matrices and the statistical theory of energy levels IV","volume":"4","author":"Dyson F. J.","year":"1963","unstructured":"F. J. Dyson and M. Lal Mehta. 1963. Random matrices and the statistical theory of energy levels IV. Journal of Mathematical Physics 4 (1963), 701\u201312.","journal-title":"Journal of Mathematical Physics"},{"issue":"6","key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"1191","DOI":"10.1063\/1.1703862","article-title":"A Brownian-motion model for the eigenvalues of a random matrix","volume":"3","author":"Dyson Freeman J.","year":"1962","unstructured":"Freeman J. Dyson. 1962. A Brownian-motion model for the eigenvalues of a random matrix. Journal of Mathematical Physics 3, 6 (1962), 1191\u20131198.","journal-title":"Journal of Mathematical Physics"},{"issue":"1","key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1063\/1.1703773","article-title":"Statistical theory of the energy levels of complex systems. I","volume":"3","author":"Dyson Freeman J.","year":"1962","unstructured":"Freeman J. Dyson. 1962. Statistical theory of the energy levels of complex systems. I. Journal of Mathematical Physics 3, 1 (1962), 140\u2013156.","journal-title":"Journal of Mathematical Physics"},{"issue":"1","key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s00222-010-0302-7","article-title":"Universality of random matrices and local relaxation flow","volume":"185","author":"Erd\u0151s L\u00e1szl\u00f3","year":"2011","unstructured":"L\u00e1szl\u00f3 Erd\u0151s, Benjamin Schlein, and Horng-Tzer Yau. 2011. Universality of random matrices and local relaxation flow. Inventiones Mathematicae 185, 1 (2011), 75\u2013119.","journal-title":"Inventiones Mathematicae"},{"issue":"3","key":"e_1_3_2_31_2","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1016\/j.aim.2011.12.010","article-title":"Rigidity of eigenvalues of generalized Wigner matrices","volume":"229","author":"Erd\u0151s L\u00e1szl\u00f3","year":"2012","unstructured":"L\u00e1szl\u00f3 Erd\u0151s, Horng-Tzer Yau, and Jun Yin. 2012. Rigidity of eigenvalues of generalized Wigner matrices. Advances in Mathematics 229, 3 (2012), 1435\u20131515.","journal-title":"Advances in Mathematics"},{"issue":"6","key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"1794","DOI":"10.1007\/s00039-019-00520-5","article-title":"Small gaps of GOE","volume":"29","author":"Feng Renjie","year":"2019","unstructured":"Renjie Feng, Gang Tian, and Dongyi Wei. 2019. Small gaps of GOE. Geometric and Functional Analysis 29, 6 (2019), 1794\u20131827.","journal-title":"Geometric and Functional Analysis"},{"key":"e_1_3_2_33_2","article-title":"Large gaps of CUE and GUE","author":"Feng Renjie","year":"2018","unstructured":"Renjie Feng and Dongyi Wei. 2018. Large gaps of CUE and GUE. arXiv preprint arXiv:1807.02149 (2018).","journal-title":"arXiv preprint arXiv:1807.02149"},{"issue":"5","key":"e_1_3_2_34_2","article-title":"Functional form for the leading correction to the distribution of the largest eigenvalue in the GUE and LUE","volume":"59","author":"Forrester Peter J.","year":"2018","unstructured":"Peter J. Forrester and Allan K. Trinh. 2018. Functional form for the leading correction to the distribution of the largest eigenvalue in the GUE and LUE. Journal of Mathematical Physics 59, 5 (2018).","journal-title":"Journal of Mathematical Physics"},{"key":"e_1_3_2_35_2","unstructured":"Nic Freeman. 2015. Ito Calculus and Complex Brownian Motion. Retrieved February 10 2025 from https:\/\/nicfreeman1209.github.io\/Website\/teaching_old\/cbm%20notes.pdf"},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"2063","DOI":"10.1109\/LSP.2021.3116525","article-title":"Order estimation via matrix completion for multi-switch antenna selection","volume":"28","author":"Garg Vaibhav","year":"2021","unstructured":"Vaibhav Garg, Alba Pages-Zamora, and Ignacio Santamaria. 2021. Order estimation via matrix completion for multi-switch antenna selection. IEEE Signal Processing Letters 28 (2021), 2063\u20132067.","journal-title":"IEEE Signal Processing Letters"},{"issue":"3","key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1063\/1.1704292","article-title":"Statistical ensembles of complex, quaternion, and real matrices","volume":"6","author":"Ginibre Jean","year":"1965","unstructured":"Jean Ginibre. 1965. Statistical ensembles of complex, quaternion, and real matrices. Journal of Mathematical Physics 6, 3 (1965), 440\u2013449.","journal-title":"Journal of Mathematical Physics"},{"issue":"1","key":"e_1_3_2_38_2","doi-asserted-by":"crossref","first-page":"011006","DOI":"10.1103\/PhysRevX.12.011006","article-title":"Probing symmetries of quantum many-body systems through gap ratio statistics","volume":"12","author":"Giraud Olivier","year":"2022","unstructured":"Olivier Giraud, Nicolas Mac\u00e9, \u00c9ric Vernier, and Fabien Alet. 2022. Probing symmetries of quantum many-body systems through gap ratio statistics. Physical Review X 12, 1 (2022), 011006.","journal-title":"Physical Review X"},{"issue":"4","key":"e_1_3_2_39_2","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1137\/1129095","article-title":"Circular law","volume":"29","author":"Girko Vyacheslav L.","year":"1985","unstructured":"Vyacheslav L. Girko. 1985. Circular law. Theory of Probability & Its Applications 29, 4 (1985), 694\u2013706.","journal-title":"Theory of Probability & Its Applications"},{"key":"e_1_3_2_40_2","first-page":"438","volume-title":"Proceedings of Algorithmic Learning Theory","author":"Gonen Alon","year":"2018","unstructured":"Alon Gonen and Ram Gilad-Bachrach. 2018. Smooth sensitivity based approach for differentially private PCA. Proceedings of Algorithmic Learning Theory 83 (2018), 438\u2013450."},{"issue":"4","key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0370-1573(97)00088-4","article-title":"Random-matrix theories in quantum physics: Common concepts","volume":"299","author":"Guhr Thomas","year":"1998","unstructured":"Thomas Guhr, Axel M\u00fcller-Groeling, and Hans A. Weidenm\u00fcller. 1998. Random-matrix theories in quantum physics: Common concepts. Physics Reports 299, 4-6 (1998), 189\u2013425.","journal-title":"Physics Reports"},{"issue":"3","key":"e_1_3_2_42_2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1177\/1475921713481015","article-title":"Principal component analysis and perturbation theory\u2013based robust damage detection of multifunctional aircraft structure","volume":"12","author":"Hajrya Rafik","year":"2013","unstructured":"Rafik Hajrya and Nazih Mechbal. 2013. Principal component analysis and perturbation theory\u2013based robust damage detection of multifunctional aircraft structure. Structural Health Monitoring 12, 3 (2013), 263\u2013277.","journal-title":"Structural Health Monitoring"},{"issue":"7","key":"e_1_3_2_43_2","doi-asserted-by":"crossref","first-page":"3811","DOI":"10.1109\/TGRS.2016.2528298","article-title":"Estimating the intrinsic dimension of hyperspectral images using a noise-whitened eigengap approach","volume":"54","author":"Halimi Abderrahim","year":"2016","unstructured":"Abderrahim Halimi, Paul Honeine, Malika Kharouf, C\u00e9dric Richard, and Jean-Yves Tourneret. 2016. Estimating the intrinsic dimension of hyperspectral images using a noise-whitened eigengap approach. IEEE Transactions on Geoscience and Remote Sensing 54, 7 (2016), 3811\u20133821.","journal-title":"IEEE Transactions on Geoscience and Remote Sensing"},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1109\/FOCS.2014.75","volume-title":"Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science","author":"Hardt Moritz","year":"2014","unstructured":"Moritz Hardt. 2014. Understanding alternating minimization for matrix completion. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, 651\u2013660."},{"key":"e_1_3_2_45_2","first-page":"1255","volume-title":"Proceedings of the 44th Annual ACM Symposium on Theory of Computing","author":"Hardt Moritz","year":"2012","unstructured":"Moritz Hardt and Aaron Roth. 2012. Beating randomized response on incoherent matrices. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing. 1255\u20131268."},{"key":"e_1_3_2_46_2","first-page":"331","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing","author":"Hardt Moritz","year":"2013","unstructured":"Moritz Hardt and Aaron Roth. 2013. Beyond worst-case analysis in private singular vector computation. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 331\u2013340."},{"issue":"4","key":"e_1_3_2_47_2","first-page":"66","article-title":"Collision or non-collision problem for interacting Brownian particles","volume":"82","author":"Inukai Kiyokazu","year":"2006","unstructured":"Kiyokazu Inukai. 2006. Collision or non-collision problem for interacting Brownian particles. Proceedings of the Japan Academy, Series A, Mathematical Sciences 82, 4 (2006), 66\u201370.","journal-title":"Proceedings of the Japan Academy, Series A, Mathematical Sciences"},{"key":"e_1_3_2_48_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-7138-7","volume-title":"An Introduction to Statistical Learning","author":"James Gareth","year":"2013","unstructured":"Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. 2013. An Introduction to Statistical Learning. Vol. 112. Springer."},{"key":"e_1_3_2_49_2","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1007\/s002200000328","article-title":"Universality of the local spacing distribution in certain ensembles of Hermitian Wigner matrices","volume":"215","author":"Johansson Kurt","year":"2001","unstructured":"Kurt Johansson. 2001. Universality of the local spacing distribution in certain ensembles of Hermitian Wigner matrices. Communications in Mathematical Physics 215 (2001), 683\u2013705.","journal-title":"Communications in Mathematical Physics"},{"key":"e_1_3_2_50_2","article-title":"Random matrices and determinantal processes","author":"Johansson Kurt","year":"2005","unstructured":"Kurt Johansson. 2005. Random matrices and determinantal processes. arXiv preprint math-ph\/0510038 (2005).","journal-title":"arXiv preprint math-ph\/0510038"},{"key":"e_1_3_2_51_2","first-page":"111","article-title":"Choosing a subset of principal components or variables","author":"Jolliffe Ian T.","year":"2002","unstructured":"Ian T. Jolliffe. 2002. Choosing a subset of principal components or variables. In Principal Component Analysis (2nd ed). Springer Series in Statistics. Springer, 111\u2013149.","journal-title":"Principal Component Analysis"},{"key":"e_1_3_2_52_2","first-page":"1395","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Kapralov Michael","year":"2013","unstructured":"Michael Kapralov and Kunal Talwar. 2013. On differentially private low rank approximation. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms. 1395\u20131414."},{"key":"e_1_3_2_53_2","volume-title":"Brownian Motion and Stochastic Calculus","author":"Karatzas Ioannis","year":"1991","unstructured":"Ioannis Karatzas and Steven Shreve. 1991. Brownian Motion and Stochastic Calculus. Springer."},{"key":"e_1_3_2_54_2","volume-title":"Random Matrix Theory in Numerical Linear Algebra","author":"Kulkarni Archit U.","year":"2020","unstructured":"Archit U. Kulkarni. 2020. Random Matrix Theory in Numerical Linear Algebra. University of California, Berkeley."},{"key":"e_1_3_2_55_2","article-title":"Singular subspace perturbation bounds via rectangular random matrix diffusions","author":"Lai Peiyao","year":"2024","unstructured":"Peiyao Lai and Oren Mangoubi. 2024. Singular subspace perturbation bounds via rectangular random matrix diffusions. arXiv preprint arXiv:2406.02502 (2024).","journal-title":"arXiv preprint arXiv:2406.02502"},{"issue":"3","key":"e_1_3_2_56_2","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1007\/s00220-017-2955-1","article-title":"Convergence of local statistics of Dyson Brownian motion","volume":"355","author":"Landon Benjamin","year":"2017","unstructured":"Benjamin Landon and Horng-Tzer Yau. 2017. Convergence of local statistics of Dyson Brownian motion. Communications in Mathematical Physics 355, 3 (2017), 949\u20131000.","journal-title":"Communications in Mathematical Physics"},{"key":"e_1_3_2_57_2","article-title":"Stochastic Calculus: An Introduction with Applications","author":"Lawler Gregory F.","year":"2010","unstructured":"Gregory F. Lawler. 2010. Stochastic Calculus: An Introduction with Applications. American Mathematical Society.","journal-title":"American Mathematical Society."},{"key":"e_1_3_2_58_2","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC \u201921)","author":"Leake Jonathan","year":"2021","unstructured":"Jonathan Leake, Colin S. McSwiggen, and Nisheeth K. Vishnoi. 2021. A polynomial-time algorithm and applications for matrix sampling from Harish-Chandra\u2013Itzykson-Zuber densities. In Proceedings of the ACM Symposium on Theory of Computing (STOC \u201921)."},{"issue":"3","key":"e_1_3_2_59_2","first-page":"2349","article-title":"Bulk universality for deformed Wigner matrices","volume":"44","author":"Lee Ji Oon","year":"2016","unstructured":"Ji Oon Lee, Kevin Schnelli, Ben Stetler, and Horng-Tzer Yau. 2016. Bulk universality for deformed Wigner matrices. Annals of Probability 44, 3 (2016), 2349\u20132425.","journal-title":"Annals of Probability"},{"key":"e_1_3_2_60_2","first-page":"38585","volume-title":"Advances in Neural Information Processing Systems","author":"Mangoubi Oren","year":"2022","unstructured":"Oren Mangoubi and Nisheeth Vishnoi. 2022. Re-analyze Gauss: Bounds for private matrix approximation via Dyson Brownian motion. In Advances in Neural Information Processing Systems 35 (2022), 38585\u201338599."},{"key":"e_1_3_2_61_2","unstructured":"Oren Mangoubi and Nisheeth K. Vishnoi. 2023. Private covariance approximation and eigenvalue-gap bounds for complex Gaussian perturbations. In Proceedings of the Thirty-Sixth Conference on Learning Theory Gergely Neu and Lorenzo Rosasco (Eds.). Proceedings of Machine Learning Research Vol. 195. PMLR 1522\u20131587. https:\/\/proceedings.mlr.press\/v195\/mangoubi23a.html"},{"key":"e_1_3_2_62_2","first-page":"3547","volume-title":"Proceedings of the Conference on Learning Theory","author":"Mangoubi Oren","year":"2022","unstructured":"Oren Mangoubi, Yikai Wu, Satyen Kale, Abhradeep Thakurta, and Nisheeth K. Vishnoi. 2022. Private matrix approximation and geometry of unitary orbits. In Proceedings of the Conference on Learning Theory. 3547\u20133588."},{"key":"e_1_3_2_63_2","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1137\/1.9781611977912.32","volume-title":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201924)","author":"Meyer Raphael","year":"2024","unstructured":"Raphael Meyer, Cameron Musco, and Christopher Musco. 2024. On the unreasonable effectiveness of single vector Krylov methods for low-rank approximation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201924). 811\u2013845."},{"key":"e_1_3_2_64_2","doi-asserted-by":"crossref","unstructured":"Hugh L. Montgomery. 1973. The pair correlation of zeros of the zeta function. In Proceedings of Symposia in Pure Mathematics Vol. 24. 181\u2013193.","DOI":"10.1090\/pspum\/024\/9944"},{"key":"e_1_3_2_65_2","volume-title":"Brownian Motion","author":"M\u00f6rters Peter","year":"2010","unstructured":"Peter M\u00f6rters and Yuval Peres. 2010. Brownian Motion. Vol. 30. Cambridge University Press."},{"issue":"3","key":"e_1_3_2_66_2","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1007\/s00440-016-0693-5","article-title":"Random matrices: Tail bounds for gaps between eigenvalues","volume":"167","author":"Nguyen Hoi","year":"2017","unstructured":"Hoi Nguyen, Terence Tao, and Van Vu. 2017. Random matrices: Tail bounds for gaps between eigenvalues. Probability Theory and Related Fields 167, 3 (2017), 777\u2013816.","journal-title":"Probability Theory and Related Fields"},{"key":"e_1_3_2_67_2","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.laa.2017.11.014","article-title":"Random perturbation of low rank matrices: Improving classical bounds","volume":"540","author":"O\u2019Rourke Sean","year":"2018","unstructured":"Sean O\u2019Rourke, Van Vu, and Ke Wang. 2018. Random perturbation of low rank matrices: Improving classical bounds. Linear Algebra and Its Application 540 (2018), 26\u201359.","journal-title":"Linear Algebra and Its Application"},{"key":"e_1_3_2_68_2","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1137\/1.9781611976465.31","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA \u201921)","author":"Peng Richard","year":"2021","unstructured":"Richard Peng and Santosh Vempala. 2021. Solving sparse linear systems faster than matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA \u201921). 504\u2013521."},{"issue":"2","key":"e_1_3_2_69_2","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1137\/S089547980342204X","article-title":"Eigenvalues and condition numbers of complex random matrices","volume":"26","author":"Ratnarajah Tharmalingam","year":"2004","unstructured":"Tharmalingam Ratnarajah, R\u00e9mi Vaillancourt, and M. Alvo. 2004. Eigenvalues and condition numbers of complex random matrices. SIAM Journal on Matrix Analysis and Applications 26, 2 (2004), 441\u2013456.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"e_1_3_2_70_2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.chemolab.2013.10.012","article-title":"On the calibration of sensor arrays for pattern recognition using the minimal number of experiments","volume":"130","author":"Rodriguez-Lujan Irene","year":"2014","unstructured":"Irene Rodriguez-Lujan, Jordi Fonollosa, Alexander Vergara, Margie Homer, and Ramon Huerta. 2014. On the calibration of sensor arrays for pattern recognition using the minimal number of experiments. Chemometrics and Intelligent Laboratory Systems 130 (2014), 123\u2013134.","journal-title":"Chemometrics and Intelligent Laboratory Systems"},{"issue":"4","key":"e_1_3_2_71_2","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/BF01196734","article-title":"Interacting Brownian particles and the Wigner law","volume":"95","author":"Rogers Leonard C. G.","year":"1993","unstructured":"Leonard C. G. Rogers and Zhan Shi. 1993. Interacting Brownian particles and the Wigner law. Probability Theory and Related Fields 95, 4 (1993), 555\u2013570.","journal-title":"Probability Theory and Related Fields"},{"issue":"2","key":"e_1_3_2_72_2","first-page":"269","article-title":"Zeros of principal L-functions and random matrix theory","volume":"81","author":"Rudnick Ze\u00e9v","year":"1996","unstructured":"Ze\u00e9v Rudnick and Peter Sarnak. 1996. Zeros of principal L-functions and random matrix theory. Duke Mathematical Journal 81, 2 (1996), 269\u2013322.","journal-title":"Duke Mathematical Journal"},{"key":"e_1_3_2_73_2","first-page":"789","volume-title":"Algorithmic Learning Theory","author":"Sheffet Or","year":"2019","unstructured":"Or Sheffet. 2019. Old techniques in differentially private linear regression. In Algorithmic Learning Theory. PMLR, 789\u2013827."},{"key":"e_1_3_2_74_2","volume-title":"Topics in Random Matrix Theory","author":"Tao Terence","year":"2012","unstructured":"Terence Tao. 2012. Topics in Random Matrix Theory. Vol. 132. American Mathematical Society."},{"issue":"1","key":"e_1_3_2_75_2","first-page":"81","article-title":"The asymptotic distribution of a single eigenvalue gap of a Wigner matrix","volume":"157","author":"Tao Terence","year":"2013","unstructured":"Terence Tao. 2013. The asymptotic distribution of a single eigenvalue gap of a Wigner matrix. Probability Theory and Related Fields 157, 1 (2013), 81\u2013106.","journal-title":"Probability Theory and Related Fields"},{"key":"e_1_3_2_76_2","article-title":"The price of privacy for low-rank factorization","volume":"31","author":"Upadhyay Jalaj","year":"2018","unstructured":"Jalaj Upadhyay. 2018. The price of privacy for low-rank factorization. Advances in Neural Information Processing Systems 31 (2018), 1\u201312.","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"7","key":"e_1_3_2_77_2","doi-asserted-by":"crossref","first-page":"3709","DOI":"10.1090\/S0002-9947-2014-05974-6","article-title":"Random Schr\u00f6dinger operators on long boxes, noise explosion and the GOE","volume":"366","author":"Valk\u00f3 Benedek","year":"2014","unstructured":"Benedek Valk\u00f3 and B\u00e1lint Vir\u00e1g. 2014. Random Schr\u00f6dinger operators on long boxes, noise explosion and the GOE. Transactions of the American Mathematical Society 366, 7 (2014), 3709\u20133728.","journal-title":"Transactions of the American Mathematical Society"},{"key":"e_1_3_2_78_2","volume-title":"High-Dimensional Probability: An Introduction with Applications in Data Science","author":"Vershynin Roman","year":"2018","unstructured":"Roman Vershynin. 2018. High-Dimensional Probability: An Introduction with Applications in Data Science. Vol. 47. Cambridge University Press."},{"key":"e_1_3_2_79_2","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","volume":"17","author":"Luxburg Ulrike Von","year":"2007","unstructured":"Ulrike Von Luxburg. 2007. A tutorial on spectral clustering. Statistics and Computing 17 (2007), 395\u2013416.","journal-title":"Statistics and Computing"},{"key":"e_1_3_2_80_2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01932678","article-title":"Perturbation bounds in connection with singular value decomposition","volume":"12","author":"Wedin Per-\u00c5ke","year":"1972","unstructured":"Per-\u00c5ke Wedin. 1972. Perturbation bounds in connection with singular value decomposition. BIT Numerical Mathematics 12 (1972), 99\u2013111.","journal-title":"BIT Numerical Mathematics"},{"issue":"3","key":"e_1_3_2_81_2","doi-asserted-by":"crossref","first-page":"548","DOI":"10.2307\/1970079","article-title":"Characteristic vectors of bordered matrices with infinite dimensions","volume":"62","author":"Wigner Eugene P.","year":"1955","unstructured":"Eugene P. Wigner. 1955. Characteristic vectors of bordered matrices with infinite dimensions. Annals of Mathematics 62, 3 (1955), 548.","journal-title":"Annals of Mathematics"},{"key":"e_1_3_2_82_2","article-title":"Gatlinberg Conference on Neutron Physics","author":"Wigner Eugene P.","year":"1956","unstructured":"Eugene P. Wigner. 1956. Gatlinberg Conference on Neutron Physics. Technical Report. Oak Ridge National Laboratory.","journal-title":"Oak Ridge National Laboratory."},{"issue":"2","key":"e_1_3_2_83_2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1093\/biomet\/asv008","article-title":"A useful variant of the Davis\u2013Kahan theorem for statisticians","volume":"102","author":"Yu Yi","year":"2015","unstructured":"Yi Yu, Tengyao Wang, and Richard J. Samworth. 2015. A useful variant of the Davis\u2013Kahan theorem for statisticians. Biometrika 102, 2 (2015), 315\u2013323.","journal-title":"Biometrika"},{"issue":"2","key":"e_1_3_2_84_2","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1007\/s11336-020-09704-7","article-title":"A note on exploratory item factor analysis by singular value decomposition","volume":"85","author":"Zhang Haoran","year":"2020","unstructured":"Haoran Zhang, Yunxiao Chen, and Xiaoou Li. 2020. A note on exploratory item factor analysis by singular value decomposition. Psychometrika 85, 2 (2020), 358\u2013372.","journal-title":"Psychometrika"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3716496","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3716496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:10Z","timestamp":1750295950000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3716496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,27]]},"references-count":83,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3716496"],"URL":"https:\/\/doi.org\/10.1145\/3716496","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2025,3,27]]},"assertion":[{"value":"2023-09-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-27","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}