Project

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. 120–145, 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. 1762–1769.

[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. 1–34, Jan. 2021.

@ARTICLE{10215352,

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

  journal={IEEE Transactions on Signal Processing}, 

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

  year={2023},

  volume={71},

  number={},

  pages={3281-3295},

  doi={10.1109/TSP.2023.3304789}

}

• official

• arXiv

• MATLAB code

• GitHub