ACT/SGER: Algorithms for Large-Scale Approximate Nonnegative Matrix Factorization in Data Analysis

William Marsh Rice University, Houston TX

Investigators

Abstract

In data analysis applications where physical data can only take nonnegative values such as pixels in imagery data, it is desirable to obtain physically meaningful ``nonnegative principal parts'', and then represent data as additive combinations of these parts. This leads to the approximate nonnegative matrix factorization (ANMF) problem, which is a constrained, nonconvex global minimization problem. The existing algorithms for ANMF are relatively expensive and not suitable for large-scale, real-time applications. The investigator proposes to reformulate a normalized ANMF problem into a low-dimensional optimization problem, thus reducing the problem size by a potentially very large factor. With the help of geometric insights from the new formulation, the project will focus on developing robust and efficient new algorithms suitable for very large-scale and real-time applications. The goal is to advance the fundamentals of ANMF and realize its full potential as a powerful data analysis tool. Can a computer identify a person, in a few seconds and with a high degree of confidence, by comparing a snapshot of his to some, perhaps old and low-quality, photos stored in a database? Approximate nonnegative matrix factorization (ANMF) is an emerging technique that may help solve this face detection problem and other real-time data analysis problems. In this project, the investigator will study novel mathematical formulations and develop new computer algorithms for solving the ANMF problems more quickly and more reliably. This award is supported jointly by the NSF and the Intelligence Community. The Approaches to Terrorism program in the Directorate for Mathematics and Physical Sciences supports new concepts in basic research and workforce development with the potential to contribute to national security.