CAREER: Coding Subspaces: Error Correction, Compression and Applications

In today’s technological world, an enormous amount of data is being constantly generated, transmitted, received, processed, and stored at an unprecedented scale. The classical approach of representing data as blocks of information bits falls short of addressing diverse requirements, including scalability, efficiency, and reliability, of the next generation storage, computation, and communication systems.

This project develops an alternative paradigm for transmission of data across massively connected wireless networks by proposing methods to embed the information into mathematical constructs called subspaces (i.e., linear-algebraic objects in a vector space), via a technique called subspace coding. While these structures capture the essence of gathered data in a wide range of signal processing applications, fundamental limits of compression as well as practical and universal techniques to attain these limits are not understood.

This project characterizes a natural duality between error correction and compression in the subspace domain and proposes to leverage this connection in order to develop explicit and efficient compression mechanisms for massive data sets that exhibit certain properties. This interdisciplinary project is tied with an education plan and provides a stimulating and innovative research environment for students at all levels.

Furthermore, workshops are developed as part of an active outreach program in order to introduce high school students to concepts in fields related to data science and communications, exposing them to careers essential to tomorrow’s workforce.

Wireless networks are rapidly growing in size, are becoming more hierarchical, and are becoming increasingly distributed. Conventional methods including channel estimation of point-to-point links and block coding do not properly scale with the size of such massive networks. This project proposes that subspace coding in the analog domain becomes relevant for conveying information across networks in such a scenario.

Furthermore, the dual problem in the compression domain is central to a wide range of applications involving large-scale raw data, often exhibiting low-dimensional structures, which require techniques for low-dimensional subspace recovery and dimensionality reduction. The specific objectives of this project are summarized as follows: (1) Provide a comprehensive framework, including a certain metric space and an analog operator channel, to study coding for wireless networks in a non-coherent fashion; (2) Construct subspace codes for analog operator channels and characterize their performance; (3) Develop techniques for low-rank subspace recovery given constrained observations; (4) Characterize fundamental limits on compression of low-rank matrices and leverage the duality with subspace codes to design explicit compression mechanisms; (5) Develop schemes for subspace-coded distributed computation to efficiently compute the outcome of algorithms operating over matrices and subspaces while minimizing the delay.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.