{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T06:40:16Z","timestamp":1729406416243,"version":"3.27.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T00:00:00Z","timestamp":1683763200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T00:00:00Z","timestamp":1683763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,10]]},"DOI":"10.1007\/s00453-023-01124-0","type":"journal-article","created":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T10:38:30Z","timestamp":1683801510000},"page":"3144-3167","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["One-Pass Additive-Error Subset Selection for $$\\ell _{p}$$ Subspace Approximation and (k,\u00a0p)-Clustering"],"prefix":"10.1007","volume":"85","author":[{"given":"Amit","family":"Deshpande","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rameshwar","family":"Pratap","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,11]]},"reference":[{"key":"1124_CR1","doi-asserted-by":"crossref","unstructured":"Feldman, D.: Introduction to Core-sets: an Updated Survey (2020)","DOI":"10.1002\/widm.1335"},{"issue":"6","key":"1124_CR2","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1145\/1039488.1039494","volume":"51","author":"AM Frieze","year":"2004","unstructured":"Frieze, A.M., Kannan, R., Vempala, S.S.: Fast monte-carlo algorithms for finding low-rank approximations. J. ACM 51(6), 1025\u20131041 (2004). https:\/\/doi.org\/10.1145\/1039488.1039494","journal-title":"J. ACM"},{"key":"1124_CR3","unstructured":"Wei, K., Iyer, R., Bilmes, J.: Submodularity in data subset selection and active learning. In: Proceedings of the 32nd International Conference on Machine Learning, vol. 37, pp. 1954\u20131963 (2015)"},{"key":"1124_CR4","doi-asserted-by":"crossref","unstructured":"Boutsidis, C., Mahoney, M.W., Drineas, P.: An improved approximation algorithm for the column subset selection problem. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 968\u2013977 (2009). SIAM","DOI":"10.1137\/1.9781611973068.105"},{"issue":"2","key":"1124_CR5","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1137\/07070471X","volume":"30","author":"P Drineas","year":"2008","unstructured":"Drineas, P., Mahoney, M.W., Muthukrishnan, S.: Relative-error CUR matrix decompositions. SIAM J. Matrix Anal. Appl. 30(2), 844\u2013881 (2008). https:\/\/doi.org\/10.1137\/07070471X","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"3","key":"1124_CR6","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1073\/pnas.0803205106","volume":"106","author":"MW Mahoney","year":"2009","unstructured":"Mahoney, M.W., Drineas, P.: CUR matrix decompositions for improved data analysis. Proc. Natl. Acad. Sci. USA 106(3), 697\u2013702 (2009). https:\/\/doi.org\/10.1073\/pnas.0803205106","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"1","key":"1124_CR7","first-page":"2729","volume":"14","author":"S Wang","year":"2013","unstructured":"Wang, S., Zhang, Z.: Improving CUR matrix decomposition and the nystr\u00f6m approximation via adaptive sampling. J. Mach. Learn. Res. 14(1), 2729\u20132769 (2013)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"1124_CR8","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1561\/2200000035","volume":"3","author":"MW Mahoney","year":"2011","unstructured":"Mahoney, M.W.: Randomized algorithms for matrices and data. Found. Trends Mach. Learn. 3(2), 123\u2013224 (2011). https:\/\/doi.org\/10.1561\/2200000035","journal-title":"Found. Trends Mach. Learn."},{"key":"1124_CR9","unstructured":"Ida, Y., Kanai, S., Fujiwara, Y., Iwata, T., Takeuchi, K., Kashima, H.: Fast deterministic cur matrix decomposition with accuracy assurance. In: International Conference on Machine Learning, pp. 4594\u20134603 (2020). PMLR"},{"key":"1124_CR10","doi-asserted-by":"crossref","unstructured":"Sun, J., Xie, Y., Zhang, H., Faloutsos, C.: Less is more: Compact matrix decomposition for large sparse graphs. In: Proceedings of the 2007 SIAM International Conference on Data Mining, pp. 366\u2013377 (2007). SIAM","DOI":"10.1137\/1.9781611972771.33"},{"key":"1124_CR11","doi-asserted-by":"crossref","unstructured":"Mahoney, M.W., Maggioni, M., Drineas, P.: Tensor-cur decompositions for tensor-based data. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 327\u2013336 (2006)","DOI":"10.1145\/1150402.1150440"},{"key":"1124_CR12","doi-asserted-by":"crossref","unstructured":"Drineas, P., Kerenidis, I., Raghavan, P.: Competitive recommendation systems. In: Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, pp. 82\u201390 (2002)","DOI":"10.1145\/509907.509922"},{"key":"1124_CR13","doi-asserted-by":"publisher","unstructured":"Deshpande, A., Vempala, S.: Adaptive sampling and fast low-rank matrix approximation. In: Proceedings of the 9th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, and 10th International Conference on Randomization and Computation. APPROX\u201906\/RANDOM\u201906, pp. 292\u2013303. Springer, Berlin, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11830924_28","DOI":"10.1007\/11830924_28"},{"issue":"12","key":"1124_CR14","doi-asserted-by":"publisher","first-page":"225","DOI":"10.4086\/toc.2006.v002a012","volume":"2","author":"A Deshpande","year":"2006","unstructured":"Deshpande, A., Rademacher, L., Vempala, S.S., Wang, G.: Matrix approximation and projective clustering via volume sampling. Theory Comput. 2(12), 225\u2013247 (2006). https:\/\/doi.org\/10.4086\/toc.2006.v002a012","journal-title":"Theory Comput."},{"key":"1124_CR15","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sinop, A.K.: Optimal column-based low-rank matrix reconstruction. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201912, pp. 1207\u20131214. Society for Industrial and Applied Mathematics, USA (2012)","DOI":"10.1137\/1.9781611973099.95"},{"key":"1124_CR16","unstructured":"Derezinski, M., Warmuth, M.K.: Unbiased estimates for linear regression via volume sampling. Advances in Neural Information Processing Systems 30 (2017)"},{"key":"1124_CR17","doi-asserted-by":"crossref","unstructured":"Broadbent, M.E., Brown, M., Penner, K., Ipsen, I., Rehman, R.: Subset selection algorithms: Randomized vs. deterministic. SIAM Undergraduate Research Online 3(01) (2010)","DOI":"10.1137\/09S010435"},{"key":"1124_CR18","unstructured":"Dan, C., Wang, H., Zhang, H., Zhou, Y., Ravikumar, P.K.: Optimal analysis of subset-selection based $$\\ell _p$$ low-rank approximation. Advances in Neural Information Processing Systems 32 (2019)"},{"issue":"2","key":"1124_CR19","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"2006","unstructured":"Lloyd, S.: Least squares quantization in pcm. IEEE Trans. Inf. Theor. 28(2), 129\u2013137 (2006). https:\/\/doi.org\/10.1109\/TIT.1982.1056489","journal-title":"IEEE Trans. Inf. Theor."},{"key":"1124_CR20","unstructured":"Arthur, D., Vassilvitskii, S.: K-means++: The advantages of careful seeding. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201907, pp. 1027\u20131035. Society for Industrial and Applied Mathematics, USA (2007)"},{"key":"1124_CR21","doi-asserted-by":"crossref","unstructured":"Bahmani, B., Moseley, B., Vattani, A., Kumar, R., Vassilvitskii, S.: Scalable k-means++. Proc. VLDB Endow. 5(7), 622\u2013633 (2012). https:\/\/doi.org\/10.14778\/2180912.2180915","DOI":"10.14778\/2180912.2180915"},{"key":"1124_CR22","doi-asserted-by":"publisher","unstructured":"Bachem, O., Lucic, M., Hassani, S.H., Krause, A.: Approximate k-means++ in sublinear time. Proceedings of the AAAI Conference on Artificial Intelligence 30(1) (2016). https:\/\/doi.org\/10.1609\/aaai.v30i1.10259","DOI":"10.1609\/aaai.v30i1.10259"},{"key":"1124_CR23","doi-asserted-by":"crossref","unstructured":"Bachem, O., Lucic, M., Hassani, S.H., Krause, A.: Fast and provably good seedings for k-means. In: Proceedings of the 30th International Conference on Neural Information Processing Systems. NIPS\u201916, pp. 55\u201363. Curran Associates Inc., Red Hook (2016)","DOI":"10.1609\/aaai.v30i1.10259"},{"key":"1124_CR24","doi-asserted-by":"publisher","unstructured":"Deshpande, A., Varadarajan, K.: Sampling-based dimension reduction for subspace approximation. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. STOC \u201907, pp. 641\u2013650. Association for Computing Machinery, New York, (2007). https:\/\/doi.org\/10.1145\/1250790.1250884","DOI":"10.1145\/1250790.1250884"},{"issue":"2","key":"1124_CR25","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D Aloise","year":"2009","unstructured":"Aloise, D., Deshpande, A., Hansen, P., Popat, P.: Np-hardness of euclidean sum-of-squares clustering. Mach. Learn. 75(2), 245\u2013248 (2009). https:\/\/doi.org\/10.1007\/s10994-009-5103-0","journal-title":"Mach. Learn."},{"key":"1124_CR26","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2010.05.034","volume":"442","author":"M Mahajan","year":"2012","unstructured":"Mahajan, M., Nimbhorkar, P., Varadarajan, K.R.: The planar k-means problem is np-hard. Theor. Comput. Sci. 442, 13\u201321 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2010.05.034","journal-title":"Theor. Comput. Sci."},{"key":"1124_CR27","doi-asserted-by":"publisher","unstructured":"Aggarwal, A., Deshpande, A., Kannan, R.: Adaptive sampling for k-means clustering, pp. 15\u201328 (2009). https:\/\/doi.org\/10.1007\/978-3-642-03685-9_2","DOI":"10.1007\/978-3-642-03685-9_2"},{"key":"1124_CR28","unstructured":"Wei, D.: A constant-factor bi-criteria approximation guarantee for k-means++. In: Proceedings of the 30th International Conference on Neural Information Processing Systems. NIPS\u201916, pp. 604\u2013612. Curran Associates Inc., Red Hook (2016)"},{"issue":"2","key":"1124_CR29","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.ipl.2014.07.009","volume":"115","author":"R Jaiswal","year":"2015","unstructured":"Jaiswal, R., Kumar, M., Yadav, P.: Improved analysis of d$${}^{\\text{2 }}$$-sampling based PTAS for k-means and other clustering problems. Inf. Process. Lett. 115(2), 100\u2013103 (2015). https:\/\/doi.org\/10.1016\/j.ipl.2014.07.009","journal-title":"Inf. Process. Lett."},{"key":"1124_CR30","doi-asserted-by":"crossref","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: A simple linear time $$(1+\\epsilon )$$-approximation algorithm for $$k$$-means clustering in any dimensions. In: 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 454\u2013462 (2004). IEEE","DOI":"10.1109\/FOCS.2004.7"},{"key":"1124_CR31","doi-asserted-by":"crossref","unstructured":"Cohen, M.B., Musco, C., Musco, C.: Input sparsity time low-rank approximation via ridge leverage score sampling. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201917, pp. 1758\u20131777. Society for Industrial and Applied Mathematics, USA (2017)","DOI":"10.1137\/1.9781611974782.115"},{"key":"1124_CR32","doi-asserted-by":"publisher","unstructured":"Mahabadi, S., Razenshteyn, I., Woodruff, D.P., Zhou, S.: Non-adaptive adaptive sampling on turnstile streams. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2020, pp. 1251\u20131264. Association for Computing Machinery, New York (2020). https:\/\/doi.org\/10.1145\/3357713.3384331","DOI":"10.1145\/3357713.3384331"},{"issue":"1","key":"1124_CR33","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/3147.3165","volume":"11","author":"JS Vitter","year":"1985","unstructured":"Vitter, J.S.: Random sampling with a reservoir. ACM Trans. Math. Softw. 11(1), 37\u201357 (1985). https:\/\/doi.org\/10.1145\/3147.3165","journal-title":"ACM Trans. Math. Softw."},{"key":"1124_CR34","doi-asserted-by":"publisher","unstructured":"Efraimidis, P.S., Spirakis, P.P.: Weighted random sampling. In: Encyclopedia of Algorithms, pp. 2365\u20132367 (2016). https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_478","DOI":"10.1007\/978-1-4939-2864-4_478"},{"key":"1124_CR35","unstructured":"Ghashami, M., Liberty, E., Phillips, J.M., Woodruff, D.P.: Frequent directions : Simple and deterministic matrix sketching. CoRR abs\/1501.01711 (2015) arXiv:1501.01711"},{"key":"1124_CR36","doi-asserted-by":"crossref","unstructured":"Braverman, V., Drineas, P., Musco, C., Musco, C., Upadhyay, J., Woodruff, D.P., Zhou, S.: Near optimal linear algebra in the online and sliding window models. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 517\u2013528 (2020). IEEE","DOI":"10.1109\/FOCS46700.2020.00055"},{"key":"1124_CR37","doi-asserted-by":"crossref","unstructured":"Ban, F., Bhattiprolu, V., Bringmann, K., Kolev, P., Lee, E., Woodruff, D.P.: A ptas for $$\\ell _p$$-low rank approximation. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 747\u2013766 (2019). SIAM","DOI":"10.1137\/1.9781611975482.47"},{"key":"1124_CR38","unstructured":"Chierichetti, F., Gollapudi, S., Kumar, R., Lattanzi, S., Panigrahy, R., Woodruff, D.P.: Algorithms for $$\\ell _p$$ low-rank approximation. In: International Conference on Machine Learning, pp. 806\u2013814 (2017). PMLR"},{"key":"1124_CR39","doi-asserted-by":"publisher","unstructured":"Liberty, E.: Simple and deterministic matrix sketching. In:Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD \u201913, pp. 581\u2013588. Association for Computing Machinery, New York, NY, USA (2013). https:\/\/doi.org\/10.1145\/2487575.2487623","DOI":"10.1145\/2487575.2487623"},{"key":"1124_CR40","doi-asserted-by":"crossref","unstructured":"Ghashami, M., Phillips, J.M.: Relative errors for deterministic low-rank matrix approximations. In:Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201914, pp. 707\u2013717. Society for Industrial and Applied Mathematics, USA (2014)","DOI":"10.1137\/1.9781611973402.53"},{"issue":"5","key":"1124_CR41","doi-asserted-by":"publisher","first-page":"1762","DOI":"10.1137\/15M1009718","volume":"45","author":"M Ghashami","year":"2016","unstructured":"Ghashami, M., Liberty, E., Phillips, J.M., Woodruff, D.P.: Frequent directions: Simple and deterministic matrix sketching. SIAM J. Comput. 45(5), 1762\u20131792 (2016). https:\/\/doi.org\/10.1137\/15M1009718","journal-title":"SIAM J. Comput."},{"key":"1124_CR42","unstructured":"Cormode, G., Dickens, C., Woodruff, D.: Leveraging well-conditioned bases: Streaming and distributed summaries in minkowski p-norms. In: International Conference on Machine Learning, pp. 1048\u20131056 (2018)"},{"key":"1124_CR43","doi-asserted-by":"publisher","unstructured":"Clarkson, K.L., Woodruff, D.P.: Low-rank approximation and regression in input sparsity time. J. ACM 63(6) (2017). https:\/\/doi.org\/10.1145\/3019134","DOI":"10.1145\/3019134"},{"key":"1124_CR44","doi-asserted-by":"crossref","unstructured":"Feldman, D., Monemizadeh, M., Sohler, C., Woodruff, D.P.: Coresets and sketches for high dimensional subspace approximation problems. In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 630\u2013649 (2010). SIAM","DOI":"10.1137\/1.9781611973075.53"},{"key":"1124_CR45","unstructured":"Ailon, N., Jaiswal, R., Monteleoni, C.: Streaming k-means approximation. Adv Neural Inform Process Syst22 (2009)"},{"issue":"1","key":"1124_CR46","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/s00453-013-9833-9","volume":"70","author":"R Jaiswal","year":"2014","unstructured":"Jaiswal, R., Kumar, A., Sen, S.: A simple D 2-sampling based PTAS for k-means and other clustering problems. Algorithmica 70(1), 22\u201346 (2014). https:\/\/doi.org\/10.1007\/s00453-013-9833-9","journal-title":"Algorithmica"},{"key":"1124_CR47","unstructured":"Anari, N., Gharan, S.O., Rezaei, A.: Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes. In: Conference on Learning Theory, pp. 103\u2013115 (2016). PMLR"},{"key":"1124_CR48","doi-asserted-by":"publisher","unstructured":"CHAO, M.T.: A general purpose unequal probability sampling plan. Biometrika 69(3), 653\u2013656 (1982) https:\/\/academic.oup.com\/biomet\/article-pdf\/69\/3\/653\/591311\/69-3-653.pdf. https:\/\/doi.org\/10.1093\/biomet\/69.3.653","DOI":"10.1093\/biomet\/69.3.653"},{"issue":"1","key":"1124_CR49","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1080\/07362990008809654","volume":"18","author":"H Cai","year":"2000","unstructured":"Cai, H.: Exact bound for the convergence of metropolis chains. Stochastic Anal Appl 18(1), 63\u201371 (2000). https:\/\/doi.org\/10.1080\/07362990008809654","journal-title":"Stochastic Anal Appl"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01124-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01124-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01124-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T06:24:55Z","timestamp":1729405495000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01124-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,11]]},"references-count":49,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["1124"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01124-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,5,11]]},"assertion":[{"value":"23 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"All authors participated in this study give the publisher the permission to publish this work.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}