Award Abstract # 1526870
CIF: Small: Online Algorithms for Streaming Structured Big-Data Mining

NSF Org: CCF
Division of Computing and Communication Foundations
Recipient: IOWA STATE UNIVERSITY OF SCIENCE AND TECHNOLOGY
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: FY 2015 = $442,385.00
History of Investigator:
  • Namrata Vaswani (Principal Investigator)
    namrata@iastate.edu
Recipient Sponsored Research Office: Iowa State University
1350 BEARDSHEAR HALL
AMES
IA  US  50011-2103
(515)294-5225
Sponsor Congressional District: 04
Primary Place of Performance: Iowa State University
3121 Coover Hall
Ames
IA  US  50011-2207
Primary Place of Performance
Congressional District:
Unique Entity Identifier (UEI): DQDBM7FGJPC5
Parent UEI: DQDBM7FGJPC5
NSF Program(s): Comm & Information Foundations
Primary Program Source: 01001516DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 7923, 7936, 9150, 9251
Program Element Code(s): 779700
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.

(Showing: 1 - 10 of 19)
J. Zhan*, B. Lois*, H. Guo*, and N. Vaswani "Online (and Offline) Robust PCA: NovelAlgorithms and Correctness Results" Proc. Intnl. Conf. Artificial Intelligence and Statistics (AISTATS) , 2016 , p.Proc. Int
J Zhan, B Lois, H Guo, N Vaswani "Online (and offline) robust PCA: Novel algorithms and performance guarantees" AISTATS , 2016
N. Vaswani and H. Guo "Correlated-PCA: Principal Components' Analysis when Data and Noise are Correlated" Proc. Neural Info. Proc. Systems (NIPS) , 2016
N. Vaswani and J. Zhan "Recursive Recovery of Sparse Signal Sequences From Compressive Measurements: A Review" IEEE Transactions on Signal Processing , v.64 , 2016 , p.3523 10.1109/TSP.2016.2539138
N. Vaswani and P. Narayanamurthy "Static and Dynamic Robust Principal Component Analysis (PCA) and Matrix Completion: A Review" Proceedings of the IEEE , v.106 , 2018 10.1109/JPROC.2018.2844126
N. Vaswani, P. Narayanamurthy "Finite Sample Guarantees for PCA in Non-Isotropic and Data-Dependent Noise" Proceedings of Allerton Conference , 2018
N. Vaswani, P. Narayanamurthy* "PCA in Sparse Data-Dependent Noise" IEEE Intl. Symp. Info. Theory (ISIT) , 2018
N Vaswani, S Nayer, YC Eldar "Low-Rank Phase Retrieval" IEEE Transactions on Signal Processing , v.65 , 2017 , p.4059 10.1109/TSP.2017.2684758
N. Vaswani, T. Bouwmans, S. Javed, P. Narayanamurthy "Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery" IEEE Signal Processing Magazine , v.35 , 2018 10.1109/MSP.2018.2826566
P. Narayanamurthy and N. Vaswani "Provable Dynamic Robust PCA or Robust Subspace Tracking" IEEE Trans. Information Theory , 2018 10.1109/TIT.2018.2872023
P. Narayanamurthy*, N. Vaswani "Nearly Optimal Robust Subspace Tracking: U A Unified Approach" Data Science Workshop (DSW) , 2018
(Showing: 1 - 10 of 19)

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.

Print this page

Back to Top of page