{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T12:41:40Z","timestamp":1762087300712,"version":"build-2065373602"},"publisher-location":"New York, NY, USA","reference-count":64,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585100","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1802-1813","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["New Subset Selection Algorithms for Low Rank Approximation: Offline and Online"],"prefix":"10.1145","author":[{"given":"David P.","family":"Woodruff","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Taisuke","family":"Yasuda","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.86"},{"key":"e_1_3_2_1_2_1","volume-title":"Fast Randomized Kernel Ridge Regression with Statistical Guarantees. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015","author":"Alaoui Ahmed El","year":"2015","unstructured":"Ahmed El Alaoui and Michael W. Mahoney . 2015 . Fast Randomized Kernel Ridge Regression with Statistical Guarantees. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015 , December 7-12, 2015 , Montreal, Quebec, Canada. Neural Information Processing Systems Foundation, Inc. (NeurIPS), Canada. 775\u2013783. https:\/\/proceedings.neurips.cc\/paper\/ 2015\/hash\/f3f27a324736617f20abbf2ffd806f6d-Abstract.html Ahmed El Alaoui and Michael W. Mahoney. 2015. Fast Randomized Kernel Ridge Regression with Statistical Guarantees. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada. Neural Information Processing Systems Foundation, Inc. (NeurIPS), Canada. 775\u2013783. https:\/\/proceedings.neurips.cc\/paper\/2015\/hash\/f3f27a324736617f20abbf2ffd806f6d-Abstract.html"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the 33nd International Conference on Machine Learning, ICML","author":"Altschuler Jason M.","year":"2016","unstructured":"Jason M. Altschuler , Aditya Bhaskara , Gang Fu , Vahab S. Mirrokni , Afshin Rostamizadeh , and Morteza Zadimoghaddam . 2016. Greedy Column Subset Selection: New Bounds and Distributed Algorithms . In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016 , New York City, NY , USA, June 19-24, 2016, Maria-Florina Balcan and Kilian Q. Weinberger (Eds.) (JMLR Workshop and Conference Proceedings , Vol. 48). JMLR.org, USA. 2539\u2013 2548 . http:\/\/proceedings.mlr.press\/v48\/altschuler16.html Jason M. Altschuler, Aditya Bhaskara, Gang Fu, Vahab S. Mirrokni, Afshin Rostamizadeh, and Morteza Zadimoghaddam. 2016. Greedy Column Subset Selection: New Bounds and Distributed Algorithms. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, Maria-Florina Balcan and Kilian Q. Weinberger (Eds.) (JMLR Workshop and Conference Proceedings, Vol. 48). JMLR.org, USA. 2539\u20132548. http:\/\/proceedings.mlr.press\/v48\/altschuler16.html"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019","author":"Ban Frank","year":"2019","unstructured":"Frank Ban , Vijay Bhattiprolu , Karl Bringmann , Pavel Kolev , Euiwoong Lee , and David P. Woodruff . 2019. A PTAS for \u2113 _p-Low Rank Approximation . In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 , San Diego, California, USA , January 6-9, 2019 , Timothy M. Chan (Ed.). SIAM, USA. 747\u2013766. Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, and David P. Woodruff. 2019. A PTAS for \u2113 _p-Low Rank Approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, Timothy M. Chan (Ed.). SIAM, USA. 747\u2013766."},{"key":"e_1_3_2_1_6_1","volume-title":"Residual Based Sampling for Online Low Rank Approximation. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019","author":"Bhaskara Aditya","year":"2019","unstructured":"Aditya Bhaskara , Silvio Lattanzi , Sergei Vassilvitskii , and Morteza Zadimoghaddam . 2019 . Residual Based Sampling for Online Low Rank Approximation. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 , Baltimore, Maryland, USA , November 9-12, 2019, David Zuckerman (Ed.). IEEE Computer Society, USA. 1596\u20131614. Aditya Bhaskara, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghaddam. 2019. Residual Based Sampling for Online Low Rank Approximation. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, David Zuckerman (Ed.). IEEE Computer Society, USA. 1596\u20131614."},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning, ICML 2021","volume":"883","author":"Bhaskara Aditya","year":"2021","unstructured":"Aditya Bhaskara , Aravinda Kanchana Ruwanpathirana , and Maheshakya Wijewardena . 2021 . Additive Error Guarantees for Weighted Low Rank Approximation . In Proceedings of the 38th International Conference on Machine Learning, ICML 2021 , 18-24 July 2021, Virtual Event, Marina Meila and Tong Zhang (Eds.) (Proceedings of Machine Learning Research , Vol. 139). PMLR, USA. 874\u2013 883 . http:\/\/proceedings.mlr.press\/v139\/bhaskara21a.html Aditya Bhaskara, Aravinda Kanchana Ruwanpathirana, and Maheshakya Wijewardena. 2021. Additive Error Guarantees for Weighted Low Rank Approximation. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, Marina Meila and Tong Zhang (Eds.) (Proceedings of Machine Learning Research, Vol. 139). PMLR, USA. 874\u2013883. http:\/\/proceedings.mlr.press\/v139\/bhaskara21a.html"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/140977898"},{"key":"e_1_3_2_1_9_1","volume-title":"Near Optimal Linear Algebra in the Online and Sliding Window Models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020","author":"Braverman Vladimir","year":"2020","unstructured":"Vladimir Braverman , Petros Drineas , Cameron Musco , Christopher Musco , Jalaj Upadhyay , David P. Woodruff , and Samson Zhou . 2020 . Near Optimal Linear Algebra in the Online and Sliding Window Models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 , Durham, NC, USA , November 16-19, 2020. IEEE, USA. 517\u2013528. Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. 2020. Near Optimal Linear Algebra in the Online and Sliding Window Models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020. IEEE, USA. 517\u2013528."},{"key":"e_1_3_2_1_10_1","volume-title":"Online Active Regression. In International Conference on Machine Learning, ICML 2022","volume":"3335","author":"Chen Cheng","year":"2022","unstructured":"Cheng Chen , Yi Li , and Yiming Sun . 2022 . Online Active Regression. In International Conference on Machine Learning, ICML 2022 , 17-23 July 2022, Baltimore, Maryland, USA, Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesv\u00e1ri, Gang Niu, and Sivan Sabato (Eds.) (Proceedings of Machine Learning Research , Vol. 162). PMLR, USA. 3320\u2013 3335 . Cheng Chen, Yi Li, and Yiming Sun. 2022. Online Active Regression. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesv\u00e1ri, Gang Niu, and Sivan Sabato (Eds.) (Proceedings of Machine Learning Research, Vol. 162). PMLR, USA. 3320\u20133335."},{"key":"e_1_3_2_1_11_1","volume-title":"Conference on Learning Theory, COLT 2021","volume":"1179","author":"Chen Xue","year":"2021","unstructured":"Xue Chen and Michal Derezinski . 2021 . Query complexity of least absolute deviation regression via robust uniform convergence . In Conference on Learning Theory, COLT 2021 , 15-19 August 2021, Boulder, Colorado, USA, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research , Vol. 134). PMLR, USA. 1144\u2013 1179 . Xue Chen and Michal Derezinski. 2021. Query complexity of least absolute deviation regression via robust uniform convergence. In Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research, Vol. 134). PMLR, USA. 1144\u20131179."},{"key":"e_1_3_2_1_12_1","volume-title":"Conference on Learning Theory, COLT 2019","volume":"695","author":"Chen Xue","year":"2019","unstructured":"Xue Chen and Eric Price . 2019 . Active Regression via Linear-Sample Sparsification . In Conference on Learning Theory, COLT 2019 , 25-28 June 2019, Phoenix, AZ, USA, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research , Vol. 99). PMLR, USA. 663\u2013 695 . Xue Chen and Eric Price. 2019. Active Regression via Linear-Sample Sparsification. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research, Vol. 99). PMLR, USA. 663\u2013695."},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017","author":"Chierichetti Flavio","year":"2017","unstructured":"Flavio Chierichetti , Sreenivas Gollapudi , Ravi Kumar , Silvio Lattanzi , Rina Panigrahy , and David P. Woodruff . 2017. Algorithms for \u2113 _p Low-Rank Approximation . In Proceedings of the 34th International Conference on Machine Learning, ICML 2017 , Sydney, NSW, Australia , 6-11 August 2017 , Doina Precup and Yee Whye Teh (Eds.) (Proceedings of Machine Learning Research, Vol. 70). PMLR, Australia. 806\u2013814. Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, and David P. Woodruff. 2017. Algorithms for \u2113 _p Low-Rank Approximation. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, Doina Precup and Yee Whye Teh (Eds.) (Proceedings of Machine Learning Research, Vol. 70). PMLR, Australia. 806\u2013814."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070469"},{"key":"e_1_3_2_1_15_1","volume-title":"Input Sparsity and Hardness for Robust Subspace Approximation. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015","author":"Kenneth","year":"2015","unstructured":"Kenneth L. Clarkson and David P. Woodruff. 2015 . Input Sparsity and Hardness for Robust Subspace Approximation. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 , Berkeley, CA, USA , 17-20 October , 2015 , Venkatesan Guruswami (Ed.). IEEE Computer Society, USA. 310\u2013329. Kenneth L. Clarkson and David P. Woodruff. 2015. Input Sparsity and Hardness for Robust Subspace Approximation. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, Venkatesan Guruswami (Ed.). IEEE Computer Society, USA. 310\u2013329."},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015","author":"Kenneth","year":"2015","unstructured":"Kenneth L. Clarkson and David P. Woodruff. 2015. Sketching for M-Estimators: A Unified Approach to Robust Regression . In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 , San Diego, CA, USA , January 4-6, 2015 , Piotr Indyk (Ed.). SIAM, USA. 921\u2013939. Kenneth L. Clarkson and David P. Woodruff. 2015. Sketching for M-Estimators: A Unified Approach to Robust Regression. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, Piotr Indyk (Ed.). SIAM, USA. 921\u2013939."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039801"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a015"},{"key":"e_1_3_2_1_19_1","volume-title":"The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021","volume":"1134","author":"Cohen-Addad Vincent","year":"2021","unstructured":"Vincent Cohen-Addad , Benjamin Guedj , Varun Kanade , and Guy Rom . 2021 . Online k-means Clustering . In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021 , April 13-15, 2021, Virtual Event, Arindam Banerjee and Kenji Fukumizu (Eds.) (Proceedings of Machine Learning Research , Vol. 130). PMLR, Virtual. 1126\u2013 1134 . http:\/\/proceedings.mlr.press\/v130\/cohen-addad21a.html Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, and Guy Rom. 2021. Online k-means Clustering. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, Arindam Banerjee and Kenji Fukumizu (Eds.) (Proceedings of Machine Learning Research, Vol. 130). PMLR, Virtual. 1126\u20131134. http:\/\/proceedings.mlr.press\/v130\/cohen-addad21a.html"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519946"},{"key":"e_1_3_2_1_21_1","volume-title":"Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021","author":"Cohen-Addad Vincent","year":"2021","unstructured":"Vincent Cohen-Addad , David Saulpic , and Chris Schwiegelshohn . 2021 . Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021 , NeurIPS 2021, December 6-14, 2021, virtual, Marc\u2019Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). Neural Information Processing Systems Foundation, Inc. (NeurIPS), Virtual. 21085\u201321098. https:\/\/openreview.net\/forum?id=wvylaMP20_b Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. 2021. Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, Marc\u2019Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). Neural Information Processing Systems Foundation, Inc. (NeurIPS), Virtual. 21085\u201321098. https:\/\/openreview.net\/forum?id=wvylaMP20_b"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451022"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2018.41"},{"key":"e_1_3_2_1_24_1","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Dan Chen","year":"2019","unstructured":"Chen Dan , Hong Wang , Hongyang Zhang , Yuchen Zhou , and Pradeep Ravikumar . 2019 . Optimal Analysis of Subset-Selection Based L_p Low-Rank Approximation . In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). Neural Information Processing Systems Foundation, Inc. (NeurIPS), Canada. 2537\u20132548. Chen Dan, Hong Wang, Hongyang Zhang, Yuchen Zhou, and Pradeep Ravikumar. 2019. Optimal Analysis of Subset-Selection Based L_p Low-Rank Approximation. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). Neural Information Processing Systems Foundation, Inc. (NeurIPS), Canada. 2537\u20132548."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/070696507"},{"key":"e_1_3_2_1_26_1","volume-title":"49th International Colloquium on Automata, Languages, and Programming, ICALP 2022","volume":"14","author":"Deshpande Amit","year":"2022","unstructured":"Amit Deshpande and Rameshwar Pratap . 2022 . One-Pass Additive-Error Subset Selection for \u2113 _p Subspace Approximation. In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022 , July 4-8, 2022, Paris, France, Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff (Eds.) (LIPIcs , Vol. 229). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, France. 51:1\u201351: 14 . Amit Deshpande and Rameshwar Pratap. 2022. One-Pass Additive-Error Subset Selection for \u2113 _p Subspace Approximation. In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff (Eds.) (LIPIcs, Vol. 229). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, France. 51:1\u201351:14."},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011","author":"Deshpande Amit","year":"2011","unstructured":"Amit Deshpande , Madhur Tulsiani , and Nisheeth K. Vishnoi . 2011. Algorithms and Hardness for Subspace Approximation . In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 , San Francisco, California, USA, Janu-ary 23-25 , 2011 , Dana Randall (Ed.). SIAM, USA. 482\u2013496. Amit Deshpande, Madhur Tulsiani, and Nisheeth K. Vishnoi. 2011. Algorithms and Hardness for Subspace Approximation. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, Janu-ary 23-25, 2011, Dana Randall (Ed.). SIAM, USA. 482\u2013496."},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing","author":"Deshpande Amit","year":"2007","unstructured":"Amit Deshpande and Kasturi R. Varadarajan . 2007. Sampling-based dimension reduction for subspace approximation . In Proceedings of the 39th Annual ACM Symposium on Theory of Computing , San Diego, California, USA , June 11-13, 2007 , David S. Johnson and Uriel Feige (Eds.). ACM, USA. 641\u2013650. Amit Deshpande and Kasturi R. Varadarajan. 2007. Sampling-based dimension reduction for subspace approximation. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, David S. Johnson and Uriel Feige (Eds.). ACM, USA. 641\u2013650."},{"key":"e_1_3_2_1_29_1","volume-title":"Vempala","author":"Deshpande Amit","year":"2006","unstructured":"Amit Deshpande and Santosh S . Vempala . 2006 . Adaptive Sampling and Fast Low-Rank Matrix Approximation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, Josep D\u00edaz, Klaus Jansen, Jos\u00e9 D. P. Rolim, and Uri Zwick (Eds.) (Lecture Notes in Computer Science , Vol. 4110). Springer, Spain. 292\u2013 303 . Amit Deshpande and Santosh S. Vempala. 2006. Adaptive Sampling and Fast Low-Rank Matrix Approximation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, Josep D\u00edaz, Klaus Jansen, Jos\u00e9 D. P. Rolim, and Uri Zwick (Eds.) (Lecture Notes in Computer Science, Vol. 4110). Springer, Spain. 292\u2013303."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442702"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/07070471X"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993712"},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010","author":"Feldman Dan","year":"2010","unstructured":"Dan Feldman , Morteza Monemizadeh , Christian Sohler , and David P. Woodruff . 2010. Coresets and Sketches for High Dimensional Subspace Approximation Problems . In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 , Austin, Texas, USA , January 17-19, 2010 , Moses Charikar (Ed.). SIAM, USA. 630\u2013649. Dan Feldman, Morteza Monemizadeh, Christian Sohler, and David P. Woodruff. 2010. Coresets and Sketches for High Dimensional Subspace Approximation Problems. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, Moses Charikar (Ed.). SIAM, USA. 630\u2013649."},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning, ICML 2021","volume":"3229","author":"Feng Zhili","year":"2021","unstructured":"Zhili Feng , Praneeth Kacham , and David P. Woodruff . 2021. Dimensionality Reduction for the Sum-of-Distances Metric . In Proceedings of the 38th International Conference on Machine Learning, ICML 2021 , 18-24 July 2021 , Virtual Event, Marina Meila and Tong Zhang (Eds.) (Proceedings of Machine Learning Research , Vol. 139). PMLR, Virtual. 3220\u2013 3229 . Zhili Feng, Praneeth Kacham, and David P. Woodruff. 2021. Dimensionality Reduction for the Sum-of-Distances Metric. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, Marina Meila and Tong Zhang (Eds.) (Proceedings of Machine Learning Research, Vol. 139). PMLR, Virtual. 3220\u20133229."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796408"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0895"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.58"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384296"},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning, ICML 2021","volume":"4981","author":"Jiang Shuli","year":"2021","unstructured":"Shuli Jiang , Dennis Li , Irene Mengze Li , Arvind V. Mahankali , and David P. Woodruff . 2021. Streaming and Distributed Algorithms for Robust Column Subset Selection . In Proceedings of the 38th International Conference on Machine Learning, ICML 2021 , 18-24 July 2021 , Virtual Event, Marina Meila and Tong Zhang (Eds.) (Proceedings of Machine Learning Research , Vol. 139). PMLR, Virtual. 4971\u2013 4981 . Shuli Jiang, Dennis Li, Irene Mengze Li, Arvind V. Mahankali, and David P. Woodruff. 2021. Streaming and Distributed Algorithms for Robust Column Subset Selection. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, Marina Meila and Tong Zhang (Eds.) (Proceedings of Machine Learning Research, Vol. 139). PMLR, Virtual. 4971\u20134981."},{"key":"e_1_3_2_1_40_1","volume-title":"Johnson and Joram Lindenstrauss","author":"William","year":"2001","unstructured":"William B. Johnson and Joram Lindenstrauss . 2001 . Handbook of the geometry of Banach spaces. Vol. 1 . North-Holland, Amsterdam, USA. William B. Johnson and Joram Lindenstrauss. 2001. Handbook of the geometry of Banach spaces. Vol. 1. North-Holland, Amsterdam, USA."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.50"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.4064\/sm-63-2-207-212"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1311831"},{"key":"e_1_3_2_1_44_1","volume-title":"Conference on Learning Theory, COLT 2021","volume":"3195","author":"Li Yi","year":"2021","unstructured":"Yi Li , David P. Woodruff , and Taisuke Yasuda . 2021 . Exponentially Improved Dimensionality Reduction for \u2113 _1: Subspace Embeddings and Independence Testing . In Conference on Learning Theory, COLT 2021 , 15-19 August 2021, Boulder, Colorado, USA, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research , Vol. 134). PMLR, USA. 3111\u2013 3195 . Yi Li, David P. Woodruff, and Taisuke Yasuda. 2021. Exponentially Improved Dimensionality Reduction for \u2113 _1: Subspace Embeddings and Independence Testing. In Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research, Vol. 134). PMLR, USA. 3111\u20133195."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974317.7"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384331"},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Arvind","year":"2021","unstructured":"Arvind V. Mahankali and David P. Woodruff. 2021. Optimal \u2113 _1 Column Subset Selection and a Fast PTAS for Low Rank Approximation . In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13 , 2021 , D\u00e1niel Marx (Ed.). SIAM, Virtual. 560\u2013578. Arvind V. Mahankali and David P. Woodruff. 2021. Optimal \u2113 _1 Column Subset Selection and a Fast PTAS for Low Rank Approximation. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, D\u00e1niel Marx (Ed.). SIAM, Virtual. 560\u2013578."},{"key":"e_1_3_2_1_48_1","volume-title":"Symposium on Theory of Computing Conference, STOC\u201913","author":"Meng Xiangrui","year":"2013","unstructured":"Xiangrui Meng and Michael W. Mahoney . 2013. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression . In Symposium on Theory of Computing Conference, STOC\u201913 , Palo Alto, CA, USA , June 1-4, 2013 , Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (Eds.). ACM, USA. 91\u2013100. Xiangrui Meng and Michael W. Mahoney. 2013. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1-4, 2013, Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (Eds.). ACM, USA. 91\u2013100."},{"key":"e_1_3_2_1_49_1","volume-title":"Online Facility Location. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001","author":"Meyerson Adam","year":"2001","unstructured":"Adam Meyerson . 2001 . Online Facility Location. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001 , 14-17 October 2001, Las Vegas, Nevada, USA. IEEE Computer Society, USA. 426\u2013431. Adam Meyerson. 2001. Online Facility Location. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA. IEEE Computer Society, USA. 426\u2013431."},{"volume-title":"Matrix decomposition methods for data mining: Computational complexity and algorithms. Ph. D. Dissertation","author":"Miettinen Pauli","key":"e_1_3_2_1_50_1","unstructured":"Pauli Miettinen . 2009. Matrix decomposition methods for data mining: Computational complexity and algorithms. Ph. D. Dissertation . University of Helsinki . Pauli Miettinen. 2009. Matrix decomposition methods for data mining: Computational complexity and algorithms. Ph. D. Dissertation. University of Helsinki."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00076"},{"volume-title":"Univariate stable distributions: models for heavy tailed data","author":"Nolan John P.","key":"e_1_3_2_1_52_1","unstructured":"John P. Nolan . [2020] \u00a9 2020. Univariate stable distributions: models for heavy tailed data . Springer , Cham, New York, USA. John P. Nolan. [2020] \u00a9 2020. Univariate stable distributions: models for heavy tailed data. Springer, Cham, New York, USA."},{"key":"e_1_3_2_1_53_1","volume-title":"APPROX\/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), Mary Wootters and Laura Sanit\u00e0 (Eds.) (LIPIcs","volume":"21","author":"Parulekar Aditya","year":"2021","unstructured":"Aditya Parulekar , Advait Parulekar , and Eric Price . 2021 . L1 Regression with Lewis Weights Subsampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), Mary Wootters and Laura Sanit\u00e0 (Eds.) (LIPIcs , Vol. 207). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, USA. 49:1\u201349: 21 . Aditya Parulekar, Advait Parulekar, and Eric Price. 2021. L1 Regression with Lewis Weights Subsampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), Mary Wootters and Laura Sanit\u00e0 (Eds.) (LIPIcs, Vol. 207). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, USA. 49:1\u201349:21."},{"key":"e_1_3_2_1_54_1","volume-title":"Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011","author":"Sohler Christian","year":"2011","unstructured":"Christian Sohler and David P. Woodruff . 2011. Subspace embeddings for the L_1-norm with applications . In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011 , San Jose, CA, USA , 6-8 June 2011 , Lance Fortnow and Salil P. Vadhan (Eds.). ACM, USA. 755\u2013764. Christian Sohler and David P. Woodruff. 2011. Subspace embeddings for the L_1-norm with applications. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, Lance Fortnow and Salil P. Vadhan (Eds.). ACM, USA. 755\u2013764."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00081"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055431"},{"key":"e_1_3_2_1_57_1","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Song Zhao","year":"2019","unstructured":"Zhao Song , David P. Woodruff , and Peilin Zhong . 2019 . Towards a Zero-One Law for Column Subset Selection . In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). Neural Information Processing Systems Foundation, Inc. (NeurIPS), Canada. 6120\u20136131. Zhao Song, David P. Woodruff, and Peilin Zhong. 2019. Towards a Zero-One Law for Column Subset Selection. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). Neural Information Processing Systems Foundation, Inc. (NeurIPS), Canada. 6120\u20136131."},{"key":"e_1_3_2_1_58_1","unstructured":"Michael J. Todd. 2016. Minimum volume ellipsoids - theory and algorithms (MOS-SIAM Series on Optimization Vol. 23). SIAM USA. \t\t\t\t  Michael J. Todd. 2016. Minimum volume ellipsoids - theory and algorithms (MOS-SIAM Series on Optimization Vol. 23). SIAM USA."},{"key":"e_1_3_2_1_59_1","volume-title":"On the Sensitivity of Shape Fitting Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012","volume":"497","author":"Kasturi","year":"2012","unstructured":"Kasturi R. Varadarajan and Xin Xiao. 2012 . On the Sensitivity of Shape Fitting Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012 , December 15-17, 2012 , Hyderabad, India, Deepak D\u2019Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan (Eds.) (LIPIcs , Vol. 18). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, India. 486\u2013 497 . Kasturi R. Varadarajan and Xin Xiao. 2012. On the Sensitivity of Shape Fitting Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, Deepak D\u2019Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan (Eds.) (LIPIcs, Vol. 18). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, India. 486\u2013497."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.110"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477537"},{"key":"e_1_3_2_1_62_1","volume-title":"Low Rank Approximation Lower Bounds in Row-Update Streams. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014","author":"Woodruff David P.","year":"2014","unstructured":"David P. Woodruff . 2014 . Low Rank Approximation Lower Bounds in Row-Update Streams. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014 , December 8-13 2014, Montreal, Quebec, Canada, Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (Eds.). Neural Information Processing Systems Foundation, Inc. (NeurIPS), Canada. 1781\u20131789. https:\/\/proceedings.neurips.cc\/paper\/ 2014\/hash\/58e4d44e550d0f7ee0a23d6b02d9b0db-Abstract.html David P. Woodruff. 2014. Low Rank Approximation Lower Bounds in Row-Update Streams. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (Eds.). Neural Information Processing Systems Foundation, Inc. (NeurIPS), Canada. 1781\u20131789. https:\/\/proceedings.neurips.cc\/paper\/2014\/hash\/58e4d44e550d0f7ee0a23d6b02d9b0db-Abstract.html"},{"key":"e_1_3_2_1_63_1","volume-title":"High-Dimensional Geometric Streaming in Polynomial Space. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022","author":"David","year":"2022","unstructured":"David P. Woodruff and Taisuke Yasuda. 2022 . High-Dimensional Geometric Streaming in Polynomial Space. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 , Denver, CO, USA, October 31 - November 3, 2022 . IEEE, USA. 732\u2013743. David P. Woodruff and Taisuke Yasuda. 2022. High-Dimensional Geometric Streaming in Polynomial Space. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022. IEEE, USA. 732\u2013743."},{"key":"e_1_3_2_1_64_1","volume-title":"Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023","author":"David","year":"2023","unstructured":"David P. Woodruff and Taisuke Yasuda. 2023. Online Lewis Weight Sampling . In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 , Florence, Italy , January 22-25, 2023 , Nikhil Bansal and Viswanath Nagarajan (Eds.). SIAM, Italy. 4622\u20134666. David P. Woodruff and Taisuke Yasuda. 2023. Online Lewis Weight Sampling. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, Nikhil Bansal and Viswanath Nagarajan (Eds.). SIAM, Italy. 4622\u20134666."},{"key":"e_1_3_2_1_65_1","volume-title":"COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, Shai Shalev-Shwartz and Ingo Steinwart (Eds.) (JMLR Workshop and Conference Proceedings","volume":"567","author":"David","unstructured":"David P. Woodruff and Qin Zhang. 2013. Subspace Embeddings and \u2113 _p-Regression Using Exponential Random Variables . In COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, Shai Shalev-Shwartz and Ingo Steinwart (Eds.) (JMLR Workshop and Conference Proceedings , Vol. 30). JMLR.org, USA. 546\u2013 567 . David P. Woodruff and Qin Zhang. 2013. Subspace Embeddings and \u2113 _p-Regression Using Exponential Random Variables. In COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, Shai Shalev-Shwartz and Ingo Steinwart (Eds.) (JMLR Workshop and Conference Proceedings, Vol. 30). JMLR.org, USA. 546\u2013567."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585100","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585100","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:33Z","timestamp":1750295433000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":64,"alternative-id":["10.1145\/3564246.3585100","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585100","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}