Pith. sign in

REVIEW 4 cited by

An Efficient HPR Algorithm for the Wasserstein Barycenter Problem with $O({Dim(P)}/\varepsilon)$ Computational Complexity

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2211.14881 v1 pith:PG2VOZRO submitted 2022-11-27 math.OC

Guojun Zhang , Yancheng Yuan , Defeng Sun This is my paper · ORCID
classification math.OC
keywords algorithmcomplexityvarepsiloncomputationalefficientsolvingbarycenterlinear
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

In this paper, we propose and analyze an efficient Halpern-Peaceman-Rachford (HPR) algorithm for solving the Wasserstein barycenter problem (WBP) with fixed supports. While the Peaceman-Rachford (PR) splitting method itself may not be convergent for solving the WBP, the HPR algorithm can achieve an $O(1/\varepsilon)$ non-ergodic iteration complexity with respect to the Karush-Kuhn-Tucker (KKT) residual. More interestingly, we propose an efficient procedure with linear time computational complexity to solve the linear systems involved in the subproblems of the HPR algorithm. As a consequence, the HPR algorithm enjoys an $O({\rm Dim(P)}/\varepsilon)$ non-ergodic computational complexity in terms of flops for obtaining an $\varepsilon$-optimal solution measured by the KKT residual for the WBP, where ${\rm Dim(P)}$ is the dimension of the variable of the WBP. This is better than the best-known complexity bound for the WBP. Moreover, the extensive numerical results on both the synthetic and real data sets demonstrate the superior performance of the HPR algorithm for solving the large-scale WBP.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Convergence Analysis of the Restarted Moving-Anchored Extra-Gradient Method in the Absence of Local Lipschitz Continuity

    math.OC 2026-07 accept novelty 7.0 of 10

    The MAEG-R method achieves convergence for monotone inclusions with merely continuous operators via a moving-anchor restart strategy, while preserving O(1/k) complexity in the Lipschitz case.

  2. A Perturbed DCA for Computing d-Stationary Points of Nonsmooth DC Programs

    math.OC 2026-01 reject novelty 6.0 of 10

    A single-subproblem perturbed DCA is claimed to compute d-stationary points almost surely, but the proof needs an unproved rate condition and the promised hybrid variant is absent.

  3. HPR-QP: A dual Halpern Peaceman-Rachford method for solving large-scale convex composite quadratic programming

    math.OC 2025-07 conditional novelty 6.0 of 10

    HPR-QP solves large-scale convex composite quadratic programs with a dual Halpern Peaceman-Rachford iteration on the restricted Wolfe dual, obtaining O(1/k) KKT residual and strong GPU benchmark results.

  4. An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems

    math.OC 2025-05 conditional novelty 5.0 of 10

    An accelerated semi-proximal ADMM with extrapolation and increasing penalties is proven to converge at O(1/K) non-ergodically, but a key equivalence used in the mixed sparse optimization application is incorrect.

Pith tools