Back to search

Georgia Institute of Technology

Subspace learning by randomized sketching

Abstract

dc:description.abstract

High dimensional data is often accompanied by inherent low dimensionality that can be leveraged to design scalable machine learning and signal processing algorithms. Developing efficient computational frameworks that take advantage of the underlying structure in the data is crucial. In this thesis, we consider a particular form of inherent low dimensionality in data: subspace models. In many applications, data is known to lie close to a low dimensional subspace. The underlying subspace itself may or may not be known a priori. Incorporating this structure into data acquisition systems and algorithms can aid in scalability. We first consider two specific applications in the field of array signal processing where subspace priors on the data are commonly used. For both these applications, we develop algorithms that require a number of measurements that scale with only the dimension of the underlying subspace. In doing so, we show that arrays demand dimensionality reduction maps that can operate on individual subsets or blocks of data at a time, without having access to other blocks. Inspired by such block constraints, we consider more general problems in numerical linear algebra where data has a natural partition into blocks. This is common in applications with distributed or decentralized data. We study the problems of sketched ridge regression and sketched matrix multiplication under this constraint and give sample optimal theoretical guarantees on block diagonal sketching matrices. Extending the block model to low-rank matrix sensing, we then study the problem of recovering a low-rank matrix from compressed observations of each column. While each column itself is compressed to a point that is beyond recovery, we leverage their joint structure to recover the matrix as a whole. To do so, we establish a new framework to design estimators of low-rank matrices that obey the constraints imposed by different observation models. Finally, we extend our framework of designing low rank matrix estimators to the application of blind deconvolution. We provide a novel estimator that enjoys uniform recovery guarantees over the entire signal class while being sample optimal.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Electrical and Computer Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Srinivasa, Rakshith
Advisor dc:contributor.advisor
  • Romberg, Justin
Committee members dc:contributor.committeemember
  • Davenport, Mark
  • Lee, Kiryung
  • Koltchinskii, Vladimir
  • Vempala, Santosh

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/64177

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Srinivasa, Rakshith. Subspace learning by randomized sketching. Doctoral thesis, Georgia Institute of Technology, 2020. http://hdl.handle.net/1853/64177