Multiprocessor Approximate Message Passing with Column-Wise Partitioning

Yanting Ma, Yue M. Lu, Dror Baron

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.

Introduction

In high-dimensional statistics and signal processing, the linear inverse problem—recovering a signal $x$ from noisy measurements $y = Ax + w$—is fundamental. However, as the scale of data grows, the sensing matrix $A$ often becomes too large to be stored or processed by a single machine. Furthermore, in fields like genomics or finance, data is frequently distributed across different institutions that may own specific features (columns) of the matrix and cannot share them due to privacy constraints.

While row-wise partitioning (splitting observations) has been extensively studied, column-wise partitioning (splitting features) presents unique challenges. In this configuration, each processor only observes a partial contribution to the measurement vector $y$. Without a rigorous coordination mechanism, distributed iterations can lead to over-correction or divergence. This paper introduces C-MP-AMP, a distributed framework for Approximate Message Passing (AMP) that addresses these challenges with theoretical guarantees.

Methodology: The C-MP-AMP Framework

The C-MP-AMP algorithm extends the standard AMP framework to a hierarchical multiprocessor setting. The architecture consists of two primary components:

  1. Local Processors: Each of the $P$ processors stores a subset of the columns of the sensing matrix $A$. These processors perform local computations to update their respective portions of the signal estimate.
  2. Fusion Center: A central node aggregates the local estimates to compute a global residual. This residual is then broadcast back to the local processors to synchronize the next iteration.

Communication and Iteration

The algorithm utilizes a dual-loop structure. "Outer iterations" represent global synchronizations where data is exchanged with the fusion center, while "inner iterations" involve local computations. A critical technical component of C-MP-AMP is the implementation of the Onsager correction at the fusion center. This term is essential in AMP to decouple the dependencies introduced during the iterative process, ensuring that the effective noise remains Gaussian.

Theoretical Analysis

The primary contribution of this work is the formal proof that C-MP-AMP's performance is predictable via State Evolution (SE). State Evolution is a powerful mathematical tool that tracks the mean squared error of AMP iterations in the large-system limit.

Finite-Sample Analysis

Using finite-sample analysis, the authors demonstrate that the algorithm's error concentrates around the SE prediction at an exponential rate. This holds even with the complex dependencies introduced by the column-wise distribution of the matrix $A$.

Key Theoretical Findings

  • The "No-Harm" Guarantee: The authors prove that C-MP-AMP converges to a fixed point that is at least as accurate as the centralized, single-processor version of AMP.
  • Linear Speedup: The analysis shows that if the communication schedule is optimized (e.g., one inner iteration per outer iteration), the asymptotic dynamics of C-MP-AMP are identical to standard AMP. This implies that with $P$ processors, the computation can theoretically be accelerated by a factor of $P$ without any loss in reconstruction fidelity.

Numerical Insights and Damping

While the theoretical proofs assume sensing matrices with i.i.d. sub-Gaussian entries, real-world applications often involve more structured or "ill-conditioned" matrices. To bridge this gap, the authors investigate the use of damping—a technique where the current estimate is averaged with the previous one. Numerical results indicate that damping significantly enhances the stability and convergence of C-MP-AMP in scenarios that deviate from the ideal theoretical assumptions.

Conclusion

C-MP-AMP provides a robust and theoretically grounded solution for solving massive linear inverse problems in a distributed, column-wise fashion. By proving that the distributed algorithm maintains the same asymptotic performance as its centralized counterpart, this work paves the way for scalable, privacy-preserving signal recovery. Future research directions include optimizing communication costs through lossy compression of messages and extending the theoretical framework to non-Gaussian sensing matrices.

Summary updated

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.
BibTeX
@inproceedings{ma2017multiprocessor,
  author = {Yanting Ma and Yue M. Lu and Dror Baron},
  title = {{Multiprocessor Approximate Message Passing with Column-Wise Partitioning}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2017},
  url = {https://openreview.net/forum?id=-Ny2tPqI_KI},
}
Figure