PAPF: Phase-Aware Polynomial Filtering for Fixed-Point Acceleration

We propose phase-aware polynomial filtering (PAPF), a simple method for accelerating fixed-point iterations by exploiting the phases of local Jacobian eigenvalues. PAPF applies the degree-two filter $S_{\alpha }=\alpha I+(1-\alpha )T^2$, with $\alpha \in (0,1)$, using two evaluations of the original operator per iteration. For firmly nonexpansive operators with a nonempty fixed-point set, the filter preserves averagedness and fixed points, guaranteeing global convergence for every fixed mixing parameter. Beyond this setting, we characterize precisely when PAPF improves the local convergence factor over the equal-cost baseline $T^2$. For a differentiable map with Jacobian $G=J_T(z^{\star })$ and spectral radius $\rho \in (0,1)$, such an improvement is possible if and only if every dominant eigenvalue $\rho e^{i{\theta }_j}$ satisfies $\cos (2{\theta }_j)<{\rho }^2$. We derive closed-form optimal parameters for individual spectral modes and formulate parameter selection for the full spectrum as a one-dimensional convex problem. When the spectrum is unavailable, we propose an empirical parameter-selection procedure based on short residual probes, requiring no explicit Jacobian information. We apply the framework to primal–dual hybrid gradient iterations for quadratically regularized optimal transport and to the power method for nonsymmetric eigenvalue problems. Experiments on these applications and synthetic operators demonstrate reductions in operator evaluations in favorable spectral regimes and support the predicted dependence of acceleration on eigenvalue phase.