Weighted or reweighted strategies have not been considered for sparsity constrained optimization. In this paper, we reformulate the sparsity constraint as an equivalent weighted l1-norm constraint in the sparsity constrained optimization problem. To solve the reformulated problem, we investigate the problem in the Lagrange dual framework, and prove that the strong duality property holds. Then we propose a weighted thresholding method to solve the Lagrangian problem. Moreover, we analyze convergence of the method and derive an error bound of the solution under some assumptions. Furthermore, we propose a weighted thresholding homotopy method to get a suitable Lagrange multiplier and prove that this homotopy method can find an L-stationarity point of the primal problem. Computational experiments on compressed sensing and sparse logistic regression problems show that, in comparable running time the proposed weighted thresholding homotopy method works better than state-of-the-art methods on randomly generated instances of the compressed sensing problem and on the synthetic data of the logistic regression problem. Especially, the sparsity level improvement of exact recovery is 26.9% for compressed sensing, and the sparsity level improvement of exact classification is 38.5% for sparse logistic regression on randomly generated data.
Article
View Weighted Thresholding Homotopy Method for Sparsity Constrained Optimization