Vi ger en ny metod för ordlistan lärande (även känd som "sparse coding") problem med att återställa en okänd n × m matris A (för m n) från exempel på formen y = Ax + e, där x är en slumpmässig vektor i R m med högst τ m nonzero koordinater, och e är en slumpmässig buller vektor i R n med begränsad magnitud. För fallet m = O(n) återvinner vår algoritm varje kolumn av A inom godtyckligt god konstant noggrannhet i tiden m O(log m/ log(τ −1 ), särskilt uppnå polynom tid om τ = m −δ för alla δ > 0, och tid m O(log m) om τ är (en tillräckligt liten) konstant. Tidigare algoritmer med jämförbara antaganden om fördelningen krävde vektorn x för att vara mycket glesare-på de flesta ε n nonzero koordinater-och det fanns inneboende hinder som hindrade dessa algoritmer från att ansöka om tätare x. Vi uppnår detta genom att utforma en algoritm för bullriga tensor nedbrytning som kan återställa, under ganska allmänna förhållanden, en ungefärlig rank-one nedbrytning av en tensor T, givet tillgång till en tensor T som är τ -nära T i spektral norm (när betraktas som en matris). Så vitt vi vet är detta den första algoritmen för tensornedbrytning som fungerar i det konstanta spektral-normbullersystemet, där det inte finns någon garanti för att den lokala optiman av T och T har liknande strukturer. Vår algoritm är baserad på en ny metod för att använda och analysera Sum of Squares semidefinite programmeringshierarki (Parrilo 2000, Lasserre 2001), och det kan ses * En fullständig version av detta dokument finns på http://arxiv.org/abs/1312.6652 † Stödd av NSF Grant 1111109. Stöds av en Microsoft Research Fellowship, en Alfred P. Sloan Fellowship, en NSF CAREER Award, och Simons Collaboration för algoritmer och geometri. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. 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, eller återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. som en indikation på nyttan av detta mycket allmänna och kraftfulla verktyg för oövervakade inlärningsproblem.
Baraks arbete på al. REF minskar problemet med att återställa kolumnerna i A till en (buller) tensor nedbrytningsproblem, som de löser med Sum-of-Squares (SoS) avkopplingar.
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}