Abstrakt. Johnson-Lindenstrauss lemma visar att n-punkter i Euclidean utrymme (dvs. R n med avstånd mätt under 2 norm) kan kartläggas ner till O (log n)/ε 2 ) dimensioner så att ingen parvis avstånd förvrängs av mer än en (1 + ε) faktor. Att avgöra om en sådan dimensionsminskning är möjlig i 1 har varit en spännande öppen fråga. Vi visar starka lägre gränser för generell dimension minskning i 1. Vi ger en explicit familj av n punkter i 1 så att varje inbäddning med konstant förvrängning D kräver n (1/D 2 ) dimensioner. Detta bevisar att det inte finns någon analog av Johnson-Lindenstrauss lemma för 1; i själva verket, inbäddning med någon konstant förvrängning kräver n (1) dimensioner. Dessutom kräver att punkterna inbäddas i 1 med (1 + ε) förvrängning n dimensioner. Vårt bevis fastställer denna nedre gräns för kortaste vägmått för serieparallelldiagram. Vi använder oss i stor utsträckning av linjär programmering och dualitet när vi utformar våra gränser. Vi förväntar oss att de verktyg och tekniker vi utvecklar kommer att vara användbara för framtida utredningar av inbäddningar i 1.
Nedre gränser för dimensionsreduktion Det första omöjlighetsresultatet för dimensionsreduktion i 1 beror på REF, som visade att det finns en n-punktsundergrupp av 1 som kräver d ≥ n  på (1/D 2 ) för alla Ddistortion inbäddning till d 1.
On the impossibility of dimension reduction in l1
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}