Iterative Signal Recovery Algorithms --- A Unified View of Turbo and Message-Passing Approaches

在过去的几年中，已经设计了大量用于压缩感知的信号恢复算法。最有效的是那些基于迭代处理的，特别是IHT和AMP及其变体。基本上，可以区分两种不同的迭代处理原理：Turbo原理和消息传递原理。在Turbo方案中，信息（通常）在两个块之间传递；每个组件内的处理在每个信号块（矢量）上联合完成。相反，消息传递利用具有（通常）大量节点的图形模型。信息在所有连接的节点（向量的元素）之间传递；处理在每个节点本地完成。因此，Turbo处理中的全局视图与消息传递中的本地视图进行比较。尽管AMP是从MP视图衍生出来的，但最终的算法可以更好地归类为Turbo原理。最近提出的信号恢复方法，如TSR、OAMP、VAMP和IMS，立即遵循Turbo原理。这两个世界有惊人的相似之处，但也有显著的差异。文献中缺乏对这些算法的统一看法。这个提议的主要目标是将Turbo和MP世界更紧密地联系在一起。必须找出共同的原则和根本的区别。通过对现有的各种变体进行深入的分析和分类，可以加深对变体的理解。因此，我们更感兴趣的是工程的角度，而不是大系统的分析和数学的观点；算法和概念应该从工程的角度重新解释和理解。将讨论将待解决的问题划分为两个子问题的问题，并对两个子问题进行迭代。因此，性能和复杂性之间的权衡是特别重要的。将研究不同算法在数字通信应用中的效率。虽然对实值和离散值稀疏信号的分析和合成将贯穿始终，但更强的重点将放在预期应用的需求（例如，不需要或不可能完美恢复）和性能度量（例如，误码率）上。

Over the last years, plenty of signal recovery algorithms for compressed sensing have been devised. The most effective are those based on iterative processing, specifically IHT and AMP and its variants. Basically, two different philosophies of iterative processing can be distinguished: the Turbo principle and the message passing principle. In Turbo schemes, information is passed between (typically) two blocks; the processing within each component is done jointly over each signal block (vector). Conversely, message passing utilizes a graphical model with (typically) a huge number of nodes. Information is passed between all connected nodes (elements of the vector); the processing is done locally in each node. Hence, the global view in Turbo processing compares with the local view in message passing.Even though AMP is derived from the MP view, the final algorithm can be better categorized under the Turbo principle. Very recently proposed signal recovery approaches like TSR, OAMP, VAMP, and IMS immediately follow the Turbo principle. Both worlds show striking similarities but also significant differences. A unified view of these algorithms is missing in the literature.The main objective of this proposal is to bring the Turbo and MP world closer together. The common principles and fundamental differences have to be worked out. Via a thorough analysis and categorization of the diverse variants meanwhile available, a deeper understanding shall be developed. Thereby, we are more interested in the engineering perspective rather than the large-system analysis and mathematical view; the algorithms and concepts should be reinterpreted and understood from the engineering perspective. The question of other partitionings of the problem to be solved into two subproblems over which iteration is done will be addressed. Thereby the tradeoff between performance and complexity is of particular interest. The efficiency of the different algorithms in applications from digital communications will be studied. Although analysis and synthesis will be done throughout for real-valued and discrete-valued sparse signals, stronger focus will be put on demands (e.g., no perfect recovery is required or possible) and performance measures (e.g., bit error rates) for the intended applications.