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

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