Provable and efficient algorithms for robust subspace learning and tracking
Date
2021-08
Authors
Narayanamurthy, Praneeth Kurpad
Major Professor
Advisor
Vaswani, Namrata
Hegde, Chinmay
Luo, Songting
Tian, Jin
Wang, Zhengdao
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Abstract
In the past decades, there has been an explosion in the amount of data that is generated. This calls for development of efficient algorithms to uncover useful information from massive datasets. Although several recent advances in computation allows for faster processing, efficient communication and storage and so on, it is the need of the hour to develop intelligent algorithms that minimize resource utilization, and does so in a near real-time fashion. A commonly observed theme in the Signal Processing and Machine Learning is to exploit the fact that most real-world (extremely high dimensional) data exhibits a simple, succinct, low-dimensional representation. In other words, the data lies close to some low-dimensional structure of the ambient space. In this thesis, we consider two such low-dimensional structures: sparsity and low-rank. Specifically, we develop provable algorithms for the problem of Subspace Tracking (ST) under several constraints. First we study robust ST wherein the data is corrupted by arbitrary outliers. Next, we consider the setting where part of the data is missing (due to issues in transmission or storage). Finally, we develop algorithms that also deal with distributed data.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
dissertation