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.