Paper Info
Title
Performance degradation of AMP for small-sized problems
Abstract
Pearl's belief propagation (BP) is an algorithm to solve inference problems on probability models defined in terms of graphical models. Computational complexity of BP per iteration is typically exponential in the degrees of nodes in the graph, which makes application of BP impractical in problems represented by dense graphs. For the alleviation of the computational difficulty of BP, an approximation of BP dubbed approximate message passing (AMP) is proposed in the area of compressed sensing. Since theoretical treatments of AMP are mostly in the infinite-dimensional limit, they are not mathematically justifiable when the system size is not large enough and little is known about the cases where the system size is small. We investigate poor performance of the AMP algorithm applied to small-sized problems, which is frequently observed in numerical experiments, by comparing performance of the AMP algorithm and that of the original BP algorithm. In this paper, firstly, we show that, under several assumptions, one can perform the original BP algorithm in time complexity that is polynomial in the degrees of the nodes, utilizing a method similar to what is employed in BP decoding for LDPC codes. Next, we apply the preceding discussion to the CDMA multiuser detection problem, to which AMP has been successfully applied in existing researches. Finally, we compare the performance of the BP and AMP algorithms and discuss the effects of the approximation involved in deriving the AMP algorithm, when the system size is not large enough.
Year
DOI
Venue
2015
10.1109/ISIT.2015.7282967
Information Theory
Keywords
Field
DocType
code division multiple access,compressed sensing,graph theory,message passing,multidimensional systems,multiuser detection,parity check codes,probability,AMP algorithm,BP algorithm,CDMA multiuser detection,LDPC codes,approximate message passing,belief propagation,compressed sensing,dense graphs,graphical model,inference problems,infinite dimensional limit,performance degradation,probability model,Approximate message passing,belief propagation,message passing
Polynomial,Low-density parity-check code,Computer science,Multiuser detection,Algorithm,Graphical model,Time complexity,Message passing,Computational complexity theory,Belief propagation
Conference
Citations 
PageRank 
References 
0
0.34
3
Authors
2
Name
Order
Citations
PageRank
Arise Kuriya100.34
Toshiyuki Tanaka219019.98