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

ACT/SGER：数据分析中大规模近似非负矩阵分解的算法

• 批准号: 0442065
• 负责人: Yin Zhang
• 金额: --
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2006-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0442065&HistoricalAwards=false
• 关键词: ACT; SGER; Algorithms; Large; Scale

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.

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