{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T12:01:49Z","timestamp":1770552109151,"version":"3.49.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,6,4]],"date-time":"2015-06-04T00:00:00Z","timestamp":1433376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s00454-015-9707-9","type":"journal-article","created":{"date-parts":[[2015,6,4]],"date-time":"2015-06-04T02:59:19Z","timestamp":1433386759000},"page":"291-315","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Nonlinear Approach to Dimension Reduction"],"prefix":"10.1007","volume":"54","author":[{"given":"Lee-Ad","family":"Gottlieb","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,4]]},"reference":[{"key":"9707_CR1","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Embedding metric spaces in their intrinsic dimension. In: Proceedings of the 19th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 363\u2013372. SIAM, Philadelphia (2008)"},{"key":"9707_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: On low dimensional local embeddings. In: Proceedings of the 20th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 875\u2013884. SIAM, Philadelphia (2009)","DOI":"10.1137\/1.9781611973068.95"},{"issue":"1\u20133","key":"9707_CR3","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/S0012-365X(03)00227-9","volume":"273","author":"N Alon","year":"2003","unstructured":"Alon, N.: Problems and results in extremal combinatorics I. Discrete Math. 273(1\u20133), 31\u201353 (2003)","journal-title":"Discrete Math."},{"issue":"4","key":"9707_CR4","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P Assouad","year":"1983","unstructured":"Assouad, P.: Plongements lipschitziens dans $${ R}^{n}$$ R n . Bull. Soc. Math. France 111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. France"},{"issue":"4","key":"9707_CR5","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/S0195-6698(13)80131-X","volume":"11","author":"K Ball","year":"1990","unstructured":"Ball, K.: Isometric embedding in $$l_p$$ l p -spaces. Eur. J. Comb. 11(4), 305\u2013311 (1990)","journal-title":"Eur. J. Comb."},{"key":"9707_CR6","unstructured":"Bartal, Y., Gottlieb, L.: Dimension reduction techniques for $$l_p\\,(1 \\le p <\\infty )$$ l p ( 1 \u2264 p < \u221e ) , with applications (2014). Available at arXiv:1408.1789"},{"key":"9707_CR7","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Recht, B., Schulman, L.: Dimensionality reduction: beyond the Johnson\u2013Lindenstrauss bound. In: Proceedings of the 22nd Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 868\u2013887. SIAM, Philadelphia (2011). An earlier version was available from the authors\u2019 webpage in 2007 under the title \u201cA Nash-type Dimensionality Reduction for Discrete Subsets of $$L_2$$ L 2 \u201d","DOI":"10.1137\/1.9781611973082.68"},{"issue":"4","key":"9707_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1734213.1734215","volume":"57","author":"H Chan","year":"2010","unstructured":"Chan, H., Gupta, A., Talwar, K.: Ultra-low-dimensional embeddings for doubling metrics. J. ACM 57(4), 1\u201326 (2010)","journal-title":"J. ACM"},{"key":"9707_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of Cuts and Metrics","author":"MM Deza","year":"1997","unstructured":"Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. Springer, Berlin (1997)"},{"issue":"2","key":"9707_CR10","doi-asserted-by":"crossref","first-page":"261","DOI":"10.2140\/pjm.1991.150.261","volume":"150","author":"T Figiel","year":"1991","unstructured":"Figiel, T., Johnson, W.B., Schechtman, G.: Factorizations of natural embeddings of $$l^n_p$$ l p n into $$l_r$$ l r . II. Pac. J. Math. 150(2), 261\u2013277 (1991)","journal-title":"Pac. J. Math."},{"key":"9707_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 534\u2013543. IEEE, Washington (October 2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"issue":"5","key":"9707_CR12","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35(5), 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9707_CR13","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1273340.1273347","volume":"3","author":"P Indyk","year":"2007","unstructured":"Indyk, P., Naor, A.: Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms 3(3), 31 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"9707_CR14","doi-asserted-by":"crossref","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Proceedings of the Conference in Modern Analysis and Probability (New Haven, CT, 1982), pp. 189\u2013206. American Mathematical Society, Providence, RI (1984)","DOI":"10.1090\/conm\/026\/737400"},{"key":"9707_CR15","unstructured":"Kahane, J.-P.: H\u00e9lices et quasi-h\u00e9lices. In Mathematical Analysis and Applications, Part B, Advances in Mathematics: Supplementary Studies, vol. 7, pp. 417\u2013433. Academic Press, New York (1981)"},{"issue":"134","key":"9707_CR16","doi-asserted-by":"crossref","first-page":"77","DOI":"10.4064\/fm-22-1-77-108","volume":"22","author":"MD Kirszbraun","year":"1934","unstructured":"Kirszbraun, M.D.: \u00dcber die zusammenziehenden und lipschitzchen transformationen. Fund. Math. 22(134), 77\u2013108 (1934)","journal-title":"Fund. Math."},{"key":"9707_CR17","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 791\u2013801. SIAM, Philadelphia (January 2004)"},{"issue":"1\u20133","key":"9707_CR18","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1023\/A:1012093209450","volume":"87","author":"U Lang","year":"2001","unstructured":"Lang, U., Plaut, C.: Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata 87(1\u20133), 285\u2013307 (2001)","journal-title":"Geom. Dedicata"},{"issue":"8","key":"9707_CR19","doi-asserted-by":"crossref","first-page":"1180","DOI":"10.1016\/j.ejc.2004.07.002","volume":"26","author":"JR Lee","year":"2005","unstructured":"Lee, J.R., Mendel, M., Naor, A.: Metric structures in $$L_1$$ L 1 : dimension, snowflakes, and average distortion. Eur. J. Comb. 26(8), 1180\u20131190 (2005)","journal-title":"Eur. J. Comb."},{"key":"9707_CR20","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF02761110","volume":"93","author":"J Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J.: On the distortion required for embedding finite metric spaces into normed spaces. Israel J. Math. 93, 333\u2013344 (1996)","journal-title":"Israel J. Math."},{"key":"9707_CR21","unstructured":"Matou\u0161ek, J.: Open problems on low-distortion embeddings of finite metric spaces 2002. Available at http:\/\/kam.mff.cuni.cz\/~matousek\/metrop.ps (2007). Accessed 29 May 2015"},{"key":"9707_CR22","doi-asserted-by":"crossref","unstructured":"Ng, T.S.E., Zhang, H.: Predicting internet network distance with coordinates-based approaches. In: Proceedings of the INFOCOM, vol. 1, pp. 170\u2013179. IEEE, Washington (2002)","DOI":"10.1109\/INFCOM.2002.1019258"},{"issue":"5500","key":"9707_CR23","doi-asserted-by":"crossref","first-page":"2323","DOI":"10.1126\/science.290.5500.2323","volume":"290","author":"S Roweis","year":"2000","unstructured":"Roweis, S., Saul, L.: Nonlinear dimensionality reduction by locally linear embedding. Science 290(5500), 2323\u20132326 (2000)","journal-title":"Science"},{"issue":"2","key":"9707_CR24","first-page":"159","volume":"61","author":"G Schechtman","year":"1987","unstructured":"Schechtman, G.: More on embedding subspaces of $$L_p$$ L p in $$l^n_r$$ l r n . Compositio Math. 61(2), 159\u2013169 (1987)","journal-title":"Compositio Math."},{"issue":"4","key":"9707_CR25","doi-asserted-by":"crossref","first-page":"811","DOI":"10.2307\/1968466","volume":"39","author":"IJ Schoenberg","year":"1938","unstructured":"Schoenberg, I.J.: Metric spaces and completely monotone functions. Ann. Math. 39(4), 811\u2013841 (1938)","journal-title":"Ann. Math."},{"issue":"3","key":"9707_CR26","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1090\/S0002-9947-1938-1501980-0","volume":"44","author":"IJ Schoenberg","year":"1938","unstructured":"Schoenberg, I.J.: Metric spaces and positive definite functions. Trans. Am. Math. Soc. 44(3), 522\u2013536 (1938)","journal-title":"Trans. Am. Math. Soc."},{"key":"9707_CR27","doi-asserted-by":"crossref","unstructured":"Schulman, L.J.: Clustering for edge-cost minimization (extended abstract). In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 547\u2013555. ACM, New York (2000). Full version available as ECCC report TR99-035","DOI":"10.1145\/335305.335373"},{"issue":"2","key":"9707_CR28","first-page":"363","volume":"108","author":"M Talagrand","year":"1990","unstructured":"Talagrand, M.: Embedding subspaces of $$L_1$$ L 1 into $$l^N_1$$ l 1 N . Proc. Am. Math. Soc. 108(2), 363\u2013369 (1990)","journal-title":"Proc. Am. Math. Soc."},{"issue":"3","key":"9707_CR29","first-page":"355","volume":"28","author":"M Talagrand","year":"1992","unstructured":"Talagrand, M.: Approximating a helix in finitely many dimensions. Ann. Inst. H. Poincar\u00e9 Probab. Statist. 28(3), 355\u2013363 (1992)","journal-title":"Ann. Inst. H. Poincar\u00e9 Probab. Statist."},{"key":"9707_CR30","doi-asserted-by":"crossref","unstructured":"Talagrand, M.: Embedding subspaces of $$L_p$$ L p in $$l^N_p$$ l p N . In Geometric Aspects of Functional Analysis (Israel, 1992\u20131994), Operator Theory: Advances and Applications, vol. 77, pp. 311\u2013325. Birkh\u00e4user, Basel (1995)","DOI":"10.1007\/978-3-0348-9090-8_26"},{"issue":"5500","key":"9707_CR31","doi-asserted-by":"crossref","first-page":"2319","DOI":"10.1126\/science.290.5500.2319","volume":"290","author":"JB Tenenbaum","year":"2000","unstructured":"Tenenbaum, J.B., de Silva, V., Langford, J.C.: A global geometric framework for nonlinear dimensionality reduction. Science 290(5500), 2319\u20132323 (2000)","journal-title":"Science"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9707-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-015-9707-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9707-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,25]],"date-time":"2019-08-25T23:26:32Z","timestamp":1566775592000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-015-9707-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,4]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["9707"],"URL":"https:\/\/doi.org\/10.1007\/s00454-015-9707-9","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,4]]}}}