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

点击翻译按钮获取中文摘要

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.