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

不适定和欠定的线性方程组出现在从医疗保健到信号处理的许多应用中。过去10年的大量研究已经证明，结构化？信号可以准确地恢复吗？，即使观测的数量少于信号的数量？维度。尽管现实信号中存在许多复杂结构，但结构化信号恢复的范围主要局限于稀疏度、低秩等基本结构。扩展结构的概念并提出有效的结构化信号恢复方案是信号处理和信息理论的主要开放挑战之一。在这个方向上的任何进展都可能影响许多应用领域，如磁共振成像（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.