Abstract The optimization problems with a sparsity constraint is a class of important global optimization problems. A typical type of thresholding algorithms for solving such a problem adopts the traditional full steepest descent direction or Newton-like direction as a search direction to generate an iterate on which a certain thresholding is performed. Traditional hard thresholding discards a large part of a vector, and thus some important information contained in a dense vector has been lost in such a thresholding process. Recent study (Zhao in SIAM J Optim 30(1): 31–55, 2020) shows that the hard thresholding should be applied to a compressible vector instead of a dense vector to avoid a big loss of information. On the other hand, the optimal k -thresholding as a novel thresholding technique may overcome the intrinsic drawback of hard thresholding, and performs thresholding and objective function minimization simultaneously. This motivates us to propose the so-called partial gradient optimal thresholding (PGOT) method and its relaxed versions in this paper. The PGOT is an integration of the partial gradient and the optimal k -thresholding technique. The solution error bound and convergence for the proposed algorithms have been established in this paper under suitable conditions. Application of our results to the sparse optimization problems arising from signal recovery is also discussed. Experiment results from synthetic data indicate that the proposed algorithm is efficient and comparable to several existing algorithms.

Abstract The optimization problem with sparsity arises in many areas of science and engineering such as compressed sensing, image processing, statistical learning and data sparse approximation. In this paper, we study the dual-density-based reweighted $$\ell _{1}$$ ℓ 1 -algorithms for a class of $$\ell _{0}$$ ℓ 0 -minimization models which can be used to model a wide range of practical problems. This class of algorithms is based on certain convex relaxations of the reformulation of the underlying $$\ell _{0}$$ ℓ 0 -minimization model. Such a reformulation is a special bilevel optimization problem which, in theory, is equivalent to the underlying $$\ell _{0}$$ ℓ 0 -minimization problem under the assumption of strict complementarity. Some basic properties of these algorithms are discussed, and numerical experiments have been carried out to demonstrate the efficiency of the proposed algorithms. Comparison of numerical performances of the proposed methods and the classic reweighted $$\ell _1$$ ℓ 1 -algorithms has also been made in this paper.

The optimal k-thresholding (OT) and optimal k-thresholding pursuit (OTP) are newly introduced frameworks of thresholding techniques for compressed sensing and signal approximation. Such frameworks motivate the practical and efficient algorithms called relaxed optimal k-thresholding (ROTω) and relaxed optimal k-thresholding pursuit (ROTPω) which are developed through the tightest convex relaxations of OT and OTP, where ω is a prescribed integer number. The preliminary numerical results demonstrated in Zhao (2020) indicate that these approaches can stably reconstruct signals with a wide range of sparsity levels. However, the guaranteed performance of these algorithms with parameter ω≥2 has not yet established in Zhao (2020). The purpose of this paper is to show the guaranteed performance of OT and OTP in terms of the restricted isometry property (RIP) of nearly optimal order for the sensing matrix governing the k-sparse signal recovery, and to establish the first guaranteed performance result for ROTω and ROTPω with ω≥2. In the meantime, we provide a numerical comparison between ROTPω and several existing thresholding methods.