Sufficient-Statistic Memory AMP

2021-12-31 · Lei Liu, Shunqi Huang, Yuzhi Yang, Zhaoyang Zhang, Brian M. Kurkoski

Approximate message passing (AMP) type algorithms have been widely used in the signal reconstruction of certain large random linear systems. A key feature of the AMP-type algorithms is that their dynamics can be correctly described by state evolution. While state evolution is a useful analytic tool, its convergence is not guaranteed. To solve the convergence problem of the state evolution of AMP-type algorithms in principle, this paper proposes a sufficient-statistic memory AMP (SS-MAMP) algorithm framework under the conditions of right-unitarily invariant sensing matrices, Lipschitz-continuous local processors and the sufficient-statistic constraint (i.e., the current message of each local processor is a sufficient statistic of the signal vector given the current and all preceding messages). We show that the covariance matrices of SS-MAMP are L-banded and convergent, which is an optimal framework (from the local MMSE/LMMSE perspective) for AMP-type algorithms given the Lipschitz-continuous local processors. Given an arbitrary MAMP, we can construct an SS-MAMP by damping, which not only ensures the convergence of the state evolution, but also preserves the orthogonality, i.e., its dynamics can be correctly described by state evolution. As a byproduct, we prove that the Bayes-optimal orthogonal/vector AMP (BO-OAMP/VAMP) is an SS-MAMP. As an example, we construct a sufficient-statistic Bayes-optimal MAMP (SS-BO-MAMP) whose state evolution converges to the minimum (i.e., Bayes-optimal) mean square error (MSE) predicted by replica methods when it has a unique fixed point. In addition, the MSE of SS-BO-MAMP is not worse than the original BO-MAMP. Finally, simulations are provided to support the theoretical results.

📄 PDF Abstract BibTeX arXiv:2112.15327

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

AMP Based on the understanding that the flat local minima of the empirical risk cause the model to generalize better. Adversarial Model Perturbation (AMP) improves generalization via…

Sufficient Statistic Memory Approximate Message Passing

2022-06-23 · Lei Liu, Shunqi Huang, Brian M. Kurkoski

Vocal Bursts Type Prediction

Episodic memory for continual model learning

2017-12-04 · David G. Nagy, Gergő Orbán

Both the human brain and artificial learning agents operating in real-world or comparably complex environments are faced with the challenge of online model selection. In principle this challenge can be overcome: hierarch…

Bayesian Inference model Model Selection

Online Learning: Sufficient Statistics and the Burkholder Method

2018-03-20 · Dylan J. Foster, Alexander Rakhlin, Karthik Sridharan

We uncover a fairly general principle in online learning: If regret can be (approximately) expressed as a function of certain "sufficient statistics" for the data sequence, then there exists a special Burkholder function…

Trimming the Independent Fat: Sufficient Statistics, Mutual Information, and Predictability from Effective Channel States

2017-02-07 · Ryan G. James, John R. Mahoney, James P. Crutchfield

One of the most fundamental questions one can ask about a pair of random variables X and Y is the value of their mutual information. Unfortunately, this task is often stymied by the extremely large dimension of the varia…

MBT: A Memory-Based Part of Speech Tagger-Generator

1996-07-11 · Walter Daelemans, Jakub Zavrel, Peter Berck, Steven Gillis

We introduce a memory-based approach to part of speech tagging. Memory-based learning is a form of supervised learning based on similarity-based reasoning. The part of speech tag of a word in a particular context is extr…

Incremental Learning Morphological Analysis Part-Of-Speech Tagging TAG