Abstrakt. Vi anser att problemet är att inbädda ett mått i den lågdimensionella euklideiska rymden. De klassiska teorem av Bourgain, och av Johnson och Lindenstrauss säger att någon metrisk på n punkter inbäddar i en O(log n)-dimensionell Euclidean utrymme med O(log n) distorsion. Dessutom visar ett enkelt "volym"-argument att denna gräns är nästan snäv: ett enhetligt mått på n-punkter kräver nästan logaritmiskt antal dimensioner för att inbäddas med logaritmisk förvrängning. Det är naturligt att fråga sig om en sådan volymbegränsning är det enda hindret för lågdimensionella inbäddningar. Med andra ord, har dubbla mätvärden, som inte har stora enhetliga submetrics, och därmed inga volymhinder för lågdimensionella inbäddningar, inbäddade i lågdimensionella euklideiska utrymmen med liten förvrängning? I den här artikeln ger vi ett positivt svar på den frågan. Vi visar hur man inbäddar eventuella dubbleringsmått i O(log log n) dimensioner med o(log n) distorsion. Detta är den första inbäddning för tillstånd att göra digitala eller hårda kopior av delar eller allt detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior visar detta meddelande på första sidan eller första skärmen av en display tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Tillstånd kan begäras från Publications Department., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (fördubbling av mätvärden till färre än logaritmiskt antal dimensioner, även möjliggör logaritmisk förvrängning. Detta resultat är en extrem punkt i vår allmänna avvägning mellan distorsion och dimension: med tanke på en n-punkt metrisk (V, d) med dubblering dimension dim D, och eventuella måldimension T i intervallet (dim D log n) ≤ T ≤ O (log n), visar vi att den metriska inbäddar i Euclidean utrymme R T med O(log n ε dim D /T ) distorsion.
En avvägning mellan snedvridning och dimension för att inbädda dubbleringsmått visades av REF.
Ultra-low-dimensional embeddings for doubling metrics
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}