{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T12:02:56Z","timestamp":1762430576689},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,11,11]],"date-time":"2011-11-11T00:00:00Z","timestamp":1320969600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2012,1]]},"DOI":"10.1007\/s00454-011-9384-2","type":"journal-article","created":{"date-parts":[[2011,11,10]],"date-time":"2011-11-10T09:41:00Z","timestamp":1320918060000},"page":"44-63","source":"Crossref","is-referenced-by-count":5,"title":["Efficient Subspace Approximation Algorithms"],"prefix":"10.1007","volume":"47","author":[{"given":"Nariankadu D.","family":"Shyamalkumar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kasturi","family":"Varadarajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,11,11]]},"reference":[{"key":"9384_CR1","volume-title":"Combinatorial and Computational Geometry","author":"P. Agarwal","year":"2005","unstructured":"Agarwal,\u00a0P., Har-Peled,\u00a0S., Varadarajan,\u00a0K.: Geometric approximation via coresets. In: Goodman,\u00a0J., Pach,\u00a0J., Welzl,\u00a0E. (eds.) Combinatorial and Computational Geometry. Cambridge University Press, Cambridge (2005)"},{"key":"9384_CR2","unstructured":"B\u0103doiu,\u00a0M., Indyk,\u00a0P.: Fast approximation algorithms for the hyperplane fitting problem. Manuscript (2006)"},{"key":"9384_CR3","first-page":"250","volume-title":"Proc. 34th Annu. ACM Sympos. Theory Comput.","author":"M. B\u0103doiu","year":"2002","unstructured":"B\u0103doiu,\u00a0M., Har-Peled,\u00a0S., Indyk,\u00a0P.: Approximate clustering via core-sets. In: Proc. 34th Annu. ACM Sympos. Theory Comput., pp. 250\u2013257 (2002)"},{"issue":"2","key":"9384_CR4","first-page":"201","volume":"28","author":"A. Brieden","year":"2002","unstructured":"Brieden,\u00a0A.: Geometric optimization problems likely not contained in apx. D C G, 28(2), 201\u2013209 (2002)","journal-title":"D C G"},{"key":"9384_CR5","first-page":"244","volume-title":"Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS)","author":"A. Brieden","year":"1998","unstructured":"Brieden,\u00a0A., Gritzmann,\u00a0P., Kannan,\u00a0R., Klee,\u00a0V., Lovasz,\u00a0L., Simonovits,\u00a0M.: Approximation of diameters: randomization doesn\u2019t help. In: Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), pp. 244\u2013251 (1998)"},{"key":"9384_CR6","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/S0167-7152(99)00067-X","volume":"45","author":"B. Chakraborty","year":"1999","unstructured":"Chakraborty,\u00a0B., Chaudhuri,\u00a0P.: A note on the robustness of multivariate medians. Stat. Probab. Lett. 45, 269\u2013276 (1999)","journal-title":"Stat. Probab. Lett."},{"key":"9384_CR7","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01585739","volume":"46","author":"R. Chandrasekharan","year":"1990","unstructured":"Chandrasekharan,\u00a0R., Tamir,\u00a0A.: Algebraic optimization: the Fermat\u2013Weber location problem. Math. Program. 46, 219\u2013224 (1990)","journal-title":"Math. Program."},{"key":"9384_CR8","first-page":"257","volume-title":"Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"K. Clarkson","year":"2005","unstructured":"Clarkson,\u00a0K.: Subgradient and sampling algorithms for L 1 regression. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 257\u2013266 (2005)"},{"key":"9384_CR9","first-page":"641","volume-title":"Proceedings of the 39th ACM Symposium on Theory of Computing (STOC)","author":"A. Deshpande","year":"2007","unstructured":"Deshpande,\u00a0A., Varadarajan, K.R.: Sampling-based dimension reduction for subspace approximation. In: Proceedings of the 39th ACM Symposium on Theory of Computing (STOC), pp. 641\u2013650 (2007)"},{"key":"9384_CR10","first-page":"292","volume-title":"Proceedings of APPROX-RANDOM","author":"A. Deshpande","year":"2006","unstructured":"Deshpande,\u00a0A., Vempala,\u00a0S.: Adaptive sampling and fast low-rank matrix approximation. In: Proceedings of APPROX-RANDOM, pp. 292\u2013303 (2006)"},{"key":"9384_CR11","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1145\/1109557.1109681","volume-title":"Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"A. Deshpande","year":"2006","unstructured":"Deshpande,\u00a0A., Rademacher,\u00a0L., Vempala,\u00a0S., Wang,\u00a0G.: Matrix approximation and projective clustering via volume sampling. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1117\u20131126 (2006)"},{"key":"9384_CR12","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/S0377-2217(02)00647-1","volume":"152","author":"J.M. Diaz-Banez","year":"2004","unstructured":"Diaz-Banez, J.M., Mesa, J.A., Schobel,\u00a0A.: Continuous location of dimensional structures. Eur. J. Oper. Res. 152, 22\u201344 (2004)","journal-title":"Eur. J. Oper. Res."},{"key":"9384_CR13","first-page":"1127","volume-title":"Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"P. Drineas","year":"2005","unstructured":"Drineas,\u00a0P., Mahoney, M.W., Muthukrishnan,\u00a0S.: Sampling algorithms for L 2 regression and applications. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1127\u20131136 (2005)"},{"key":"9384_CR14","first-page":"1","volume":"73","author":"U. Faigle","year":"1996","unstructured":"Faigle,\u00a0U., Kern,\u00a0W., Streng,\u00a0M.: Note on the computational complexity of j-radii of polytopes in \u211d n . Math. Program. 73, 1\u20135 (1996)","journal-title":"Math. Program."},{"key":"9384_CR15","first-page":"315","volume-title":"Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS)","author":"D. Feldman","year":"2006","unstructured":"Feldman,\u00a0D., Fiat,\u00a0A., Sharir,\u00a0M.: Coresets for weighted facilities and their applications. In: Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), pp. 315\u2013324 (2006)"},{"issue":"6","key":"9384_CR16","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1145\/1039488.1039494","volume":"51","author":"A. Frieze","year":"2004","unstructured":"Frieze,\u00a0A., Kannan,\u00a0R., Vempala,\u00a0S.: Fast Monte-Carlo algorithms for finding low rank approximations. J. ACM 51(6), 1025\u20131041 (2004)","journal-title":"J. ACM"},{"key":"9384_CR17","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF01581243","volume":"59","author":"P. Gritzmann","year":"1993","unstructured":"Gritzmann,\u00a0P., Klee,\u00a0V.: Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces. Math. Program. 59, 163\u2013213 (1993)","journal-title":"Math. Program."},{"key":"9384_CR18","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0012-365X(94)00111-U","volume":"136","author":"P. Gritzmann","year":"1994","unstructured":"Gritzmann,\u00a0P., Klee,\u00a0V.: On the complexity of some basic problems in computational convexity: I.\u00a0Containment problems. Discrete Math. 136, 129\u2013174 (1994)","journal-title":"Discrete Math."},{"key":"9384_CR19","unstructured":"Har-Peled,\u00a0S.: Low rank matrix approximation in linear time. Manuscript (2006)"},{"issue":"1","key":"9384_CR20","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.comgeo.2006.02.003","volume":"36","author":"S. Har-Peled","year":"2007","unstructured":"Har-Peled,\u00a0S.: How to get close to the median shape. Comput. Geom. 36(1), 39\u201351 (2007)","journal-title":"Comput. Geom."},{"key":"9384_CR21","first-page":"312","volume-title":"Proc. 18th Annu. ACM Sympos. Comput. Geom","author":"S. Har-Peled","year":"2002","unstructured":"Har-Peled,\u00a0S., Varadarajan, K.R.: Projective clustering in high dimensions using core-sets. In: Proc. 18th Annu. ACM Sympos. Comput. Geom, pp. 312\u2013318 (2002)"},{"issue":"2","key":"9384_CR22","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s00454-004-1118-2","volume":"32","author":"S. Har-Peled","year":"2004","unstructured":"Har-Peled,\u00a0S., Varadarajan,\u00a0K.: High-dimensional shape fitting in linear time. Discrete Comput. Geom. 32(2), 269\u2013288 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"9384_CR23","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/978-3-642-58043-7_7","volume-title":"New Trends in Discrete and Computational Geometry","author":"N.M. Korneenko","year":"1993","unstructured":"Korneenko, N.M., Martini,\u00a0H.: Hyperplane approximation and related topics. In: Pach,\u00a0J. (ed.) New Trends in Discrete and Computational Geometry, pp. 135\u2013162. Springer, New York (1993)"},{"key":"9384_CR24","volume-title":"Multivariate Analysis","author":"K.V. Mardia","year":"1979","unstructured":"Mardia, K.V., Kent, J.T., Bibby, J.M.: Multivariate Analysis. Academic Press, London (1979)"},{"key":"9384_CR25","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0747-7171(08)80067-3","volume":"10","author":"N. Megiddo","year":"1990","unstructured":"Megiddo,\u00a0N.: On the complexity of some geometric problems in unbounded dimension. J. Symb. Comput. 10, 327\u2013334 (1990)","journal-title":"J. Symb. Comput."},{"key":"9384_CR26","unstructured":"Panigrahy,\u00a0R.: Minimum enclosing polytope in high dimensions. arXiv:cs.CG\/0407020"},{"key":"9384_CR27","doi-asserted-by":"crossref","first-page":"2323","DOI":"10.1126\/science.290.5500.2323","volume":"290","author":"S. Roweis","year":"2000","unstructured":"Roweis,\u00a0S., Saul,\u00a0L.: Nonlinear dimensionality reduction by locally linear embedding. Science 290, 2323\u20132326 (2000)","journal-title":"Science"},{"key":"9384_CR28","first-page":"143","volume-title":"Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS)","author":"T. Sarlos","year":"2006","unstructured":"Sarlos,\u00a0T.: Improved approximation algorithms for large matrices via random projections. In: Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), pp. 143\u2013152 (2006)"},{"key":"9384_CR29","doi-asserted-by":"crossref","first-page":"2319","DOI":"10.1126\/science.290.5500.2319","volume":"290","author":"J. Tenenbaum","year":"2000","unstructured":"Tenenbaum,\u00a0J., de Silva,\u00a0V., Langford,\u00a0J.: A global geometric framework for nonlinear dimensionality reduction. Science 290, 2319\u20132323 (2000)","journal-title":"Science"},{"issue":"6","key":"9384_CR30","doi-asserted-by":"crossref","first-page":"1764","DOI":"10.1137\/050627472","volume":"36","author":"K.R. Varadarajan","year":"2007","unstructured":"Varadarajan, K.R., Venkatesh,\u00a0S., Zhang,\u00a0J., Ye,\u00a0Y.: Approximating the radii of point sets. SIAM J. Comput. 36(6), 1764\u20131776 (2007)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9384_CR31","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1137\/S1064827502419154","volume":"26","author":"Z. Zhang","year":"2005","unstructured":"Zhang,\u00a0Z., Zha,\u00a0H.: Principal manifolds and nonlinear dimension reduction via local tangent space alignment. SIAM J. Sci. Comput. 26(1), 313\u2013338 (2005)","journal-title":"SIAM J. Sci. Comput."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-011-9384-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-011-9384-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-011-9384-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:50:34Z","timestamp":1559073034000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-011-9384-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,11]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["9384"],"URL":"https:\/\/doi.org\/10.1007\/s00454-011-9384-2","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,11]]}}}