A stochastic proximal point algorithm for total variation regularization over large scale graphs

Adil Salim; Pascal Bianchi; Walid Hachem; Jeremie Jakubowicz

doi:10.1109/CDC.2016.7798952

A stochastic proximal point algorithm for total variation regularization over large scale graphs

Adil Salim, Pascal Bianchi, Walid Hachem, Jeremie Jakubowicz

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original language	English
Title of host publication	2016 IEEE 55th Conference on Decision and Control, CDC 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	4490-4495
Number of pages	6
ISBN (Electronic)	9781509018376
DOIs	https://doi.org/10.1109/CDC.2016.7798952
Publication status	Published - 27 Dec 2016
Externally published	Yes
Event	55th IEEE Conference on Decision and Control, CDC 2016 - Las Vegas, United States Duration: 12 Dec 2016 → 14 Dec 2016

Publication series

Name	2016 IEEE 55th Conference on Decision and Control, CDC 2016

Conference

Conference	55th IEEE Conference on Decision and Control, CDC 2016
Country/Territory	United States
City	Las Vegas
Period	12/12/16 → 14/12/16

Access to Document

10.1109/CDC.2016.7798952

Cite this

Salim, A., Bianchi, P., Hachem, W., & Jakubowicz, J. (2016). A stochastic proximal point algorithm for total variation regularization over large scale graphs. In 2016 IEEE 55th Conference on Decision and Control, CDC 2016 (pp. 4490-4495). Article 7798952 (2016 IEEE 55th Conference on Decision and Control, CDC 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2016.7798952

@inproceedings{39658d4fd33c415097397905afb68b5c,

title = "A stochastic proximal point algorithm for total variation regularization over large scale graphs",

abstract = "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.",

author = "Adil Salim and Pascal Bianchi and Walid Hachem and Jeremie Jakubowicz",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 55th IEEE Conference on Decision and Control, CDC 2016 ; Conference date: 12-12-2016 Through 14-12-2016",

year = "2016",

month = dec,

day = "27",

doi = "10.1109/CDC.2016.7798952",

language = "English",

series = "2016 IEEE 55th Conference on Decision and Control, CDC 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "4490--4495",

booktitle = "2016 IEEE 55th Conference on Decision and Control, CDC 2016",

}

Salim, A, Bianchi, P, Hachem, W & Jakubowicz, J 2016, A stochastic proximal point algorithm for total variation regularization over large scale graphs. in 2016 IEEE 55th Conference on Decision and Control, CDC 2016., 7798952, 2016 IEEE 55th Conference on Decision and Control, CDC 2016, Institute of Electrical and Electronics Engineers Inc., pp. 4490-4495, 55th IEEE Conference on Decision and Control, CDC 2016, Las Vegas, United States, 12/12/16. https://doi.org/10.1109/CDC.2016.7798952

A stochastic proximal point algorithm for total variation regularization over large scale graphs. / Salim, Adil; Bianchi, Pascal; Hachem, Walid et al.
2016 IEEE 55th Conference on Decision and Control, CDC 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 4490-4495 7798952 (2016 IEEE 55th Conference on Decision and Control, CDC 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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

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.

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 -

Salim A, Bianchi P, Hachem W, Jakubowicz J. A stochastic proximal point algorithm for total variation regularization over large scale graphs. In 2016 IEEE 55th Conference on Decision and Control, CDC 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 4490-4495. 7798952. (2016 IEEE 55th Conference on Decision and Control, CDC 2016). doi: 10.1109/CDC.2016.7798952

A stochastic proximal point algorithm for total variation regularization over large scale graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this