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

CIF：小：具有线性混合和随机化的系统的近似消息传递

• 批准号: 1116589
• 负责人: Sundeep Rangan
• 金额: $ 48.15万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1116589&HistoricalAwards=false
• 关键词: CIF; Small; Approximate; Message; Passing

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.

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