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.