CIF: Small: Recursive Robust Principal Components' Analyis (PCA)

CIF：小型：递归稳健主成分分析 (PCA)

• 批准号: 1117125
• 负责人: Namrata Vaswani
• 金额: $ 39.67万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117125&HistoricalAwards=false
• 关键词: CIF; Small; Recursive; Robust; Principal

We develop novel and provably stable polynomial time solutions for solving the recursive robust principal component analysis (PCA) problem. Here, "robust" refers to robustness to both independent and correlated sparse outliers. The goal of PCA is to find the principal component (PC) space, which is the minimum-dimension subspace that spans (or, in practice, approximately spans) a given dataset. Computing the PCs in the presence of outliers is called robust PCA. If the PC space changes over time, there is a need to update the PCs. Doing this recursively is referred to as recursive robust PCA. Key potential applications include automatic foreground extraction from similar-looking backgrounds in video; sensor-network-based detection and tracking of abnormal events such as forest fires; online detection of brain activation patterns from functional MRI sequences; and speech/audio extraction from large but correlated background noise.The key idea is to reformulate this as a problem of recursively recovering a time sequence of sparse signals in the presence of large but correlated noise. The noise must be correlated enough to have an approximately low rank covariance matrix that is either constant or changes slowly. The change in the support of the sparse signal sequences may or may not be slow, but it is highly correlated; e.g. the support can move, expand or deform over time. We ask the following practically relevant questions about performance guarantees of the proposed algorithms. (a) Under what conditions can we prove exact recovery? (b) When can be obtain time-invariant and small error bounds (i.e., show stability)? The research will be included in the curriculum at various levels and in undergraduate senior design and summer research projects.

我们开发新颖且可证明稳定的多项式时间解决方案来解决递归稳健主成分分析（PCA）问题。这里，“鲁棒”是指对独立和相关稀疏异常值的鲁棒性。 PCA 的目标是找到主成分 (PC) 空间，它是跨越（或实际上近似跨越）给定数据集的最小维度子空间。在存在异常值的情况下计算 PC 称为稳健 PCA。如果 PC 空间随时间发生变化，则需要更新 PC。递归地执行此操作称为递归鲁棒 PCA。主要的潜在应用包括从视频中相似的背景中自动提取前景；基于传感器网络的森林火灾等异常事件的检测和跟踪；根据功能性 MRI 序列在线检测大脑激活模式；关键思想是将其重新表述为在存在大量但相关的噪声的情况下递归恢复稀疏信号的时间序列的问题。噪声必须足够相关，才能具有恒定或缓慢变化的近似低秩协方差矩阵。稀疏信号序列的支持度的变化可能很慢，也可能不慢，但它是高度相关的；例如随着时间的推移，支撑件可能会移动、膨胀或变形。我们提出以下有关所提出算法的性能保证的实际相关问题。 (a) 在什么条件下我们可以证明精确恢复？ (b) 什么时候可以获得时不变且小误差界（即表现出稳定性）？该研究将纳入各级课程以及本科生高级设计和暑期研究项目。