MULTISCALE METHODS FOR POLYHEDRAL REGULARIZATIONS

In this paper we present the extension and generalization of the adaptive inverse scale space (aISS) method proposed for l(1) regularization in [Math. Comp., 82 (2013), pp. 269-299] to arbitrary polyhedral functions. We will see that the representation of a convex polyhedral function as a finitely generated function allows us to conclude that the inverse scale space flow (the time continuous formulation of the augmented Lagrangian method) can be solved exactly without discretization. We present an algorithm for the computation of such a solution for arbitrary polyhedral functions, analyze its convergence, and interpret the well-known (forward) scale space flow as the inverse scale space flow on the convex conjugate functional, thus including this class of flows in our analysis. A surprising result is the equivalence of the scale space or gradient flow with a standard variational problem. Finally, we give examples of the applications for the aISS algorithm for polyhedral functions, which illustrate that the resulting algorithm can be fast (depending on the finitely generated representation of the polyhedral function) and behaves favorably over classical variational methods in the case of noisy data.