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

Abstract We prove that the $$L^2$$ L 2 distance between the minimizer of the $$\ell ^1$$ ℓ 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^{{1}/{2} - {q'}/{2q}})$$ O ( h 1 / 2 - q ′ / 2 q ) , where h is the grid’s mesh size and the datum belongs to $$L^q$$ L q , $$q \ge 2$$ q ≥ 2 . These convergence rates are valid in any dimension $$d\ge 1$$ d ≥ 1 . However, in dimension $$d = 1$$ d = 1 they can be further improved to $$\mathcal {O}(h^{{1}/{2} - {1}/{2q}})$$ O ( h 1 / 2 - 1 / 2 q ) . To establish the error bounds, $$L^q$$ 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.