We are interested in minimizing functionals with 𝓁2 data and gradient fitting term and 𝓁1 regularization term with higher order derivatives in a discrete setting. We examine the structure of the solution in 1D by reformulating the original problem into a contact problem which can be solved by dual optimization techniques. The solution turns out to be a ‘smooth’ discrete polynomial spline whose knots coincide with the contact points while its counterpart in the contact problem is a discrete version of a spline with higher defect and contact points as knots. In 2D we modify Chambolle's algorithm to solve the minimization problem with the 𝓁1 norm of interacting second order partial derivatives as regularization term. We show that the algorithm can be implemented efficiently by applying the fast cosine transform. We demonstrate by numerical denoising examples that the 𝓁2 gradient fitting term can be used to avoid both edge blurring and staircasing effects.