Title: Multiprocessor Approximate Message Passing with Column-Wise Partitioning,
Abstract: Solving a large-scale regularized linear inverse problem using multiple
processors is important in various real-world applications due to the
limitations of individual processors and constraints on data sharing policies.
This paper focuses on the setting where the matrix is partitioned column-wise.
We extend the algorithmic framework and the theoretical analysis of approximate
message passing (AMP), an iterative algorithm for solving linear inverse
problems, whose asymptotic dynamics are characterized by state evolution (SE).
In particular, we show that column-wise multiprocessor AMP (C-MP-AMP) obeys an
SE under the same assumptions when the SE for AMP holds. The SE results imply
that (i) the SE of C-MP-AMP converges to a state that is no worse than that of
AMP and (ii) the asymptotic dynamics of C-MP-AMP and AMP can be identical.
Moreover, for a setting that is not covered by SE, numerical results show that
damping can improve the convergence performance of C-MP-AMP.