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

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

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.