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

在数据分析应用中，物理数据只能取非负值，如图像数据中的像素，需要获得物理上有意义的“非负主成分”，然后将数据表示为这些部分的加性组合。这就导致了近似非负矩阵分解（ANMF）问题，这是一个有约束的、非凸的全局最小化问题。现有的ANMF算法相对昂贵，不适合大规模、实时的应用。研究者建议将一个归一化的ANMF问题重新表述为一个低维优化问题，从而将问题的规模减少了一个潜在的非常大的因素。借助新公式的几何见解，该项目将专注于开发适用于大规模和实时应用的鲁棒高效新算法。目标是推进ANMF的基本原理，并实现其作为强大数据分析工具的全部潜力。计算机能否在几秒钟内，通过将一个人的快照与数据库中存储的一些（可能是旧的、低质量的）照片进行比较，高度自信地识别出一个人？近似非负矩阵分解（ANMF）是一种新兴的技术，可以帮助解决人脸检测问题和其他实时数据分析问题。在这个项目中，研究者将研究新的数学公式，并开发新的计算机算法，以更快、更可靠地解决ANMF问题。该奖项由美国国家科学基金会和情报界共同支持。数学和物理科学理事会的恐怖主义方法项目支持基础研究和劳动力发展方面的新概念，这些新概念有可能为国家安全做出贡献。

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.