Variational Multiscale Nonparametric Regression: Algorithms and Implementation
Many modern statistically efficient methods come with tremendous computational challenges, often leading to large-scale optimisation problems. In this work, we examine such computational issues for recently developed estimation methods in nonparametric regression with a specific view on image denois...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-11-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/11/296 |
| _version_ | 1797547910403981312 |
|---|---|
| author | Miguel del Alamo Housen Li Axel Munk Frank Werner |
| author_facet | Miguel del Alamo Housen Li Axel Munk Frank Werner |
| author_sort | Miguel del Alamo |
| collection | DOAJ |
| description | Many modern statistically efficient methods come with tremendous computational challenges, often leading to large-scale optimisation problems. In this work, we examine such computational issues for recently developed estimation methods in nonparametric regression with a specific view on image denoising. We consider in particular certain variational multiscale estimators which are statistically optimal in minimax sense, yet computationally intensive. Such an estimator is computed as the minimiser of a smoothness functional (e.g., TV norm) over the class of all estimators such that none of its coefficients with respect to a given multiscale dictionary is statistically significant. The so obtained multiscale Nemirowski-Dantzig estimator (MIND) can incorporate any convex smoothness functional and combine it with a proper dictionary including wavelets, curvelets and shearlets. The computation of MIND in general requires to solve a high-dimensional constrained convex optimisation problem with a specific structure of the constraints induced by the statistical multiscale testing criterion. To solve this explicitly, we discuss three different algorithmic approaches: the Chambolle-Pock, ADMM and semismooth Newton algorithms. Algorithmic details and an explicit implementation is presented and the solutions are then compared numerically in a simulation study and on various test images. We thereby recommend the Chambolle-Pock algorithm in most cases for its fast convergence. We stress that our analysis can also be transferred to signal recovery and other denoising problems to recover more general objects whenever it is possible to borrow statistical strength from data patches of similar object structure. |
| first_indexed | 2024-03-10T14:51:48Z |
| format | Article |
| id | doaj.art-65a8765b1edf493db90820651cfdc028 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T14:51:48Z |
| publishDate | 2020-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-65a8765b1edf493db90820651cfdc0282023-11-20T20:55:31ZengMDPI AGAlgorithms1999-48932020-11-01131129610.3390/a13110296Variational Multiscale Nonparametric Regression: Algorithms and ImplementationMiguel del Alamo0Housen Li1Axel Munk2Frank Werner3Department of Applied Mathematics, University of Twente, 7522 NB Enschede, The NetherlandsInstitute for Mathematical Stochastics, University of Göttingen, 37073 Göttingen, GermanyInstitute for Mathematical Stochastics, University of Göttingen, 37073 Göttingen, GermanyInstitute of Mathematics, University of Würzburg, 97070 Würzburg, GermanyMany modern statistically efficient methods come with tremendous computational challenges, often leading to large-scale optimisation problems. In this work, we examine such computational issues for recently developed estimation methods in nonparametric regression with a specific view on image denoising. We consider in particular certain variational multiscale estimators which are statistically optimal in minimax sense, yet computationally intensive. Such an estimator is computed as the minimiser of a smoothness functional (e.g., TV norm) over the class of all estimators such that none of its coefficients with respect to a given multiscale dictionary is statistically significant. The so obtained multiscale Nemirowski-Dantzig estimator (MIND) can incorporate any convex smoothness functional and combine it with a proper dictionary including wavelets, curvelets and shearlets. The computation of MIND in general requires to solve a high-dimensional constrained convex optimisation problem with a specific structure of the constraints induced by the statistical multiscale testing criterion. To solve this explicitly, we discuss three different algorithmic approaches: the Chambolle-Pock, ADMM and semismooth Newton algorithms. Algorithmic details and an explicit implementation is presented and the solutions are then compared numerically in a simulation study and on various test images. We thereby recommend the Chambolle-Pock algorithm in most cases for its fast convergence. We stress that our analysis can also be transferred to signal recovery and other denoising problems to recover more general objects whenever it is possible to borrow statistical strength from data patches of similar object structure.https://www.mdpi.com/1999-4893/13/11/296non-smooth large-scale optimisationimage denoisingvariational estimationmultiscale methodsMIND estimator |
| spellingShingle | Miguel del Alamo Housen Li Axel Munk Frank Werner Variational Multiscale Nonparametric Regression: Algorithms and Implementation Algorithms non-smooth large-scale optimisation image denoising variational estimation multiscale methods MIND estimator |
| title | Variational Multiscale Nonparametric Regression: Algorithms and Implementation |
| title_full | Variational Multiscale Nonparametric Regression: Algorithms and Implementation |
| title_fullStr | Variational Multiscale Nonparametric Regression: Algorithms and Implementation |
| title_full_unstemmed | Variational Multiscale Nonparametric Regression: Algorithms and Implementation |
| title_short | Variational Multiscale Nonparametric Regression: Algorithms and Implementation |
| title_sort | variational multiscale nonparametric regression algorithms and implementation |
| topic | non-smooth large-scale optimisation image denoising variational estimation multiscale methods MIND estimator |
| url | https://www.mdpi.com/1999-4893/13/11/296 |
| work_keys_str_mv | AT migueldelalamo variationalmultiscalenonparametricregressionalgorithmsandimplementation AT housenli variationalmultiscalenonparametricregressionalgorithmsandimplementation AT axelmunk variationalmultiscalenonparametricregressionalgorithmsandimplementation AT frankwerner variationalmultiscalenonparametricregressionalgorithmsandimplementation |