CIF: Small: Mathematical Aspects of Sparse Recovery-Theory and Algorithms

这项研究背后的动机是通过提高稀疏信号重构算法的性能，使压缩感知领域的最新突破得到更广泛（和有效）的使用。压缩或稀疏感知是一种新的方法，当信号的支持点（所讨论的信号假定为非零值的点）是有限的时，可以从少量的测量中恢复模拟信号（信号重构）。稀疏信号是传统奈奎斯特采样中带限信号的对应物。这种方法的吸引力在于，实现“完美”重建所需的样本数量通常非常少，并且快速优化算法可以完成重建。这项研究计划的第一步将是找到利用有关信号支持性质的先验知识的方法。最终目标是开发算法方法（理论/实践），以帮助从业者在无线通信，机器学习，DNA微阵列和图像重建中出现的各种问题等应用中制定现实的假设。研究的重点是设计多项式重建算法，可以证明桥梁之间的差距差距稀疏测量密度比（S/MDR）恢复的当前国家的最先进的算法和最好的情况下，S/MDR接近1。具体而言，该地区目前最先进的方法在很大程度上缺乏成功。更广泛地说，目标是获得性能质量（复杂性，精度等）的理论保证。一些实际可行的优化算法。除了既定的目标，这项工作有可能创造强大的数学形式主义解决其他具有挑战性的基本优化问题。

The motivation behind this research is to enable broader (and valid) usage of recent breakthroughs in the field of compressed sensing by improving the performance of sparse signal reconstruction algorithms. Compressed or sparse sensing is a new way to recover an analog signal (signal reconstruction) from a small number of measurements when the signal's support - points where the signal in question assumes nonzero values - is finite. Sparse signals are the counterpart to band-limited signals in conventional Nyquist sampling. What makes this approach so attractive is that the number of samples required to achieve "perfect" reconstruction is generally very small, and fast optimization algorithms can accomplish reconstruction. The first step in this research program will be to find ways to exploit prior knowledge about the nature of the support of the signal. The ultimate goal is to develop algorithmic approaches (theoretical/practical) to aid practitioners in formulating realistic assumptions in applications ranging from wireless communications, machine learning, DNA micro arrays, and various problems arising in image reconstruction. The research focus is on designing polynomial reconstruction algorithms that could provably bridge the gap between sparsity to measurement density ratios (S/MDR) recoverable by the current state-of-the-art algorithms and the best possible situation where the S/MDR approaches 1. Specifically, the region where there has been a substantial lack of success for current state of the art approaches. More broadly, the objective is to obtain theoretical guarantees on the performance quality (complexity, precision etc.) of certain practically feasible optimization algorithms. Beyond the stated objectives, this work has the potential for creating powerful mathematical formalisms for solving other challenging fundamental optimization problems.