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

BodmannDMS-1412524在过去几十年中见证了由高分辨率传感设备生成并通过通信基础设施传输的数字化模拟数据量的爆炸性增长。例如，在以MRI或CT扫描或共焦显微镜形式的医学成像中获取高分辨率数据，并且在作为高光谱卫星图像的国防相关成像中获取高分辨率数据。应用数学中压缩感知的发展向我们表明，令人惊讶的是，随机组织的测量提供了一种减少传感器获取的数据量的方法，代价是调用非线性后处理阶段。来自压缩感测的随机化策略也与生成代码和校验和相关，所述代码和校验和允许在传输数字化模拟信号时从稀疏错误中恢复。然而，即使在最先进的数学理论水平上，随机检测和编码也排除了关键情况下所需的性能保证。这个项目提供了随机选择的另一种选择：帧描述了通过传感器获得的测量的结构，以一步一步、递增的方式构建。为了实现可证明的性能保证，每一步都按照贪婪的优化原则进行。这种测量设计的一个主要应用是在感兴趣区域计算机断层扫描中从有限采集中恢复图像。在有限扫描的情况下准确重建感兴趣区域的组织密度的能力表现出几个潜在的优势，包括减少辐射剂量和缩短扫描时间。更一般地，根据该策略的信号的有效解析对于微阵列数据处理、运动分割和许多其他数据密集型应用具有潜在的相关性。同样的贪婪构造原理可以应用于数字化模拟数据的编码传输，这对于诸如因特网的通信系统是重要的。针对数据丢失的近最佳差错抑制的解决方案将影响通过互联网发送的流媒体的质量，或者在不可靠的环境中的无线音频或视频通信的质量。这个项目的部分内容可以在本科生或研究生水平的研究中制定。在这个项目的过程中，研究人员至少培训了两名研究生和一名本科生。学生们希望通过理论工作和计算机断层扫描的应用相结合来获得有价值的知识。压缩感知向我们展示了如何通过随机感知来减少带宽，随机感知直接捕获可压缩信号的基本部分，并将信号恢复的负担从传感器转移到数字后处理阶段。同样的技术可用于模型选择，例如子空间聚类，以及用于纠正稀疏错误，如传输中的部分数据丢失。然而，我们在信号采集和传输方面仍然面临着具有挑战性的悬而未决的问题。相关维度之间的差距往往与实际情况相去甚远，这是让随机建筑几乎肯定成功所必需的。此外，目前还没有可行的已知测试来保证随机施工的具体结果是成功的。该项目解决了在以下情况下数据采集和传输的可证明的性能保证的需求：(1)如果随机信号源集中在子空间的并集附近，如何有效和可靠地从源的噪声样本中识别这些子空间？(2)如果在发送数字化的模拟信号时预期通信故障，导致传输的数据的丢失部分，那么如何对信号进行编码，以便以接近最佳的方式抑制数据丢失对重建的模拟信号的影响？该项目涉及凸优化理论、泛函和数值分析以及框架理论的元素。框架是提供稳定展开的(超过)完备向量族。帧理论对于传感和数字化通信很重要，因为与正交基相比，帧可以合并帧向量之间的线性依赖关系，这允许在其设计中灵活并提供纠错的基本方法。直到最近，最先进的框架理论结果要么依赖于随机结构，要么依赖于群表示。这个项目的重点是通过贪婪的建筑原则逐步递增地设计近乎最佳的框架，这些原则的灵感来自丹尼尔·斯皮尔曼在与尼基尔·斯里瓦斯塔瓦和亚当·马库斯合作开发的技术。这种方法有很强的应用价值，如最近Bourain-Tzafriri定理的简化证明和Kadison-Singer问题的解决。该项目的预期结果包括通过贪婪的方法构建帧，这种方法提供(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.