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

点击翻译按钮获取中文摘要

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.