Frame builder: Greedy construction principles for near-optimal signal sparsification, transmission and recovery

在过去的几十年里，高分辨率传感设备产生的数字化模拟数据量爆炸式增长，并通过通信基础设施传输。获得高分辨率数据，例如在MRI或CT扫描或共聚焦显微镜形式的医学成像中，以及在国防相关成像中，如高光谱卫星图像。应用数学中压缩感知的发展向我们表明，令人惊讶的是，随机组织的测量提供了一种方法，以调用非线性后处理阶段为代价，减少传感器获取的数据量。来自压缩感知的随机化策略也与生成代码和校验和相关，这些代码和校验和允许在传输数字化模拟信号时从稀疏错误中恢复。然而，即使在最先进的数学理论水平上，随机感知和编码也排除了在关键情况下所需的性能保证。该项目提供了一种随机选择的替代方案：框架描述了传感器获得的测量结构，以一步一步、增量的方式构建。为了实现可证明的性能保证，每一步都按照“贪婪”优化原则进行。该测量设计的主要应用是在感兴趣区域计算机断层扫描中从有限采集中恢复图像。在有限扫描的情况下，在感兴趣的区域进行精确的组织密度重建的能力具有几个潜在的优势，包括减少辐射剂量和缩短扫描时间。更一般地说，根据这种策略对信号的有效解析对于微阵列数据处理、运动分割和许多其他数据密集型应用具有潜在的相关性。同样的贪婪构造原理也可以应用于数字化模拟数据的编码传输，这对互联网等通信系统非常重要。对数据丢失的近乎最优错误抑制的解决方案将影响通过互联网发送的流媒体的质量，或者在不可靠的环境中无线音频或视频通信的质量。这个项目的部分内容可以在本科或研究生阶段的研究中制定。研究者在这个项目的过程中至少训练两名研究生和一名本科生。期望学生通过理论工作与计算机断层扫描的应用相结合，获得有价值的知识。压缩感知向我们展示了如何通过随机感知来减少带宽，随机感知直接捕获可压缩信号的基本部分，并将信号恢复的负担从传感器转移到数字后处理阶段。同样的技术对于子空间聚类等模型选择和纠正传输中的部分数据丢失等稀疏错误也很有用。然而，在信号采集和传输方面，我们仍然面临着一些具有挑战性的问题。要使随机构造获得近乎确定的成功，所需的相关维度之间的差距往往与实际情况相去甚远。此外，没有可行的已知测试来保证随机构造的具体结果是成功的。本项目解决了在以下情况下对数据采集和传输的可证明性能保证的需求：(1)如果随机信号的源集中在子空间的并集附近，如何从源的噪声样本中有效可靠地识别这些子空间？(2)如果在发送数字化模拟信号时预计通信失败，导致传输数据的一部分丢失，那么如何对信号进行编码，以便以接近最佳的方式抑制数据丢失对重构模拟信号的影响？该项目涉及凸优化理论、泛函和数值分析以及框架理论的元素。坐标系是一个（过）完备的向量族，它提供稳定的展开。帧理论对传感和数字化通信很重要，因为与标准正交基相反，帧可以在帧向量之间包含线性依赖关系，这允许其设计的灵活性，并提供纠错的基本方法。直到最近，最先进的框架理论结果要么依赖于随机结构，要么依赖于群表示结构。该项目的重点是通过贪婪的构造原则逐步设计接近最佳的框架，其灵感来自Daniel Spielman与Nikhil Srivastava和Adam Marcus合作开发的技术。这种技术有强大的应用，正如最近对布尔甘-查夫里定理的简化证明和卡迪逊-辛格问题的解决所显示的那样。该项目的预期结果包括通过贪婪方法构建帧，该方法提供(1)具有已知统计量的信号的稀疏扩展和(2)与随机构造性能相匹配的编码传输的纠错能力。这些构造方法应用于感兴趣区域计算机断层扫描，这是一种有意的数据减少策略，其中只使用经过被成像器官附近的x射线，从而减少总体辐射剂量。贪婪方法在帧设计中的成功实施也有望对所有涉及在存在噪声的情况下传输或解释模拟信号的任务产生重大影响。研究者在这个项目的过程中至少训练两名研究生和一名本科生。

