CAREER: Coding Subspaces: Error Correction, Compression and Applications

在当今的技术世界中，海量的数据正以前所未有的规模不断地被生成、传输、接收、处理和存储。将数据表示为信息位块的经典方法不能满足下一代存储、计算和通信系统的不同需求，包括可伸缩性、效率和可靠性。该项目开发了一种在大规模连接的无线网络上传输数据的替代范例，方法是通过一种名为子空间编码的技术，将信息嵌入到称为子空间(即，向量空间中的线性代数对象)的数学结构中。虽然这些结构捕获了在广泛的信号处理应用中收集的数据的本质，但人们并不了解压缩的基本限制以及达到这些限制的实用和通用技术。这个项目描述了子空间域中纠错和压缩之间的自然二元性，并建议利用这种联系来为表现出某些属性的海量数据集开发显式和高效的压缩机制。这一跨学科项目与教育计划捆绑在一起，为各级学生提供了一个激励和创新的研究环境。此外，开展研讨会是积极拓展计划的一部分，目的是向高中生介绍数据科学和通信相关领域的概念，让他们接触到对未来的工作至关重要的职业。无线网络的规模正在迅速增长，变得越来越分层，并且变得越来越分散。包括点对点链路的信道估计和块编码在内的传统方法不能随着这种大规模网络的大小而适当地缩放。该项目提出，在这种情况下，模拟域中的子空间编码变得与跨网络传输信息相关。此外，压缩领域中的对偶问题是涉及大规模原始数据的广泛应用的核心，这些数据通常表现为低维结构，这需要低维子空间恢复和降维技术。该项目的具体目标概括如下：(1)提供一个全面的框架，包括一定的度量空间和模拟操作员信道，以非相干的方式研究无线网络的编码；(2)构造模拟操作员信道的子空间码并表征其性能；(3)开发在有约束观测的情况下的低秩子空间恢复技术；(4)表征低阶矩阵压缩的基本极限，并利用子空间码的对偶性来设计显式压缩机制；(5)发展子空间编码的分布式计算方案，以高效地计算在矩阵和子空间上操作的算法的结果，同时最小化延迟。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.