Detta arbete introducerar Divide-Factor-Combine (DFC), en parallell divide-andconquer ram för bullriga matris factorization. DFC delar upp en storskalig matris factorization uppgift i mindre subproblem, löser varje subproblem parallellt med hjälp av en godtycklig basmatris factorization algoritm, och kombinerar subproblemlösningar med hjälp av tekniker från randomiserad matris approximation. Våra experiment med samarbetsfiltrering, videobakgrundsmodellering och simulerade data visar de nästan linjära till superlinjära uppfarter som uppnås med detta tillvägagångssätt. Dessutom visar vår analys att DFC har hög sannolikhet återvinning garantier jämförbara med de i sin basalgoritm. Notation för M  till R m×n, vi definierar M (i) som ith rad vektor och M ij som ijth posten. Om rank(M) = r, skriver vi den kompakta singular value decomposition (SVD) av M som där M är diagonal och innehåller r icke-noll singular värden av M, och U M M×r och V M M  och R n×r är motsvarande vänster och höger singular vektorer av M. Vi definierar M + = V M  och −1 M U  och M som Moore-Penrose pseudoinverse av M och P M = MM + som ortogonal projektion på kolumnutrymmet av M. Vi låter · 2, · F, och · * respektive betecknar spektral, Frobenius, och nukleära normer av en matris och låt · representerar l 2 norm av en vektor. I detta avsnitt presenterar vi vår split-and-conquer ram för skalbar bullriga matris factorization. Vi börjar med att definiera problemställningen av intresse. I inställningen av bullriga matris factorization, observerar vi en delmängd av posterna i en matris M = L 0 + S 0 + Z 0  till R m×n, där L 0 har rank r  på m, n, S 0 representerar en gles matris av avvikelser av godtycklig magnitud, och Z 0 är en tät bullermatris. Vi låter oss representera platserna för de observerade posterna och P är den ortogonala projektionen på utrymmet för m × n matriser med stöd, så att vårt mål är att återställa låg-rankade matrisen L 0 från P  och (M) med fel proportionellt till bullernivån  på Z 0 F. Vi kommer att fokusera på två specifika fall av detta allmänna problem: • Buller Matrix Complete (MC): s M poster avslöjas enhetligt utan ersättning, tillsammans med deras platser. Det finns inga avvikelser, så att S 0 är identiskt noll. • Noisy Robust Matrix Factorization (RMF): S 0 är identiskt noll, utom för s outlier poster av godtycklig magnitud med okända platser fördelade jämnt utan ersättning. Alla poster av M observeras, så att P (M) = M. Algoritmer 1 och 2 sammanfattar två kanoniska exempel på den allmänna Divide-Factor-Combine ram som vi kallar DFC-PROJ och DFC-NYS. Varje algoritm har tre enkla steg: (D-steg) Dela input matris i submatriser: DFC-PROJ slumpmässigt partitioner P  och (M) till t lcolumn submatriser, {P  och (C 1 ),. ., P (C t )} 1, medan DFC-NYS väljer en l-kolumn submatris, P (C) och en d-rad submatris, P (R), enhetligt slumpmässigt. (F steg) Faktor varje submatris parallellt med någon bas MF algoritm: DFC-PROJ utför t parallella submatris faktoriseringar, medan DFC-NYS utför två sådana parallella faktoriseringar. Standard bas MF algoritmer ut de låg-rankade approximationer { och 1,. .., t } för DFC-PROJ och, ochR för DFC-NYS. Alla matriser behålls i faktorform. DFC-PROJ genererar en slutlig låg rank uppskattningL proj genom att projicera [ ska 1,. .., till t ] på kolonnen utrymme för att 1, medan DFC-NYS bildar den lågrankade uppskattningenL nys från ochR via den generaliserade Nyström metoden. Dessa matris approximationstekniker beskrivs mer i detalj i avsnitt 2.3. Våra split-and-conquer algoritmer bygger på två metoder som genererar randomiserade låg-rank approximationer till en godtycklig matris M från submatriser av M.
Mackey och Al. REF introducerar en Divide-Factor-Combine (DFC) ram, där den dyra uppgiften att matris factorization slumpmässigt delas in i mindre subproblem.
Divide-and-Conquer Matrix Factorization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}