Vid lexikoninlärning, även känd som gles kodning, ges algoritmen prover av formen y = Ax där x  till R m är en okänd slumpmässig gles vektor och A är en okänd lexikonmatris i R n×m (vanligtvis m > n, vilket är det överkompletta fallet). Målet är att lära sig A och x. Detta problem har studerats inom neurovetenskap, maskininlärning, visioner och bildbehandling. I praktiken är det löst med heuristiska algoritmer och bevisbara algoritmer verkade svåra att hitta. Nyligen har bevisbara algoritmer hittats som fungerar om den okända funktionen vektor x är ε n-sparse eller till och med sparser. Spielman m.fl. Detta höjde problemet med att utforma bevisbara algoritmer som tillåter gleshet  på den dolda vektorn x. Den nuvarande papper designar algoritmer som tillåter gleshet upp till n/poly (log n). Det fungerar för en klass av matriser där funktioner är individuellt återvinningsbara, ett nytt begrepp som identifieras i detta dokument som kan motivera ytterligare arbete. Algoritmen körs i kvasipolynom tid eftersom de använder begränsad uppräkning.
På samma sätt föreslår Arora et al ett ramverk som tillåter sparsamhet upp till O(d/ log d) men körs i kvasi-polynom tid REF.
More Algorithms for Provable Dictionary Learning
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}