TY - GEN
T1 - A stochastic proximal point algorithm for total variation regularization over large scale graphs
AU - Salim, Adil
AU - Bianchi, Pascal
AU - Hachem, Walid
AU - Jakubowicz, Jeremie
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/12/27
Y1 - 2016/12/27
N2 - The total-variation (TV) regularizer is often used to promote the structured sparsity of a given real function over the vertices of a non-directed graph. Indeed, the proximity operator associated with TV regularizer promotes sparsity of the function discrete gradient. Although quite affordable in the special case of one-dimensional (1D) graphs, the computation of the proximity operator for general large scale graphs can be demanding. In this paper, we propose a stochastic algorithm for solving this problem over large graphs with a moderate iteration complexity. The algorithm consists in properly selecting random paths in the graph and computing 1D-proximity operators over these paths. Convergence of the algorithm is related to recent results on stochastic proximal point algorithms.
AB - The total-variation (TV) regularizer is often used to promote the structured sparsity of a given real function over the vertices of a non-directed graph. Indeed, the proximity operator associated with TV regularizer promotes sparsity of the function discrete gradient. Although quite affordable in the special case of one-dimensional (1D) graphs, the computation of the proximity operator for general large scale graphs can be demanding. In this paper, we propose a stochastic algorithm for solving this problem over large graphs with a moderate iteration complexity. The algorithm consists in properly selecting random paths in the graph and computing 1D-proximity operators over these paths. Convergence of the algorithm is related to recent results on stochastic proximal point algorithms.
UR - https://www.scopus.com/pages/publications/85010739140
U2 - 10.1109/CDC.2016.7798952
DO - 10.1109/CDC.2016.7798952
M3 - Conference contribution
AN - SCOPUS:85010739140
T3 - 2016 IEEE 55th Conference on Decision and Control, CDC 2016
SP - 4490
EP - 4495
BT - 2016 IEEE 55th Conference on Decision and Control, CDC 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 55th IEEE Conference on Decision and Control, CDC 2016
Y2 - 12 December 2016 through 14 December 2016
ER -