Performance degradation of AMP for small-sized problems

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.