On the ROF Model in Rectilinear Anisotropy: Piecewise Constant Approximation and Universal Minimality

Abstract

We prove that the $L^2$ distance between the minimizer of the ${\ell }^1$-anisotropic Rudin-Osher-Fatemi (ROF) functional and its minimizer over the space of piecewise constant functions on a rectilinear grid is $\mathcal{O}(h^{\frac{1}{2}-\frac{q^{\prime }}{2q}})$, where $h$ is the grid's mesh size and the datum belongs to $L^q$, $q\ge 2$. These convergence rates are valid in any dimension $d\ge 1$. However, in dimension $d=1$ they can be further improved to $\mathcal{O}(h^{\frac{1}{2}-\frac{1}{2q}})$. To establish the error bounds, $L^q$ estimates of the ROF minimizer in terms of the datum are critical. Such estimates are particular cases of a universal minimality property of the ROF minimizer derived in the second part of the paper. There it is shown, in both the finite-dimensional and infinite-dimensional settings, that the minimizer simultaneously minimizes a broad class of convex functionals over a neighbourhood of the datum arising in the convex dual of the ROF problem. This extends previous results of similar type about taut strings and the ROF problem.

Changes in this version: Error bounds and rates in section 5 are new. Sections 2, 3, 4 contain new preparatory material. Sections 6, 7, 8 are not new but arranged differently and improved