Approximate-message passing (AMP) algorithms have become an important element of high-dimensional statistical inference, mostly due to their adaptability and concentration properties, the state evolution (SE) equations. This is demonstrated by the growing number of new iterations proposed for increasingly complex problems, ranging from multi-layer inference to low-rank matrix estimation with elaborate priors. In this paper, we address the following questions: is there a structure underlying all AMP iterations that unifies them in a common framework? Can we use such a structure to give a modular proof of state evolution equations, adaptable to new AMP iterations without reproducing each time the full argument ? We propose an answer to both questions, showing that AMP instances can be generically indexed by an oriented graph. This enables to give a unified interpretation of these iterations, independent from the problem they solve, and a way of composing them arbitrarily. We then show that all AMP iterations indexed by such a graph admit rigorous SE equations, extending the reach of previous proofs, and proving a number of recent heuristic derivations of those equations. Our proof naturally includes non-separable functions and we show how existing refinements, such as spatial coupling or matrix-valued variables, can be combined with our framework.


翻译:近似信息传递( AMP) 算法已成为高维统计推导的一个重要要素, 主要是因为其适应性和集中性, 国家进化( SE) 方程式。 这表现在为日益复杂的问题提出了越来越多的新的迭代, 从多层次推论到低层次矩阵估算, 加上详细的前科。 在本文中, 我们处理以下问题: 是否所有AMP迭代法都有一个结构, 将其统一在一个共同框架内? 我们能否使用这样一个结构来提供国家进化方程式的模块化证明, 适应新的 AMP迭代, 而不在每次重复全部论证的情况下进行新的迭代? 我们提议对这两个问题的答复, 表明AMP 例可以通过一个方向图表进行通用化的索引。 这使得能够对这些迭代法进行统一解释, 独立于它们解决的问题, 以及任意地将它们组合成一种方式。 我们然后表明, 所有通过这种图形指数指数指数指数的增缩的AMPeration 都能够接受严格的 SE方程式, 扩大先前证据的覆盖范围, 并证明最近一系列的超常态推算, 我们自然地展示了这些变式的矩阵的模型。

0
下载
关闭预览

相关内容

图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
39+阅读 · 2020年8月22日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
已删除
将门创投
8+阅读 · 2018年10月31日
Arxiv
0+阅读 · 2021年11月16日
Arxiv
7+阅读 · 2021年10月19日
VIP会员
相关资讯
已删除
将门创投
8+阅读 · 2018年10月31日
Top
微信扫码咨询专知VIP会员