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.