Analysis of the recovery of edges in images and signals by minimizing nonconvex regularized least-squares

We consider the restoration of discrete signals and images using least-squares with nonconvex regularization. Our goal is to find important features of the (local) minimizers of the cost function in connection with the shape of the regularization term. This question is of paramount importance for a relevant choice of regularization term. The main point of interest is the restoration of edges. We show that the differences between neighboring pixels in homogeneous regions are smaller than a small threshold, while they are larger than a large threshold at edges: we can say that the former are shrunk, while the latter are enhanced. This naturally entails a neat classification of differences as belonging to smooth regions or to edges. Furthermore, if the original signal or image is a scaled characteristic function of a subset, we show that the global minimizer is smooth everywhere if the contrast is low, whereas edges are correctly recovered at higher (finite) contrast. Explicit expressions are derived for the truncated quadratic and the "0-1" regularization function. It is seen that restoration using nonconvex regularization is fundamentally different from edge-preserving convex regularization. Our theoretical results are illustrated using a numerical experiment.