CIF: Small: Approximate Message Passing for Systems with Linear Mixing and Randomization

当今许多工程和科学问题的基本挑战是找到易于处理的方法来处理大规模、复杂的非线性系统。这项研究考虑了具有线性混合的大系统，其中系统组件通过小的，线性的扰动的集合相互作用。对于这样的系统，该研究研究了一种有前途的新型算法，称为广义近似消息传递（GAMP），它利用线性混合相互作用的本质，迭代地将大规模问题分解为更小、更容易处理的问题。GAMP方法提供了一个系统的程序，适用于大量的系统，这些系统在计算上可扩展到非常高的维度，并允许在某些高维随机系统的情况下进行易于处理的数学分析。因此，GAMP算法的潜力是深远的，研究探索了不同领域的应用，包括蜂窝无线系统的调度、图像恢复、模式识别和神经网络连接检测。GAMP方法是基于大的、密集的图上的循环信念传播的高斯近似和二次近似。所得到的算法是一个通用的，但计算简单的迭代过程，它在基于系统的局部行为的标量优化和估计操作之间交替，以及捕获系统组件之间相互作用的线性变换。该研究的理论组成部分是描述算法的渐近行为，收敛性和最优性，以及对线性和非线性相互作用混合系统的扩展。该研究将利用优化、图形模型、数值方法和随机系统等更广泛领域的工具并做出贡献。

A fundamental challenge in many engineering and science problems today is to find tractable methods to handle large scale, complex nonlinear systems. This research considers large systems with linear mixing, where the system components interact through aggregates of small, linearizable perturbations. For such systems, the research investigates a promising new class of algorithms called generalized approximate message passing (GAMP) that exploits the nature of the linear mixing interactions to iteratively decompose large-scale problems into smaller, more tractable, problems. The GAMP methodology provides a systematic procedure applicable to a large class of systems that is computationally scalable to very high dimensions and admits a tractable mathematical analysis in the case of certain high-dimensional random systems. The potential for the GAMP algorithm is thus far reaching, and the research explores applications in diverse fields including scheduling in cellular wireless systems, image recovery, pattern recognition and detection of connectivity in neural networks.The GAMP methodology is based on a Gaussian and quadratic approximations of loopy belief propagation on large, dense graphs. The resulting algorithm is a general, but computationally simple, iterative procedure that alternates between scalar optimization and estimation operations based on the local behavior of the system, along with linear transforms that capture the interactions between system components. The theoretical components of the research are to characterize the algorithm's asymptotic behavior, convergence and optimality along with developing extensions to the systems with mixes of linear and nonlinear interactions. The research will leverage tools from and contribute to the broader fields of optimization, graphical models, numerical methods and random systems.