Variable-Wise Diagonal Preconditioning for Primal-Dual Splittin: Design and Applications

Published in IEEE Transactions on Signal Processing

Kazuki Naganuma and Shunsuke Ono


This paper proposes a method for designing diagonal preconditioners for a preconditioned primal-dual splitting method (P-PDS), an efficient algorithm that solves nonsmooth convex optimization problems. To speed up the convergence of P-PDS, a design method has been proposed to automatically determine appropriate preconditioners from the problem structure. However, the existing method has two limitations. One is that it directly accesses all elements of matrices representing linear operators involved in a given problem, which is inconvenient for handling linear operators implemented as procedures rather than matrices. The other is that it takes an element-wise preconditioning approach, which turns certain types of proximity operators into analytically intractable forms. To overcome these limitations, we establish an Operator norm-based design method of Variable-wise Diagonal Preconditioning (OVDP). First, OVDP constructs diagonal preconditioners using only (upper bounds) of the operator norms of linear operators, thus eliminating the need for their explicit matrix representations. Furthermore, since OVDP takes a variable-wise preconditioning approach, it keeps any proximity operator analytically computable. We also prove that our preconditioners satisfy the convergence condition of P-PDS. Finally, we demonstrate the effectiveness and usefulness of OVDP through applications to mixed noise removal of hyperspectral images, hyperspectral unmixing, and graph signal recovery.



[1] A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging,  J. Math. Imag. Vis., vol. 40, no. 1, pp. 120145, 2010.

[2] T. Pock and A. Chambolle, Diagonal preconditioning for first order primal-dual algorithms in convex optimization, in IEEE Int. Conf. Comput. Vis. (ICCV), Nov. 2011, pp. 17621769.

[3] Y. Liu, Y. Xu, and W. Yin, Acceleration of primal–dual methods by preconditioning and simple subproblem procedures, J. Sci. Comput., vol. 86, no. 21, pp. 134, Jan. 2021.


K. Naganuma and S. Ono, "Variable-Wise Diagonal Preconditioning for Primal-Dual Splitting: Design and Applications," in IEEE Transactions on Signal Processing, vol. 71, pp. 3281-3295, 2023, doi: 10.1109/TSP.2023.3304789.


  author={Naganuma, Kazuki and Ono, Shunsuke},

  journal={IEEE Transactions on Signal Processing}, 

  title={Variable-Wise Diagonal Preconditioning for Primal-Dual Splitting: Design and Applications},