Optimal rates for total variation denoising
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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
PMLR
2020
|
| Online Access: | https://hdl.handle.net/1721.1/125674 |
| _version_ | 1826211477732720640 |
|---|---|
| author | Huetter, Jan-Christian Klaus Rigollet, Philippe |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Huetter, Jan-Christian Klaus Rigollet, Philippe |
| author_sort | Huetter, Jan-Christian Klaus |
| collection | MIT |
| description | 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. Key words and phrases: Total variation regularization; TV denoising; sharp oracle inequalities; image denoising; edge Lasso; trend filtering; nonparametric regression; shape constrained regression; minimax |
| first_indexed | 2024-09-23T15:06:33Z |
| format | Article |
| id | mit-1721.1/125674 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:06:33Z |
| publishDate | 2020 |
| publisher | PMLR |
| record_format | dspace |
| spelling | mit-1721.1/1256742022-09-29T12:44:58Z Optimal rates for total variation denoising Huetter, Jan-Christian Klaus Rigollet, Philippe Massachusetts Institute of Technology. Department of Mathematics 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. Key words and phrases: Total variation regularization; TV denoising; sharp oracle inequalities; image denoising; edge Lasso; trend filtering; nonparametric regression; shape constrained regression; minimax 2020-06-04T17:41:41Z 2020-06-04T17:41:41Z 2016 2019-11-19T17:18:16Z Article http://purl.org/eprint/type/ConferencePaper 2640-3498 https://hdl.handle.net/1721.1/125674 Huetter, Jan-Christian and Philippe Rigollet. "Optimal rates for total variation denoising." 29th Annual Conference on Learning Theory, PMLR 49, (2016): 1115-1146. © 2016 J.-C. Hütter & P. Rigollet en http://proceedings.mlr.press/v49/huetter16.html 29th Annual Conference on Learning Theory, PMLR 49 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf PMLR arXiv |
| spellingShingle | Huetter, Jan-Christian Klaus Rigollet, Philippe Optimal rates for total variation denoising |
| title | Optimal rates for total variation denoising |
| title_full | Optimal rates for total variation denoising |
| title_fullStr | Optimal rates for total variation denoising |
| title_full_unstemmed | Optimal rates for total variation denoising |
| title_short | Optimal rates for total variation denoising |
| title_sort | optimal rates for total variation denoising |
| url | https://hdl.handle.net/1721.1/125674 |
| work_keys_str_mv | AT huetterjanchristianklaus optimalratesfortotalvariationdenoising AT rigolletphilippe optimalratesfortotalvariationdenoising |