Nonlinear evolution equations as fast and exact solvers of estimation problems

We develop computationally efficient procedures for solving certain restoration problems in one dimension, including the one-dimensional (1-D) discrete versions of the total variation regularized problem introduced by Sauer and Bouman and the constrained total variation minimization problem introduced by Rudin et al. The procedures are exact and have time complexity O(NlogN) and space complexity O(N), where N is the number of data samples. They are based on a simple nonlinear diffusion equation proposed by Pollak et al. and related to the Perona-Malik equation. A probabilistic interpretation for this diffusion equation in 1-D is provided by showing that it produces optimal solutions to a sequence of estimation problems. We extend our methods to two dimensions, where they no longer have similar optimality properties; however, we experimentally demonstrate their effectiveness for image restoration.