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

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 $O\left(h^{1/2-q^{\text{'}}/2q}\right)$ , 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 $O\left(h^{1/2-1/2q}\right)$ . 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.