{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T07:22:49Z","timestamp":1791444169711,"version":"4.3.3"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,8,4]],"date-time":"2017-08-04T00:00:00Z","timestamp":1501804800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,8,4]]},"DOI":"10.1145\/3097983.3098050","type":"proceedings-article","created":{"date-parts":[[2017,8,4]],"date-time":"2017-08-04T18:35:54Z","timestamp":1501871754000},"page":"615-623","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Randomization or Condensation?"],"prefix":"10.1145","author":[{"given":"Kai","family":"Zhang","sequence":"first","affiliation":[{"name":"Temple University, Philadelphia, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chuanren","family":"Liu","sequence":"additional","affiliation":[{"name":"Drexel University, Philadelphia, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jie","family":"Zhang","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hui","family":"Xiong","sequence":"additional","affiliation":[{"name":"Rutgers University, Newark, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric","family":"Xing","sequence":"additional","affiliation":[{"name":"Carneigie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jieping","family":"Ye","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, Ann Arbor, MI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,8,4]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.97.18.10101"},{"key":"e_1_3_2_2_2_1","volume-title":"Positive Definite Matrices","author":"Bhatia R.","unstructured":"R. Bhatia . 2015. Positive Definite Matrices . Princeton University Press . R. Bhatia. 2015. Positive Definite Matrices. Princeton University Press."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/12086755X"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/120874540"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591819"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"e_1_3_2_2_7_1","volume-title":"The Fast Cauchy Transform and Faster Robust Linear Regression Annual ACM-SIAM Symposium on Discrete Algorithms. 466--477","author":"Clarkson K.L.","unstructured":"K.L. Clarkson , P. Drineas , M. Magdon-Ismail , M.W. Mahoney , X. Meng , and D.P. Woodruff . 2013 . The Fast Cauchy Transform and Faster Robust Linear Regression Annual ACM-SIAM Symposium on Discrete Algorithms. 466--477 . K.L. Clarkson, P. Drineas, M. Magdon-Ismail, M.W. Mahoney, X. Meng, and D.P. Woodruff. 2013. The Fast Cauchy Transform and Faster Robust Linear Regression Annual ACM-SIAM Symposium on Discrete Algorithms. 466--477."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"crossref","unstructured":"K.L. Clarkson and D.P. Woodruff 2013. Low rank approximation and regression in input sparsity time Annual ACM Symposium on theory of computing.  K.L. Clarkson and D.P. Woodruff 2013. Low rank approximation and regression in input sparsity time Annual ACM Symposium on theory of computing.","DOI":"10.1145\/2488608.2488620"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4571(199009)41:6%3C391::AID-ASI1%3E3.0.CO;2-9"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442696"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2503308.2503352"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1046920.1194916"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262185"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"e_1_3_2_2_15_1","volume-title":"Matrix Computation","author":"Golub G. H.","unstructured":"G. H. Golub and C. F. Van Loan 1996. Matrix Computation . Johns Hopkins University Press . G. H. Golub and C. F. Van Loan 1996. Matrix Computation. Johns Hopkins University Press."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(96)00301-1"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"e_1_3_2_2_18_1","first-page":"981","article-title":"Sampling methods for the Nystr\u00f6m method","volume":"13","author":"Kumar S.","year":"2012","unstructured":"S. Kumar , M. Mohri , and A. Talwalkar 2012 . Sampling methods for the Nystr\u00f6m method . Journal of Machine Learning Research Vol. 13 , 1 (2012), 981 -- 1006 . S. Kumar, M. Mohri, and A. Talwalkar 2012. Sampling methods for the Nystr\u00f6m method. Journal of Machine Learning Research Vol. 13, 1 (2012), 981--1006.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2017.05.001"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1038\/44565"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487623"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0709640104"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1980.1094577"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0803205106"},{"key":"e_1_3_2_2_26_1","unstructured":"I. Mitliagkas C. Caramanis and P. Jain. 2013. Memory limited streaming PCA. In Advances in Neural Information Processing Systems. 2886--2894.  I. Mitliagkas C. Caramanis and P. Jain. 2013. Memory limited streaming PCA. In Advances in Neural Information Processing Systems. 2886--2894."},{"key":"e_1_3_2_2_27_1","volume-title":"Nguy\u00ean","author":"Nelson J.","year":"2015","unstructured":"J. Nelson and H. L. Nguy\u00ean 2015 . OSNAP : Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings IEEE Annual Symposium on Foundations of Computer Science (FOCS) . 135--143. J. Nelson and H.L. Nguy\u00ean 2015. OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings IEEE Annual Symposium on Foundations of Computer Science (FOCS). 135--143."},{"key":"e_1_3_2_2_28_1","first-page":"647","article-title":"A Scalable CUR Matrix Decomposition Algorithm","volume":"25","author":"Wang S.","year":"2012","unstructured":"S. Wang and Z. Zhang . 2012 . A Scalable CUR Matrix Decomposition Algorithm : Lower Time Complexity and Tighter Bound. Advances in Neural Information Processing Systems 25. 647 -- 655 . S. Wang and Z. Zhang. 2012. A Scalable CUR Matrix Decomposition Algorithm: Lower Time Complexity and Tighter Bound. Advances in Neural Information Processing Systems 25. 647--655.","journal-title":"Lower Time Complexity and Tighter Bound. Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_2_29_1","first-page":"1","article-title":"Towards More Efficient Nystrom Approximation and CUR Matrix Decomposition","volume":"17","author":"Wang S.","year":"2016","unstructured":"S. Wang , Z. Zhang , and T. Zhang . 2016 . Towards More Efficient Nystrom Approximation and CUR Matrix Decomposition . Journal of Machine Learning Research 17 (2016), 1 -- 49 . S. Wang, Z. Zhang, and T. Zhang. 2016. Towards More Efficient Nystrom Approximation and CUR Matrix Decomposition. Journal of Machine Learning Research 17 (2016), 1--49.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_2_30_1","unstructured":"C.K. I. Williams and M. Seeger 2001. Using the Nystrom Method to Speed Up Kernel Machines Advances in Neural Information Processing Systems 13. 682--688.  C.K. I. Williams and M. Seeger 2001. Using the Nystrom Method to Speed Up Kernel Machines Advances in Neural Information Processing Systems 13. 682--688."},{"key":"e_1_3_2_2_31_1","first-page":"3177","volume":"28","author":"Yun S.","year":"2015","unstructured":"S. Yun , M. lelarge, and A. Proutiere 2015 . Fast and Memory Optimal Low-Rank Matrix Approximation. Advances in Neural Information Processing Systems 28. 3177 -- 3185 . S. Yun, M. lelarge, and A. Proutiere 2015. Fast and Memory Optimal Low-Rank Matrix Approximation. Advances in Neural Information Processing Systems 28. 3177--3185.","journal-title":"Fast and Memory Optimal Low-Rank Matrix Approximation. Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_2_32_1","unstructured":"H. Zha C. Ding M. Gu X. He and H. Simon 2002. Spectral relaxation for K-means clustering.. In Neural Information Processing Systems 14.  H. Zha C. Ding M. Gu X. He and H. Simon 2002. Spectral relaxation for K-means clustering.. In Neural Information Processing Systems 14."},{"key":"e_1_3_2_2_33_1","volume-title":"Limited Resources: A Low-rank Linearization Approach Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research)","author":"Zhang K.","year":"2012","unstructured":"K. Zhang , L. Lan , Z. Wang , and F. Moerchen . 2012 . Scaling up Kernel SVM on Limited Resources: A Low-rank Linearization Approach Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research) , Vol. Vol. 22 . 1425--1434. K. Zhang, L. Lan, Z. Wang, and F. Moerchen. 2012. Scaling up Kernel SVM on Limited Resources: A Low-rank Linearization Approach Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research), Vol. Vol. 22. 1425--1434."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"crossref","unstructured":"K. Zhang I. Tsang and J. Kwok 2008. Improved Nystr\u00f6m low-rank approximation and error analysis International conference on Machine learning. 1232--1239.  K. Zhang I. Tsang and J. Kwok 2008. Improved Nystr\u00f6m low-rank approximation and error analysis International conference on Machine learning. 1232--1239.","DOI":"10.1145\/1390156.1390311"},{"key":"e_1_3_2_2_35_1","volume-title":"Godec: Randomized low-rank & sparse matrix decomposition in noisy case (2011) International Conference on Machine Learning.","author":"Zhou T.","year":"2011","unstructured":"T. Zhou and D. Tao . 2011 . Godec: Randomized low-rank & sparse matrix decomposition in noisy case (2011) International Conference on Machine Learning. T. Zhou and D. Tao. 2011. Godec: Randomized low-rank & sparse matrix decomposition in noisy case (2011) International Conference on Machine Learning."}],"event":{"name":"KDD '17: The 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","location":"Halifax NS Canada","acronym":"KDD '17","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3097983.3098050","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3097983.3098050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:25Z","timestamp":1750217425000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3097983.3098050"}},"subtitle":["Linear-Cost Matrix Sketching Via Cascaded Compression Sampling"],"short-title":[],"issued":{"date-parts":[[2017,8,4]]},"references-count":35,"alternative-id":["10.1145\/3097983.3098050","10.1145\/3097983"],"URL":"https:\/\/doi.org\/10.1145\/3097983.3098050","relation":{},"subject":[],"published":{"date-parts":[[2017,8,4]]},"assertion":[{"value":"2017-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}