{"entities":{"Q2571745":{"pageid":2582488,"ns":120,"title":"Item:Q2571745","lastrevid":57959412,"modified":"2026-04-03T06:08:54Z","type":"item","id":"Q2571745","labels":{"en":{"language":"en","value":"Measured descent: A new embedding method for finite metrics"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2228663"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2571745$56DDD331-6958-4E2F-895C-AB616774A1B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dfa851a3b451a3b7653c108a5f505f3562b86a13","datavalue":{"value":{"text":"Measured descent: A new embedding method for finite metrics","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2571745$A109CC49-AD49-4937-B2BC-1D617C9D580E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a92f2179a4a87b6e650867d1e192c2fc67748bd2","datavalue":{"value":"1108.46010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2571745$D8B9AE7C-2D3D-4713-BC78-16626BA0C6DE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4ab31fa932ebec99543358ca6fa8f0045c7548e","datavalue":{"value":{"entity-type":"item","numeric-id":249078,"id":"Q249078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2571745$43ADDAFC-067D-4565-B536-1569A7B739D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2629bc8a032bf1a0a3df3197cce82e656cd5e623","datavalue":{"value":{"entity-type":"item","numeric-id":359546,"id":"Q359546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2571745$EEF063FC-BF68-4424-913A-0480E7A851F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e15064a955e2b0fc1477893d6cd3b38b1f1b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":185634,"id":"Q185634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2571745$065A1C40-43B9-468C-BD56-510B2A22BB92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2129463e4fb202d617a918e802d846c3730ad87","datavalue":{"value":{"entity-type":"item","numeric-id":610753,"id":"Q610753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2571745$8763DD54-AABC-418F-A66C-EF8AE56F643D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9f7ed99dde37a1ed2b712f0eb37bcc96b8743b93","datavalue":{"value":{"entity-type":"item","numeric-id":172246,"id":"Q172246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2571745$C4F15155-2FD4-45D3-A943-051D05F0BB18","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c52c36c21dbb1fa9a6ec6b8c4cff8252b0f6e684","datavalue":{"value":{"time":"+2005-11-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2571745$6BF5C607-5D16-4975-9527-08323D096A1E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2a6b683d110b258f0a6d5f1a7a73c1b2f4f133b5","datavalue":{"value":"https://arxiv.org/abs/cs/0412008","type":"string"},"datatype":"url"},"type":"statement","id":"Q2571745$98B07C36-9399-4113-A184-7B615B6FE4E7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9dd8a9c4ca00ad3495eabe74e1fda1478866c4c4","datavalue":{"value":"The authors devise a new embedding method, called measure descent. It is based on decomposing a metric space locally, according to the density of a certain probability measure. The method unifies and refines the methods of Bourgain and of Rao for constructing Fr{\u00e9chet}-type embeddings, that is embeddings where each coordinate is proportional to the distance from some subset of the metric space. The authors prove that any \\(n\\)-point metric space \\(X\\) embeds into \\(\\ell _2\\) with distortion \\(O(\\sqrt{\\alpha _X \\log n})\\), where \\(\\alpha _X\\) is a geometric estimate on the decomposability of \\(X\\) satisfying \\(\\alpha _X = O(\\log n)\\) and \\(\\alpha _X = O(\\log \\lambda _X)\\), where \\(\\lambda _X\\) (\\(\\leq n\\)) is the doubling constant of \\(X\\). Thus the result recovers \\textit{J.\\,Bourgain}'s theorem [Isr.\\ J.\\ Math.\\ 52, 46--52 (1985; Zbl 0657.46013)].   The next result answers affirmatively a question posed by K.\\,Feige about volume-respecting embeddings. The notion of volume-respecting embeddings was introduced by \\textit{U.\\,Feige} [J.~Comput.\\ Syst.\\ Sci.\\ 60, No.\\,3, 510--539 (2000; Zbl 0958.68191)] as follows. Let \\(S\\) be a \\(k\\)-point subset of \\(X\\). Define  \\[  \\text{vol} (S) = \\sup \\{\\text{vol}_{k-1} (\\text{conv}\\;g(S)) \\mid g : S \\to L_2 \\text{ is } 1\\text{-Lipschitz} \\},  \\]  where \\(\\text{conv}\\) denotes the convex hull and \\(\\text{vol} _{k-1}\\) denotes the \\((k-1)\\)-dimensional volume with respect to the Euclidean structure induced by \\(L_2\\). A~\\(1\\)-Lipschitz mapping \\(f : S \\to L_2\\) is called \\((k, \\eta)\\)-volume-respecting if, for every \\(k\\)-point subset \\(S\\) of \\(X\\), one has  \\[  \\left( \\text{vol} (S) / \\text{vol} _{k-1} (\\text{conv} \\;f(S)) \\right)^{1/(k-1)} \\leq \\eta.  \\]  The authors prove that every \\(n\\)-point metric space \\(X\\) admits an embedding into \\(L_2\\) which is \\((k, O(\\sqrt{\\alpha _X \\log n}))\\)-volume-respecting for every \\(2\\leq k \\leq n\\). Finally, the authors use their methods to improve a result of Rao and answer in the affirmative a question of Rabinovitch. Namely, they show that every \\(n\\)-point edge-weighted planar graph equipped with the shortest path metric embeds into \\(\\ell _{\\infty}^{O(\\log n)}\\) with \\(O(1)\\) distortion.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2571745$8DDF9B0C-6B95-4F2B-AAE2-FEC55FB4825A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"79f8d64a9a918483c4e5229e22c3ea6d9711b362","datavalue":{"value":"46B07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2571745$79E05331-5768-4597-ABC8-777CB96EBE05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f6e6327c80fa5b5429b44357435fe659a5220afe","datavalue":{"value":"46B09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2571745$87301D26-646A-4373-AC2C-7C2C365AB7E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b1973cb8aec01fefec7c06d3ac452f505442dd21","datavalue":{"value":"54C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2571745$BF42C231-6D8D-4505-8D4A-940B140C3F52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2571745$3D84BA19-3AE3-47E2-AE06-CD40D6AFB297","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"374d9cbecf176eb232486ccaf546526518256472","datavalue":{"value":"2228663","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2571745$96C31630-ABDB-4EE2-84E3-BC16ADC8AC22","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff82759d6402dd8020361c46f57bbac1506f9228","datavalue":{"value":"decomposition bundle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2571745$0B66998E-959A-466C-AF20-A3CBE468DDEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd195618975a5773a609e7679d204d0191e5de0e","datavalue":{"value":"distortion","type":"string"},"datatype":"string"},"type":"statement","id":"Q2571745$BA44DE76-08B7-4765-B89A-C409E9546CC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e86d9b4ad5a06064fd9c9bcbc50f8026b1c776dc","datavalue":{"value":"embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q2571745$25D59F5A-41D0-43FB-AC95-6D2DB3EA5B13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"acba796d993df630211dc7c5bcad8936b3a96da9","datavalue":{"value":"\\(n\\)-point metric space","type":"string"},"datatype":"string"},"type":"statement","id":"Q2571745$46122007-8109-421F-9891-9AE95E36918E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ec53353af0d8a6834c6e9018a331afc537e41c2","datavalue":{"value":"measured descent","type":"string"},"datatype":"string"},"type":"statement","id":"Q2571745$ADB9EEDB-3568-4B7E-B177-98C9588251AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30fc9b2d8646ef758df2bc4206ee7db4af3329c4","datavalue":{"value":"padded decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2571745$D1FFD7DF-8D18-4D63-9863-AA1CF3127337","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3186bcbf17a931d31ac5e011ac5cf706211ba410","datavalue":{"value":"volume-respecting","type":"string"},"datatype":"string"},"type":"statement","id":"Q2571745$2E55491D-D52C-4FEE-82F8-546EA26BCC78","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2571745$3EA93AC0-BC00-4BE2-88D7-95B70157849A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"87c44841556b4f072f2c872e08dadc592a349cc6","datavalue":{"value":"W3098011928","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2571745$6F0C0807-EE79-40B1-87E7-360F8B025416","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8d7c6727619b6711d2b7864423c73e56d8717884","datavalue":{"value":"10.1007/S00039-005-0527-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2571745$F0A32A3F-4B7C-4C3E-A0CF-6A035DEC1000","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9e52245b2ae38c20f7043f0f8b9c6d098da43b5","datavalue":{"value":{"entity-type":"item","numeric-id":5894374,"id":"Q5894374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c76dd5d3af0fe95dc61ecb7f77ddfb9ad73d042f","datavalue":{"value":{"amount":"+0.8562412","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2571745$0D52FFD3-A7CD-4627-9FB4-D154474E8C91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"564a1ac3236392c943d672ab83f111bbb0b4a213","datavalue":{"value":{"entity-type":"item","numeric-id":5891923,"id":"Q5891923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d004ae33dbe823fee3978f30ddec32cdda54c3a","datavalue":{"value":{"amount":"+0.85624117","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2571745$E9AE0198-D5EA-4C0C-8FE0-122B842EB952","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b51edea040fe4ffd3a4f007dcfaf1fe5237e79c","datavalue":{"value":{"entity-type":"item","numeric-id":1076679,"id":"Q1076679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8bf6df7441c7aa30c9edcd97a81dcf72aaf2fb9","datavalue":{"value":{"amount":"+0.84989","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2571745$90315FFA-3763-4B62-8CC8-A5C70D91C2E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6899e9d3d599182032c800667614a825b5804567","datavalue":{"value":{"entity-type":"item","numeric-id":4471325,"id":"Q4471325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"688ea613fe6c31a6e09ce793fbed72cdcceec367","datavalue":{"value":{"amount":"+0.8498132","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2571745$5F4FED83-CFF7-4A6B-8440-D07E48C1DF3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90f4c095772f80c4e19f0abc3ed3662cfd130fab","datavalue":{"value":{"entity-type":"item","numeric-id":5716764,"id":"Q5716764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e48750f434ca4790833cf31d788b126a22f224c4","datavalue":{"value":{"amount":"+0.847463","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2571745$DB0DEFF4-7B67-4983-9867-FF73A11F4866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4df57dc1d55597027586f69e6e63c189c14b7bc","datavalue":{"value":{"entity-type":"item","numeric-id":4281228,"id":"Q4281228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2df1cb4fdd65a7f62925f07bb5ff4b390ddbe092","datavalue":{"value":{"amount":"+0.84626454","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2571745$D232A9A0-47DC-4206-ABE2-EB62CC36EBA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb5312c3e00cc1832784b582802f476405c437e8","datavalue":{"value":{"entity-type":"item","numeric-id":826038,"id":"Q826038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2438d9ef73430d5bd8968a237117573ceeb5e2a5","datavalue":{"value":{"amount":"+0.84625936","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2571745$096E6CBC-BF41-43ED-9835-2D85F202B293","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4acef233fe075879b693db6547cdb88ee834d2b7","datavalue":{"value":{"entity-type":"item","numeric-id":394235,"id":"Q394235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e102d6ed508578703a2e792a5998f21b9cd4e5d","datavalue":{"value":{"amount":"+0.84568274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2571745$46538A36-8FF7-4B54-915F-16D20DE756F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"135c5bcb0c2e999e27ecf5c71b3809fad0fcb0a0","datavalue":{"value":{"entity-type":"item","numeric-id":3188862,"id":"Q3188862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25825743a025297d5759946bc6b77f29223d136b","datavalue":{"value":{"amount":"+0.8456714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2571745$B4D21A3D-FCA9-472C-A177-FFA89458EC96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8453b67e5ec59dd0aa463d82dedb0dbebf49327","datavalue":{"value":{"entity-type":"item","numeric-id":260269,"id":"Q260269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25825743a025297d5759946bc6b77f29223d136b","datavalue":{"value":{"amount":"+0.8456714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2571745$98FD7D76-42A7-4141-A234-4F0C20CAF3F5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2571745","badges":[]}}}}}