Métodos de Otimização Contínua para o Problema de Fatoração Não-Negativa de Matrizes

Abstract

AFatoração Não-Negativa de Matrizes (NMF) é uma técnica de redução de dimensio nalidade que impõe a não negatividade aos fatores. Este trabalho investiga a NMF do ponto de vista da otimização contínua, formulando o problema como a minimização da distância, com respeito à norma de Frobenius, entre a matriz de dados e o produto de dois fatores não-negativos. São estudados dois algoritmos iterativos inspirados no método de minimizações alternadas: o método das Atualizações Multiplicativas, proposto por Lee e Seung (2001), e o método de Minimizações Alternadas com Gradi ente Projetado, baseado nos trabalhos de Lin (2007). Mostra-se que a função objetivo é convexa em cada bloco de variáveis separadamente, mas não é conjuntamente con vexa. Para o método de Lee e Seung, demonstra-se a monotonicidade da função de custo por meio de funções auxiliares; contudo, não há garantia de convergência a pontos estacionários. Para o método de Lin, estabelece-se a convergência a pontos estacionários do problema com restrições de caixa utilizando um resultado de Grippo e Sciandrone (2000). Além disso, propõe-se uma heurística para a escolha de cotas superiores, baseada nas condições de Karush-Kuhn-Tucker do problema original, a f im de tornar a região viável compacta. Experimentos numéricos com matrizes sin téticas e em uma aplicação ao reconhecimento de faces mostram que o método de Lin apresenta melhor performance, obtendo acurácia superior na classificação, com erros de reconstrução comparáveis aos do método multiplicativo. Os resultados re forçam a importância da fundamentação teórica na escolha do algoritmo e indicam possibilidades para trabalhos futuros.