BodmannDMS-1412524 The last decades have seen an explosive growth in the amount of digitized analog data being generated by high-resolution sensing devices and transmitted by communications infrastructure. High-resolution data is acquired for example in medical imaging in the form of MRI or CT scans or confocal microscopy, and in defense-related imaging as hyperspectral satellite images. The development of compressed sensing in applied mathematics has shown us that, surprisingly, randomly organized measurements provide a means to reduce the amount of data acquired by the sensor at the cost of invoking a nonlinear post-processing stage. The randomization strategies from compressed sensing are also relevant for generating codes and check sums that permit the recovery from sparse errors when transmitting a digitized analog signal. However, even at the level of state-of-the-art mathematical theory, random sensing and encoding precludes performance guarantees needed in critical situations. This project provides an alternative to random choice: Frames, which describe the structure of the measurements obtained with a sensor, are built in a step-by-step, incremental fashion. In order to realize provable performance guarantees, each step proceeds according to "greedy" optimization principles. A main application of this measurement design is image recovery from limited acquisition in region-of-interest computed tomography. The ability to perform accurate reconstruction of tissue density in a region of interest with limited scanning presents several potential advantages, including the reduction of radiation dose and the shortening of scanning time. More generally, the efficient parsing of signals according to this strategy has potential relevance for microarray data processing, motion segmentation, and many other data-intensive applications. The same greedy construction principles can be applied to the encoded transmission of digitized analog data, which is important for communication systems such as the internet. The solution to near-optimal error suppression for data loss would impact the quality of streaming media sent across the internet, or of wireless audio or video communications in unreliable environments. Parts of this project can be formulated at undergraduate or graduate-level research. The investigator trains at least two graduate students and one undergraduate student in the course of this project. The students are expected to gain valuable knowledge through the combination of theoretical work and the application to computed tomography. Compressed sensing has shown us how to reduce bandwidth by randomized sensing, which captures the essential part of a compressible signal directly, and by moving the burden of signal recovery from the sensor to a digital post-processing stage. The same techniques are useful for model selection such as subspace clustering and for correcting sparse errors such as partial data loss in transmissions. However, we still face challenging unresolved problems in signal acquisition and transmission. The gap between the relevant dimensions required to give near-certain success of a random construction is often far removed from practical situations. Moreover, there is no feasible known test that guarantees that a concrete outcome of a random construction is successful. This project addresses the need for provable performance guarantees of data acquisition and transmission in the following settings: (1) If a source for random signals concentrates near a union of subspaces, how can these subspaces be identified efficiently and reliably from noisy samples of the source? (2) If one expects communication failures when sending a digitized analog signal, resulting in a lost portion of the transmitted data, then how can the signal be encoded in order to suppress the impact of the data loss on the reconstructed analog signal in a near-optimal way? The project involves elements from convex optimization theory, functional and numerical analysis, and frame theory. A frame is an (over)complete family of vectors that provides stable expansions. Frame theory is important for sensing and digitized communications because in contrast to orthonormal bases, frames can incorporate linear dependencies between frame vectors, which allows for flexibility in their design and provides a fundamental method of error correction. Until recently, the state of the art of frame theoretic results relied on either randomized or group-representation constructions. This project focuses on an incremental, step-by-step design of near-optimal frames by greedy construction principles that are inspired by a technique developed by Daniel Spielman in works with Nikhil Srivastava and Adam Marcus. This technique has powerful applications, as shown in the recent simplified proof of the Bourgain-Tzafriri theorem and in the resolution of the Kadison-Singer problem. The expected outcomes of the project include the construction of frames by greedy methods that provide (1) sparse expansions for signals with known statistics and (2) error-correction capabilities for encoded transmissions that match the performance of randomized constructions. These construction methods are applied to region-of-interest computed tomography, an intentional data reduction strategy in which only X-rays are used that pass in the vicinity of an organ that is being imaged, thereby reducing the overall radiation dose. The successful implementation of greedy methods in frame design is also expected to have a significant impact on all tasks that involve analog signals being transmitted or interpreted in the presence of noise. The investigator trains at least two graduate students and one undergraduate student in the course of this project.