En enastående öppen fråga [51, Fråga #5] ber att karakterisera metriska utrymmen där avstånd kan uppskattas med hjälp av effektiva skisser. Speciellt säger vi att en skiss algoritm är effektiv om det uppnår konstant approximation med konstant skissstorlek. Ett välkänt resultat av Indyk (J. ACM, 2006) innebär att ett mått som medger en konstant förvrängning inbäddning i p för p 0, 2] också medger ett effektivt skissningsschema. Men är det motsatta sant, d.v.s. att inbädda i p det enda sättet att uppnå effektiv skissning? Vi tar upp dessa frågor för det viktiga speciella fallet av normerade utrymmen, genom att ge en nästan fullständig karakterisering av skissning i form av inbäddningar. I synnerhet bevisar vi att ett finit-dimensionellt normat utrymme möjliggör effektiva skisser om och endast om det inbäddar (linjärt) i 1−ε med konstant förvrängning. Vi bevisar vidare att för normer som är stängda under totalprodukt, är effektiv skissning lika med inbäddning i 1 med konstant förvrängning. Exempel på sådana normer är Jordens distans (speciellt dess normvariant, kallad Kantorovich-Rubinstein norm), och spårnormen (alias. Schatten 1-norm eller kärnnormen). Använda kända icke-bäddbarhet teorem för dessa normer av Naor och Schechtman (SICOMP, 2007) och av Pisier (Compositio. Math., 1978), drar vi sedan slutsatsen att dessa utrymmen inte medger effektiva skisser heller, gör framsteg mot att besvara en annan öppen fråga [51, Fråga nr 7]. Slutligen observerar vi att lösa om "sketching är likvärdigt att inbädda i 1 för allmänna normer" (dvs. utan ovanstående begränsning) är detsamma som att lösa ett välkänt öppet problem i funktionell analys som Kwapien ställde 1969.
Ett annat relaterat arbete är REF, som visar att för normer är förekomsten av bra skisser lika med enhetlig inbäddbarhet i 2.
Sketching and Embedding are Equivalent for Norms
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}