Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with $f$-Divergence Perception Constraints

📄 Abstract

Abstract: We study the computation of the rate-distortion-perception function (RDPF) for discrete memoryless sources subject to a single-letter average distortion constraint and a perception constraint belonging to the family of $f$-divergences. In this setting, the RDPF forms a convex programming problem for which we characterize optimal parametric solutions. We employ the developed solutions in an alternating minimization scheme, namely Optimal Alternating Minimization (OAM), for which we provide convergence guarantees. Nevertheless, the OAM scheme does not lead to a direct implementation of a generalized Blahut-Arimoto (BA) type of algorithm due to implicit equations in the iteration's structure. To overcome this difficulty, we propose two alternative minimization approaches whose applicability depends on the smoothness of the used perception metric: a Newton-based Alternating Minimization (NAM) scheme, relying on Newton's root-finding method for the approximation of the optimal solution of the iteration, and a Relaxed Alternating Minimization (RAM) scheme, based on relaxing the OAM iterates. We show, by deriving necessary and sufficient conditions, that both schemes guarantee convergence to a globally optimal solution. We also provide sufficient conditions on the distortion and perception constraints, which guarantee that the proposed algorithms converge exponentially fast in the number of iteration steps. We corroborate our theoretical results with numerical simulations and establish connections with existing results.