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

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

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.