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.