Analytical bounds on the minimizers of (nonconvex) regularized least-squares (Q939208)

The classical inverse problem of the recovery of an estimate of an unknown image based on observed noisy data is studied. A generalization of the conventional Tikhonov regularization method is employed in the wide context of edge-preserving regularization. The key contribution of this paper is a theoretical study on the minimizers of cost-functions composed of an \(l_2\) data-fidelity term and a possibly non-smooth or non-convex regularization term acting on the differences (or the discrete gradients) of the image or the signal to restore. The simple and general analytical bounds characterizing the local and global minimizers of these cost-functions are derived. These bounds are for arbitrary signals (images) of a finite size and they hold for possibly non-smooth or non-convex regularization terms. In the first part of the paper, bounds that compare the restored data with the noisy data are derived. Further, a tight data-independent bound on the \(l_{\infty}\) norm of the residual (the estimate of the noise) is exhibited even if its \(l_2\) norm is being minimized to cope with the edge preservation challenge. Finally, the smoothing incurred by the local minimizers in terms of the differences (or the discrete gradients) of the restored image (signal) is noticed. The constructed analytical bounds do not involve asymptotic assumptions and address practical situations.