CIF: Small: Online Algorithms for Streaming Structured Big-Data Mining

在当今的大数据时代，我们周围产生了大量的流媒体大数据。这些信息中的大多数要么没有存储，要么只存储了很短的时间段，例如，流媒体视频或改变社交网络连接。该项目开发了一种新的在线算法，用于从不完整或失真的数据中进行降维和结构信息恢复。该研究对大数据流中结构恢复的理论和实践都有一定的贡献。(1)研究人员和她的团队正在开发可证明是正确的在线算法，用于从欠采样、离群值损坏或其他高噪声的流数据中跟踪健壮的结构(子空间或支持)。虽然解决这些问题的批量方法已经得到了很好的研究，但在线问题在很大程度上是开放的。我们的理论结果是稳健的子空间跟踪(在线稳健PCA)和稳健支持跟踪问题的第一批正确结果之一。在线算法很有用，因为与大多数批处理技术相比，它们速度更快，需要的存储空间更少。此外，我们的在线算法通过利用某些额外的时间依赖假设消除了批处理方法的一个关键限制：与批处理方法相比，它们允许更多的相关支持更改。(2)研究人员还在为在线鲁棒稀疏-主成分分析问题以及其他几个相关问题开发新的可证明准确的解决方案。(3)最后，这项计划有助培养一批训练有素和多元化的未来劳动人口。我们预计我们的解决方案将显著改变各种大数据分析应用的最先进水平，例如，流视频分析、移动视频聊天、雾天或下雨环境中的自动车辆或飞机导航，以及从动态社交网络连接数据中检测异常或可疑行为。

In today's big data age, a lot of streaming big-data is generated around us. Most of this is either not stored or stored only for short periods of time, e.g., streaming videos or changing social network connections. This project develops novel online algorithms for dimensionality reduction and structural information recovery from incomplete or distorted data.This research makes several contributions to both the theory and the practice of structure recovery from streaming big-data. (1) The investigator and her team are developing provably correct online algorithms for robust structure (subspace or support) tracking from undersampled, outlier-corrupted or otherwise highly noisy streaming data. While batch approaches for these problems have been well-studied, the online problem is largely open. Our theoretical results are among the first correctness results for the robust subspace tracking (online robust PCA) and robust support tracking problems. Online algorithms are useful because they are faster and need lesser storage compared to most batch techniques. Moreover, our online algorithms remove a key limitation of batch approaches by exploiting certain extra temporal dependency assumptions: they allow significantly more correlated support change compared with batch methods. (2) The investigator is also developing novel provably accurate solutions for the online robust sparse-PCA problem, as well as several other related problems. (3) Finally, this project is helping to produce a well-trained and diverse future workforce. We expect our solutions to significantly transform the state-of-the-art in various big-data analytics applications, e.g., streaming video analytics, mobile video chats, autonomous vehicle or airplane navigation in foggy or rainy environments, anomalous or suspicious behavior detection from dynamic social network connectivity data.