CIF: Small: Collaborative Research: Towards universal signal recovery algorithms

不适定和欠定线性方程组出现在从医疗保健到信号处理的许多应用中。过去十年的大量研究已经证明了这一点。结构？信号可以恢复吗？准确吗？即使观测值的数量小于信号的数量尺寸.尽管在现实世界的信号中存在许多复杂的结构，结构化信号恢复的范围主要仍然局限于基本结构，如稀疏性和低秩。扩展结构的概念，并提出有效的恢复方案，这种结构化的信号是在信号处理和信息理论的主要开放的挑战之一。这方面的任何进展都可能影响许多应用领域，如磁共振成像（MRI）。这项研究涉及开发一种新的和变革性的方法来解决以下问题的结构化信号恢复：（i）是否存在实用和有效的信号恢复算法，可以恢复信号从其欠采样的线性测量集很少或没有先验信息的结构？这种算法在信息论中被称为通用算法。(ii)这些通用算法的基本性能限制是什么？通用方案已经被开发出来，并且在其他应用中很受欢迎。例如，通用的压缩算法，如无所不在的Lempel-Ziv码实现了最佳性能，而不需要任何关于数据分布的知识。最近的结果，由PI和其他人，理论上证明了通用信号恢复算法的存在。本研究调查的存在和基本性能限制的计算效率的通用恢复算法。

Ill-posed and underdetermined systems of linear equations arise in many applications ranging from healthcare to signal processing. Extensive research in the last decade has proven that ?structured? signals can be recovered ?accurately?, even if the number of observations is less than the signals? dimensions. Despite the existence of many complex structures in real-world signals, the scope of structured signal recovery has mainly remained limited to basic structures, such as sparsity and low-rankness. Extending the notion of structure and proposing efficient recovery schemes for such structured signals is one of the major open challenges in signal processing and information theory. Any progress in this direction can potentially impact many application areas such as magnetic resonance imaging (MRI). This research involves developing a novel and transformative approach to structured signal recovery by addressing the following questions: (i) Do there exist practical and efficient signal recovery algorithms that can recover signals from their undersampled sets of linear measurements with little or no prior information about their structures? Such algorithms are referred to as universal algorithms in information theory. (ii) What are the fundamental performance limits of such universal algorithms? Universal schemes have been developed and are popular in other applications. For instance, universal compression algorithms such as the omnipresent Lempel-Ziv code achieve the optimal performance without requiring any knowledge about the distribution of the data. Recent results, by the PIs and others, theoretically prove the existence of universal signal recovery algorithms. This research investigates the existence and fundamental performance limits of computationally efficient universal recovery algorithms.