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

框架生成器：用于近乎最优信号稀疏、传输和恢复的贪婪构造原理

• 批准号: 1412524
• 负责人: Bernhard Bodmann
• 金额: $ 22.92万
• 依托单位: University of Houston
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1412524&HistoricalAwards=false
• 关键词: Frame; builder; Greedy; construction; principles

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.

Bodmanndms-1412524最近几十年已经看到了高分辨率传感设备生成的数字化模拟数据的爆炸性增长，并通过通信基础架构传输。 例如，以MRI或CT扫描或共聚焦显微镜形式获得高分辨率数据，例如在医学成像中，以及作为高光谱卫星图像的与防御相关的成像。 在应用数学中的压缩传感的发展表明，令人惊讶的是，随机组织的测量值提供了一种减少传感器获取的数据量的方法，以调用非线性后处理阶段的成本。 来自压缩传感的随机策略也与生成代码和检查总和有关，该总和允许在传输数字化模拟信号时从稀疏错误中恢复。 但是，即使在最先进的数学理论层面上，随机感应和编码的编码也排除了在关键情况下所需的性能。 该项目提供了随机选择的替代方法：框架描述了用传感器获得的测量的结构，以逐步的增量方式构建。 为了实现可证明的绩效保证，每个步骤都根据“贪婪”优化原则进行。 该测量设计的主要应用是在计算机断层扫描区域中有限获取的图像恢复。 在有限的扫描范围内进行精确重建组织密度重建的能力具有几种潜在的优势，包括减少辐射剂量和缩短扫描时间。 更一般而言，根据此策略的有效解析信号与微阵列数据处理，运动分割以及许多其他数据密集型应用程序具有潜在的相关性。 相同的贪婪施工原理可以应用于数字化模拟数据的编码传输，这对于诸如互联网等通信系统很重要。 解决数据丢失的近乎最佳错误抑制的解决方案将影响跨Internet发送的流媒体的质量，或者在不可靠的环境中无线音频或视频通信的质量。 该项目的一部分可以在本科或研究生级研究中制定。 研究人员在该项目的过程中培训至少两名研究生和一名本科生。 预计学生将通过理论工作和计算机断层扫描的应用结合获得宝贵的知识。 压缩传感向我们展示了如何通过随机传感来减少带宽，这可以直接捕获可压缩信号的基本部分，以及通过将信号恢复的负担从传感器移动到数字后处理阶段。 相同的技术对于模型选择（例如子空间聚类和纠正稀疏误差，例如传输中的部分数据丢失）很有用。 但是，我们在信号获取和传输方面仍然面临着挑战性的未解决问题。 与实际情况相去甚远，与实际情况相去甚远。 此外，没有可行的已知测试可以保证随机结构的具体结果成功。 本项目解决了以下设置中对数据采集和传输的可证明性能保证的需求：（1）如果随机信号的源集中在子空间的结合附近，如何从源头的噪声样本中有效且可靠地识别这些子空间？ （2）如果人们在发送数字化模拟信号时期望通信失败，从而导致传输数据的丢失，那么如何编码信号以抑制数据丢失对重建的模拟信号的影响 - 最佳方式？ 该项目涉及凸优化理论，功能和数值分析以及框架理论的要素。 框架是一个（过度）完整的向量系列，可提供稳定的扩展。 框架理论对于传感和数字化的通信很重要，因为与正统基础相比，框架可以在框架向量之间结合线性依赖性，从而可以在其设计中灵活地进行灵活性，并提供了一种基本的误差校正方法。 直到最近，框架理论结果的艺术状态仍依赖于随机或群体代表性结构。 该项目着重于贪婪的建筑原则的近距离设计，这是受丹尼尔·斯皮尔曼（Daniel Spielman）与尼克希尔·斯里瓦斯塔瓦（Nikhil Srivastava）和亚当·马库斯（Adam Marcus）合作的技术的启发。 该技术具有强大的应用程序，如最近的简化 - tzafriri定理的简化证明，并在解决Kadison-Singer问题的解决中所示。 该项目的预期结果包括通过贪婪的方法构建框架，这些方法提供了（1）具有已知统计数据的信号的稀疏扩展以及（2）与随机结构性能相匹配的编码传输的错误校正功能。 这些构造方法应用于利息区域计算机断层扫描，这是一种有意的数据减少策略，其中仅使用X射线，该X射线通过正在成像的器官附近，从而减少了整体辐射剂量。 预计，贪婪方法在框架设计中的成功实施还会对涉及在噪声存在下传输或解释的所有任务产生重大影响。 研究人员在该项目的过程中培训至少两名研究生和一名本科生。

项目成果

Binary Parseval frames from group orbits

来自群轨道的二元帕塞瓦尔框架

• DOI: 10.1016/j.laa.2018.07.016
• 发表时间: 2018
• 期刊: Linear Algebra and its Applications
• 影响因子: 1.1
• 作者: Mendez, Robert P.;Bodmann, Bernhard G.;Baker, Zachery J.;Bullock, Micah G.;McLaney, Jacob E.
• 通讯作者: McLaney, Jacob E.