Efficient iterative thresholding algorithms with functional feedbacks and convergence analysis

Ningning Han, Shidong Li, Zhanjie Song

Published 2020-05-14Version 1

An accelerated class of adaptive scheme of iterative thresholding algorithms is studied analytically and empirically. They are based on the feedback mechanism of the null space tuning techniques (NST+HT+FB). The main contribution of this article is the accelerated convergence analysis and proofs with a variable/adaptive index selection and different feedback principles at each iteration. These convergence analysis require no longer a priori sparsity information $s$ of a signal. %key theory in this paper is the concept that the number of indices selected at each iteration should be considered in order to speed up the convergence. It is shown that uniform recovery of all $s$-sparse signals from given linear measurements can be achieved under reasonable (preconditioned) restricted isometry conditions. Accelerated convergence rate and improved convergence conditions are obtained by selecting an appropriate size of the index support per iteration. The theoretical findings are sufficiently demonstrated and confirmed by extensive numerical experiments. It is also observed that the proposed algorithms have a clearly advantageous balance of efficiency, adaptivity and accuracy compared with all other state-of-the-art greedy iterative algorithms.