A Provably Exact Distributed ADMM Projection onto Graph-Constrained Doubly Stochastic Matrices

Extended version of a letter on the distributed computation of the Euclidean projection of a symmetric matrix onto the symmetric, nonnegative, doubly stochastic matrices supported on a graph, using only local computation and communication between neighboring nodes. We show that a natural project-then-average scheme can converge to a biased fixed point. We propose a global-consensus ADMM formulation that duplicates each edge variable at its two endpoints, prove that it is exact for symmetric targets and that the distributed iteration converges to the centralized projection, and derive an exact scalar-bisection solver for the node-local subproblem. The solver extends to heterogeneous curvature, coefficients, and box constraints, and an explicit counterexample shows that it does not extend to two independent linear couplings. On four graph families, the heuristic stalls at relative errors between 3.5e-3 and 6.3e-2, whereas the proposed method reaches 1e-11 to 1e-16 with one communication round per sweep instead of two. The report also studies the sensitivity to the penalty parameter, scaling to graphs with 800 nodes, and warm starts within an outer ADMM iteration. Code: https://github.com/raghuram87/decentralized-fmmc-admm