Den exakta icke-negativa matris factorization (exact NMF) problem är följande: givet en m-by-n nonnegative matris X och en faktorization rank r, hitta, om möjligt, en m-by-r nonnegative matris W och en r-by-n nonnegative matris H sådan att X = W H. I detta papper, föreslår vi två heuristics för exakt NMF, en inspirerad från simulerad annealing och den andra från den giriga randomiserade adaptiva sökproceduren. Vi visar att dessa två heuristiker kan beräkna exakta icke-negativa faktoriseringar för flera klasser av icke-negativa matriser (nämligen linjära Euclidean avstånd matriser, slack matriser, unik-delbarhet matriser, och slumpmässigt genererade matriser) och som sådana visa sin överlägsenhet över standard multi-start strategier. Vi överväger också en hybridisering mellan dessa två heuristiker som gör att vi kan kombinera fördelarna med båda metoderna. Slutligen diskuterar vi användningen av dessa heuristiker för att få insikt om beteendet hos den icke-negativa rangen, d.v.s. den minsta factorization rangen sådan att en exakt NMF existerar. I synnerhet motbevisar vi ett antagande om den icke-negativa rangen av en Kronecker produkt, föreslår en ny övre gräns för utvidgning komplexiteten av generiska n-gons och antar det exakta värdet av (i) utvidgningen komplexiteten av regelbundna n-gons och (ii) den icke-negativa rangen av en submatris av slack matris av korrelationspolytopen.
Vandaele m.fl. REF föreslog giriga randomiserade adaptiva sökprocedurer och simulerade glödgning för att lösa NMF-problemet.
Heuristics for Exact Nonnegative Matrix Factorization
{'venue': 'Journal of Global Optimization 65 (2), pp 369-400, 2016', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}