Optimal rates for total variation denoising

Jan-Christian Hütter, Philippe Rigollet
29th Annual Conference on Learning Theory, PMLR 49:1115-1146, 2016.

Abstract

Motivated by its practical success, we show that the 2D total variation denoiser satisfies a sharp oracle inequality that leads to near optimal rates of estimation for a large class of image models such as bi-isotonic, Hölder smooth and cartoons. Our analysis hinges on properties of the unnormalized Laplacian of the two-dimensional grid such as eigenvector delocalization and spectral decay. We also present extensions to more than two dimensions as well as several other graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v49-huetter16, title = {Optimal rates for total variation denoising}, author = {Hütter, Jan-Christian and Rigollet, Philippe}, booktitle = {29th Annual Conference on Learning Theory}, pages = {1115--1146}, year = {2016}, editor = {Feldman, Vitaly and Rakhlin, Alexander and Shamir, Ohad}, volume = {49}, series = {Proceedings of Machine Learning Research}, address = {Columbia University, New York, New York, USA}, month = {23--26 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v49/huetter16.pdf}, url = {https://proceedings.mlr.press/v49/huetter16.html}, abstract = {Motivated by its practical success, we show that the 2D total variation denoiser satisfies a sharp oracle inequality that leads to near optimal rates of estimation for a large class of image models such as bi-isotonic, Hölder smooth and cartoons. Our analysis hinges on properties of the unnormalized Laplacian of the two-dimensional grid such as eigenvector delocalization and spectral decay. We also present extensions to more than two dimensions as well as several other graphs. } }
Endnote
%0 Conference Paper %T Optimal rates for total variation denoising %A Jan-Christian Hütter %A Philippe Rigollet %B 29th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2016 %E Vitaly Feldman %E Alexander Rakhlin %E Ohad Shamir %F pmlr-v49-huetter16 %I PMLR %P 1115--1146 %U https://proceedings.mlr.press/v49/huetter16.html %V 49 %X Motivated by its practical success, we show that the 2D total variation denoiser satisfies a sharp oracle inequality that leads to near optimal rates of estimation for a large class of image models such as bi-isotonic, Hölder smooth and cartoons. Our analysis hinges on properties of the unnormalized Laplacian of the two-dimensional grid such as eigenvector delocalization and spectral decay. We also present extensions to more than two dimensions as well as several other graphs.
RIS
TY - CPAPER TI - Optimal rates for total variation denoising AU - Jan-Christian Hütter AU - Philippe Rigollet BT - 29th Annual Conference on Learning Theory DA - 2016/06/06 ED - Vitaly Feldman ED - Alexander Rakhlin ED - Ohad Shamir ID - pmlr-v49-huetter16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 49 SP - 1115 EP - 1146 L1 - http://proceedings.mlr.press/v49/huetter16.pdf UR - https://proceedings.mlr.press/v49/huetter16.html AB - Motivated by its practical success, we show that the 2D total variation denoiser satisfies a sharp oracle inequality that leads to near optimal rates of estimation for a large class of image models such as bi-isotonic, Hölder smooth and cartoons. Our analysis hinges on properties of the unnormalized Laplacian of the two-dimensional grid such as eigenvector delocalization and spectral decay. We also present extensions to more than two dimensions as well as several other graphs. ER -
APA
Hütter, J. & Rigollet, P.. (2016). Optimal rates for total variation denoising. 29th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 49:1115-1146 Available from https://proceedings.mlr.press/v49/huetter16.html.

Related Material