Precise phase transition of total variation minimization

Bingwen Zhang; Weiyu Xu; Jian Feng Cai; Lifeng Lai

doi:10.1109/ICASSP.2016.7472532

Precise phase transition of total variation minimization

Bingwen Zhang, Weiyu Xu, Jian Feng Cai, Lifeng Lai

Department of Mathematics

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

8 Citations (Scopus)

Abstract

Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex optimization signal recovery methods such as ℓ1 minimization and nuclear norm minimization are well understood through recent years' research. However, rigorously characterizing the phase transition of total variation (TV) minimization in recovering sparse-gradient signal is still open. In this paper, we fully characterize the phase transition curve of the TV minimization. Our proof builds on Donoho, Johnstone and Montanari's conjectured phase transition curve for the TV approximate message passing algorithm (AMP), together with the linkage between the minmax Mean Square Error (MSE) of a denoising problem and the high-dimensional convex geometry for TV minimization.

Original language	English
Title of host publication	2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	4518-4522
Number of pages	5
ISBN (Electronic)	9781479999880
DOIs	https://doi.org/10.1109/ICASSP.2016.7472532
Publication status	Published - 18 May 2016
Event	41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Shanghai, China Duration: 20 Mar 2016 → 25 Mar 2016

Publication series

Name	ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume	2016-May
ISSN (Print)	1520-6149

Conference

Conference	41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016
Country/Territory	China
City	Shanghai
Period	20/03/16 → 25/03/16

Bibliographical note

Publisher Copyright:
© 2016 IEEE.

Keywords

Gaussian width
Phase Transition
Total Variation Minimization

Access to Document

10.1109/ICASSP.2016.7472532

Cite this

Zhang, B., Xu, W., Cai, J. F., & Lai, L. (2016). Precise phase transition of total variation minimization. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings (pp. 4518-4522). Article 7472532 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2016-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2016.7472532

Zhang, Bingwen ; Xu, Weiyu ; Cai, Jian Feng et al. / Precise phase transition of total variation minimization. 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 4518-4522 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{0fba0e4e5acb426187fd3d5027f0de44,

title = "Precise phase transition of total variation minimization",

abstract = "Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex optimization signal recovery methods such as ℓ1 minimization and nuclear norm minimization are well understood through recent years' research. However, rigorously characterizing the phase transition of total variation (TV) minimization in recovering sparse-gradient signal is still open. In this paper, we fully characterize the phase transition curve of the TV minimization. Our proof builds on Donoho, Johnstone and Montanari's conjectured phase transition curve for the TV approximate message passing algorithm (AMP), together with the linkage between the minmax Mean Square Error (MSE) of a denoising problem and the high-dimensional convex geometry for TV minimization.",

keywords = "Gaussian width, Phase Transition, Total Variation Minimization",

author = "Bingwen Zhang and Weiyu Xu and Cai, \{Jian Feng\} and Lifeng Lai",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 ; Conference date: 20-03-2016 Through 25-03-2016",

year = "2016",

month = may,

day = "18",

doi = "10.1109/ICASSP.2016.7472532",

language = "English",

series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",

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

pages = "4518--4522",

booktitle = "2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings",

}

Zhang, B, Xu, W, Cai, JF & Lai, L 2016, Precise phase transition of total variation minimization. in 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings., 7472532, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, vol. 2016-May, Institute of Electrical and Electronics Engineers Inc., pp. 4518-4522, 41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016, Shanghai, China, 20/03/16. https://doi.org/10.1109/ICASSP.2016.7472532

Precise phase transition of total variation minimization. / Zhang, Bingwen; Xu, Weiyu; Cai, Jian Feng et al.
2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2016. p. 4518-4522 7472532 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2016-May).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - Precise phase transition of total variation minimization

AU - Zhang, Bingwen

AU - Xu, Weiyu

AU - Cai, Jian Feng

AU - Lai, Lifeng

PY - 2016/5/18

Y1 - 2016/5/18

N2 - Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex optimization signal recovery methods such as ℓ1 minimization and nuclear norm minimization are well understood through recent years' research. However, rigorously characterizing the phase transition of total variation (TV) minimization in recovering sparse-gradient signal is still open. In this paper, we fully characterize the phase transition curve of the TV minimization. Our proof builds on Donoho, Johnstone and Montanari's conjectured phase transition curve for the TV approximate message passing algorithm (AMP), together with the linkage between the minmax Mean Square Error (MSE) of a denoising problem and the high-dimensional convex geometry for TV minimization.

AB - Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex optimization signal recovery methods such as ℓ1 minimization and nuclear norm minimization are well understood through recent years' research. However, rigorously characterizing the phase transition of total variation (TV) minimization in recovering sparse-gradient signal is still open. In this paper, we fully characterize the phase transition curve of the TV minimization. Our proof builds on Donoho, Johnstone and Montanari's conjectured phase transition curve for the TV approximate message passing algorithm (AMP), together with the linkage between the minmax Mean Square Error (MSE) of a denoising problem and the high-dimensional convex geometry for TV minimization.

KW - Gaussian width

KW - Phase Transition

KW - Total Variation Minimization

UR - https://openalex.org/W2963247080

UR - https://www.scopus.com/pages/publications/84973358613

U2 - 10.1109/ICASSP.2016.7472532

DO - 10.1109/ICASSP.2016.7472532

M3 - Conference Paper published in a book

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 4518

EP - 4522

BT - 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016

Y2 - 20 March 2016 through 25 March 2016

ER -

Zhang B, Xu W, Cai JF, Lai L. Precise phase transition of total variation minimization. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2016. p. 4518-4522. 7472532. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). doi: 10.1109/ICASSP.2016.7472532

Precise phase transition of total variation minimization

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this