CAREER: Coding Subspaces: Error Correction, Compression and Applications

在当今的技术世界中，以前所未有的规模不断产生、传输、接收、处理和存储大量数据。将数据表示为信息位块的经典方法无法满足下一代存储、计算和通信系统的各种需求，包括可伸缩性、效率和可靠性。该项目通过一种称为子空间编码的技术，提出将信息嵌入到称为子空间（即向量空间中的线性代数对象）的数学结构中的方法，为跨大规模连接的无线网络传输数据开发了另一种范例。虽然这些结构在广泛的信号处理应用中捕获了收集数据的本质，但压缩的基本限制以及实现这些限制的实用和通用技术尚不清楚。该项目描述了子空间领域中纠错和压缩之间的自然对偶性，并建议利用这种联系为具有某些属性的大量数据集开发明确而有效的压缩机制。这个跨学科的项目与一个教育计划联系在一起，为各级学生提供了一个激励和创新的研究环境。此外，为了向高中生介绍与数据科学和通信相关领域的概念，使他们接触到对未来劳动力至关重要的职业，作为积极推广计划的一部分，开发了讲习班。无线网络的规模正在迅速扩大，层次越来越分明，分布也越来越分散。传统的点对点链路信道估计和分组编码等方法无法适应如此庞大网络的规模。该项目提出，模拟域的子空间编码与在这种情况下跨网络传输信息相关。此外，压缩领域的对偶问题对于涉及大规模原始数据的广泛应用至关重要，这些数据通常表现为低维结构，这需要低维子空间恢复和降维技术。该项目的具体目标总结如下：(1)提供一个全面的框架，包括一定的度量空间和模拟运营商信道，以非相干方式研究无线网络的编码；(2)构建模拟运营商信道的子空间码，并对其性能进行表征；(3)开发基于受限观测的低秩子空间恢复技术；(4)描述低秩矩阵压缩的基本限制，并利用与子空间码的对偶性设计显式压缩机制；(5)开发子空间编码分布式计算方案，以有效地计算在矩阵和子空间上运行的算法的结果，同时最小化延迟。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.