{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:49:34Z","timestamp":1763459374058,"version":"3.45.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,11,19]],"date-time":"2017-11-19T00:00:00Z","timestamp":1511049600000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1409543"],"award-info":[{"award-number":["1409543"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2017,5,31]]},"abstract":"\n Computation of covariance matrices from observed data is an important problem, as such matrices are used in applications such as principal component analysis (PCA), linear discriminant analysis (LDA), and increasingly in the learning and application of probabilistic graphical models. However, computing an empirical covariance matrix is not always an easy problem. There are two key difficulties associated with computing such a matrix from a very high-dimensional dataset. The first problem is over-fitting. For a\n p<\/jats:italic>\n -dimensional covariance matrix, there are\n p<\/jats:italic>\n (\n p<\/jats:italic>\n \u2212 1)\/2 unique, off-diagonal entries in the empirical covariance matrix \u015c for large\n p<\/jats:italic>\n (say,\n p<\/jats:italic>\n > 10\n 5<\/jats:sup>\n ), the size\n n<\/jats:italic>\n of the dataset is often much smaller than the number of covariances to compute. Over-fitting is a concern in any situation in which the number of parameters learned can greatly exceed the size of the dataset. Thus, there are strong theoretical reasons to expect that for high-dimensional data\u2014even Gaussian data\u2014the empirical covariance matrix is not a good estimate for the true covariance matrix underlying the generative process. The second problem is computational. Computing a covariance matrix takes\n O<\/jats:italic>\n (\n np<\/jats:italic>\n 2<\/jats:sup>\n ) time. For large\n p<\/jats:italic>\n (greater than 10,000) and\n n<\/jats:italic>\n much greater than\n p<\/jats:italic>\n , this is debilitating. In this article, we consider how both of these difficulties can be handled simultaneously. Specifically, a key regularization technique for high-dimensional covariance estimation is\n thresholding<\/jats:italic>\n , in which the smallest or least significant entries in the covariance matrix are simply dropped and replaced with the value 0. This suggests an obvious way to address the computational difficulty as well: First, compute the identities of the\n K<\/jats:italic>\n entries in the covariance matrix that are actually important in the sense that they will not be removed during thresholding, and then in a second step, compute the values of those entries. This can be done in\n O<\/jats:italic>\n (\n Kn<\/jats:italic>\n ) time. If\n K<\/jats:italic>\n \u226a\n p<\/jats:italic>\n 2<\/jats:sup>\n and the identities of the important entries can be computed in reasonable time, then this is a big win. The key technical contribution of this article is the design and implementation of two different distributed algorithms for approximating the identities of the important entries quickly, using sampling. We have implemented these methods and tested them using an 800-core compute cluster. Experiments have been run using real datasets having millions of data points and up to 40, 000 dimensions. These experiments show that the proposed methods are both accurate and efficient.\n <\/jats:p>","DOI":"10.1145\/2935750","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T09:01:46Z","timestamp":1479718906000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Distributed Algorithms for Computing Very Large Thresholded Covariance Matrices"],"prefix":"10.1145","volume":"11","author":[{"given":"Zekai J.","family":"Gao","sequence":"first","affiliation":[{"name":"Rice University, Houston, TX"}]},{"given":"Chris","family":"Jermaine","sequence":"additional","affiliation":[{"name":"Rice University, Houston, TX"}]}],"member":"320","published-online":{"date-parts":[[2016,11,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1214\/08-AOS600"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053607000000758"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2011.tm10560"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2011.tm10155"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276343"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.908981"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100028334"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/972450.972454"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jeconom.2008.09.017"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS944"},{"key":"e_1_2_1_12_1","first-page":"507","article-title":"Frequency distribution of the values of the correlation coefficient in samples from an indefinitely large population","volume":"10","author":"Fisher Ronald A.","year":"1915","unstructured":"Ronald A. Fisher and others. 1915. Frequency distribution of the values of the correlation coefficient in samples from an indefinitely large population. Biometrika 10, 4 (1915), 507--521.","journal-title":"Biometrika"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1989.10478752"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmva.2006.08.003"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/846219.847312"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/330577"},{"key":"e_1_2_1_17_1","volume-title":"Retaining positive definiteness in thresholded matrices. Linear Algebra and its Applications 436, 11","author":"Guillot Dominique","year":"2012","unstructured":"Dominique Guillot and Bala Rajaratnam. 2012. Retaining positive definiteness in thresholded matrices. Linear Algebra and its Applications 436, 11 (2012), 4143--4160."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/141484.130335"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999792.2999965"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2986459.2986719"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/93.1.85"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007641"},{"volume-title":"Linear Discriminant Analysis","author":"Izenman Alan Julian","key":"e_1_2_1_23_1","unstructured":"Alan Julian Izenman. 2008. Linear Discriminant Analysis. Springer."},{"key":"e_1_2_1_24_1","volume-title":"Covariance selection by thresholding the sample correlation matrix. Statistics 8 Probability Letters 83, 11","author":"Jiang Binyan","year":"2013","unstructured":"Binyan Jiang. 2013. Covariance selection by thresholding the sample correlation matrix. Statistics 8 Probability Letters 83, 11 (2013), 2492--2498."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1009210544"},{"volume-title":"Principal Component Analysis","author":"Jolliffe Ian","key":"e_1_2_1_26_1","unstructured":"Ian Jolliffe. 2005. Principal Component Analysis. Wiley Online Library."},{"key":"e_1_2_1_27_1","volume-title":"James Laurie Snell, and others","author":"Kindermann Ross","year":"1980","unstructured":"Ross Kindermann, James Laurie Snell, and others. 1980. Markov Random Fields and Their Applications, Vol. 1. American Mathematical Society Providence, RI."},{"key":"e_1_2_1_28_1","volume-title":"Xing","author":"Kolar Mladen","year":"2012","unstructured":"Mladen Kolar and Eric P. Xing. 2012. Consistent covariance selection from data with missing values. In Proceedings of ICML."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1795555"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/09-AOS720"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2501100"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOAS139"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.93611"},{"key":"e_1_2_1_34_1","first-page":"457","article-title":"Distribution of eigenvalues for some sets of random matrices. Sbornik","volume":"1","author":"Mar\u010denko Vladimir A.","year":"1967","unstructured":"Vladimir A. Mar\u010denko and Leonid Andreevich Pastur. 1967. Distribution of eigenvalues for some sets of random matrices. Sbornik: Mathematics 1, 4 (1967), 457--483.","journal-title":"Mathematics"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999134.2999219"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402748"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999134.2999310"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2009.0101"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1198\/016214508000000021"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/3008751.3008847"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.161"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2012.725386"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/asm018"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2935750","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2935750","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2935750","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:42:56Z","timestamp":1763458976000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2935750"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,19]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,5,31]]}},"alternative-id":["10.1145\/2935750"],"URL":"https:\/\/doi.org\/10.1145\/2935750","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2016,11,19]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}