Nonnegative Matrix Factorization (NMF) är en effektiv dimensionsreduktionsmetod för icke-negativa dyadiska data, och har visat sig vara användbar inom många områden, såsom textutvinning, bioinformatik och bildbehandling. NMF är vanligtvis formulerat som ett begränsat icke-konvext optimeringsproblem, och många algoritmer har utvecklats för att lösa det. Nyligen har en koordinatnedstigningsmetod, FastHals [3], föreslagits för att lösa minst kvadrater NMF och betraktas som en av de state-of-the-art tekniker för problemet. I detta dokument visar vi först att FastHals har en ineffektivitet i att det använder en cyklisk koordinat nedstigning schema och därmed utför onödiga nedstigning steg på oviktiga variabler. Vi presenterar sedan en variabel urvalsschema som använder lutningen av den objektiva funktionen för att komma fram till en ny koordinat nedstigning metod. Vår nya metod är betydligt snabbare i praktiken och vi visar att den har teoretiska konvergensgarantier. Dessutom när lösningen är sparsam, som ofta är fallet i verkliga tillämpningar, vår nya metod fördelar genom att välja viktiga variabler för att uppdatera oftare, vilket resulterar i högre hastighet. Som ett exempel på ett textdataset RCV1 är vår metod 7 gånger snabbare än FastHals, och mer än 15 gånger snabbare när glesheten ökas genom att lägga till en L1-påföljd. Vi utvecklar också nya koordinatnedstigningsmetoder när fel i NMF mäts med KLdivergence genom att använda Newton-metoden för att lösa de envariabla underproblemen. Experiment visar att vår algoritm för att minimera KL-divergensen är snabbare än Lee & Seungs multiplikativa regel med en faktor på 10 på CBCL-avbildningsdatasetet.
Införande av GCD-algoritm för att lösa NMF-problemet REF där de delar som ska uppdateras är girigt utvalda baserat på den viktmätare som beräknas med hjälp av gradienterna.
Fast coordinate descent methods with variable selection for non-negative matrix factorization
{'venue': 'KDD', 'journal': None, 'mag_field_of_study': ['Computer Science']}