The proximal alternating iterative hard thresholding method for l0l0 minimization, with complexity O(1/k)

Since digital images are usually sparse in the wavelet frame domain, some nonconvex minimization models based on wavelet frame have been proposed and sparse approximations have been widely used in image restoration in recent years. Among them, the proximal alternating iterative hard thresholding method is proposed in this paper to solve the nonconvex model based on wavelet frame. Through combining the proposed algorithm with the iterative hard thresholding algorithm which is well studied in compressed sensing theory, this paper proves that the complexity of the proposed method is O(1/k). On the other hand, a more general nonconvex–nonsmooth model is adopted and the pseudo proximal alternating linearized minimization method is developed to solve the above problem. With the Kurdyka–Łojasiewicz (KL) property, it is proved that the sequence generated by the proposed algorithm converges to some critical points of the corresponding model. Finally, the proposed method is applied to restore the blurred noisy gray images. As the numerical results reveal, the performance of the proposed method is comparable or better than some well-known convex image restoration methods.