Abstract-Ges en uppsättning n punkter i 1, hur många dimensioner behövs för att representera alla pairwise avstånd inom en specifik förvrängning? Denna fråga om fördelning mellan dimensioner är väl förstådd för 2 normen, där O( (log n)/ 2 ) dimensioner räcker för att uppnå 1 + snedvridning. I skarp kontrast finns det ett betydande gap mellan övre och nedre gränser för dimensionsminskning i 1. Ett nytt resultat visar att distorsion 1 + kan uppnås med n/ 2 dimensioner. Å andra sidan, de enda lägre gränserna kända är att distorsion δ kräver n 2 ) dimensioner och att distorsion 1+ kräver n 1/2-O( log(1/ )) dimensioner. I detta arbete visar vi de första nästan linjära nedre gränserna för dimensionsreduktion i 1. I synnerhet visar vi att 1 + distorsion kräver minst n 1‐O(1/ log(1/ )) dimensioner. Våra bevis är kombinatoriska, men inspirerade av linjär programmering. I själva verket leder våra tekniker till ett enkelt kombinatoriskt argument som motsvarar LP-baserade bevis för BrinkmanCharikar för lägre gränser på dimensionsreduktion i 1.
För 1 + distorsionssystemet använde REF kombinatoriska tekniker för att visa att dimensionen måste vara minst n 1‐O(1/ log(1/ )) (och gav också ett annat bevis på det ursprungliga resultatet).
Near Linear Lower Bound for Dimension Reduction in L1
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}