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

当今许多工程和科学问题中的一个基本挑战是找到处理大规模复杂非线性系统的易处理方法。 本研究考虑线性混合的大系统，其中系统组件通过聚集的小的，线性化的扰动相互作用。 对于这样的系统，该研究调查了一类有前途的新算法，称为广义近似消息传递（GAMP），利用线性混合相互作用的性质，迭代地将大规模问题分解为更小，更容易处理的问题。 GAMP的方法提供了一个系统的程序，适用于一个大类的系统，计算可扩展到非常高的维度，并承认在某些高维随机系统的情况下，一个易于处理的数学分析。 GAMP算法的潜力是深远的，研究探索在不同领域的应用，包括蜂窝无线系统中的调度，图像恢复，模式识别和检测的连接在neural networks.The 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.