
NSF Org: |
CCF Division of Computing and Communication Foundations |
Recipient: |
|
Initial Amendment Date: | September 3, 2015 |
Latest Amendment Date: | September 3, 2015 |
Award Number: | 1526870 |
Award Instrument: | Standard Grant |
Program Manager: |
Phillip Regalia
pregalia@nsf.gov (703)292-2981 CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
Start Date: | October 1, 2015 |
End Date: | September 30, 2019 (Estimated) |
Total Intended Award Amount: | $442,385.00 |
Total Awarded Amount to Date: | $442,385.00 |
Funds Obligated to Date: |
|
History of Investigator: |
|
Recipient Sponsored Research Office: |
1350 BEARDSHEAR HALL AMES IA US 50011-2103 (515)294-5225 |
Sponsor Congressional District: |
|
Primary Place of Performance: |
3121 Coover Hall Ames IA US 50011-2207 |
Primary Place of
Performance Congressional District: |
|
Unique Entity Identifier (UEI): |
|
Parent UEI: |
|
NSF Program(s): | Comm & Information Foundations |
Primary Program Source: |
|
Program Reference Code(s): |
|
Program Element Code(s): |
|
Award Agency Code: | 4900 |
Fund Agency Code: | 4900 |
Assistance Listing Number(s): | 47.070 |
ABSTRACT
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.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
Intellectual Merit:
During this project, we solved or partially solved on the following problems.
- Provable guarantees and experimental evaluation of a novel simple Recursive Projected Compressive Sensing (ReProCS) based algorithm for dynamic robust PCA (robust subspace tracking). Dynamic robust PCA refers to the dynamic (time-varying) extension of robust PCA (RPCA). It assumes that the true (uncorrupted) data lies in a low-dimensional subspace that can change with time, albeit slowly. The goal is to track this changing subspace over time in the presence of sparse outliers. We develop and study a novel algorithm, that we call simple-ReProCS, based on the recently introduced Recursive Projected Compressive Sensing (ReProCS) framework. Our work provides the first guarantee for dynamic RPCA that holds under weakened versions of standard RPCA assumptions, slow subspace change and a lower bound assumption on most outlier magnitudes. Our result is significant because (i) it removes the strong assumptions needed by the two previous complete guarantees for ReProCS-based algorithms; (ii) it shows that it is possible to achieve significantly improved outlier tolerance, compared with all existing RPCA or dynamic RPCA solutions by exploiting the above two simple extra assumptions; and (iii) it proves that simple-ReProCS is online (after initialization), fast, and, has near-optimal memory complexity.
- We obtained novel guarantees for the related problem of PCA in sparse data-dependent noise
- We showed that a simple modification of the ReProCS algorithm also solves the dynamic Matrix Completion (Subspace Tracking with Missing Entries) problem and its Robust generalization (both missing data and outliers). In the only missing-data setting, the guarantee for ReProCS is in fact a lot simpler, and hence a lot more interesting than for the robust setting.
- We did some preliminary work on Phaseless PCA (Low Rank Phase Retrieval) and Phaseless Subspace Tracking.
Work supported by this grant was published in NIPS 2016, AISTATS 2016, ICML 2018, IEEE Transactions on Information Theory, IEEE Transactions on Signal Processing (2 papers), Proceedings of the IEEE, IEEE Signal Processing Magazine.
Broader Impacts:
- One of the three graduate students supported by this grant is a woman.
- The PI developed (i) a new undergraduate course on Machine Learning: A Signal Processing Perspective; and (ii) the PI has developed material for a new graduate course on “High Dimensional Probability and Linear Algebra for Machine Learning” by teaching the material in special topics’ courses twice and developing it in the process (EE 520). The regular course is being proposed and will be taught starting Fall 2020.
- Short courses and tutorials (GIAN course in 2017 and tutorials at SPCOM 2018 and ICASSP 2017) were taught based on some of the work funded by this grant.
- The PI organized and lead a special issue for the Proceedings of the IEEE, and a mini-issue for IEEE Signal Processing Magazine; the PI also coedited a third issue for IEEE JSTSP. All three were on PCA, Robust PCA, and related topics.
Last Modified: 12/11/2019
Modified by: Namrata Vaswani
Please report errors in award information by writing to: awardsearch@nsf.gov.