Non-convex sparse optimization through deterministic annealing and applications

We propose a new formulation to the sparse approximation problem for the case of tight frames which allows to minimize the cost function using gradient descent. We obtain a generalized version of the iterative hard thresholding (IHT) algorithm, which provides locally optimal solutions. In addition, to avoid non-favorable minima we use an annealing technique consisting of gradually de-smoothing a previously smoothed version of the cost function. This results in decreasing the threshold through the iterations, as some authors have already proposed as a heuristic. We have adapted and applied our method to restore images having localized information losses, such as missing pixels. We present high-performance in-painting results.