Algorithms and stability analysis for optimization problems with sparsity

[摘要] The optimization models with sparsity arise in many areas of science and engineering, such as compressive sensing, image processing, statistical learning and machine learning. In this thesis, we study a general 10-minimization model, which can be used to deal with many practical applications. Firstly, we show some theoretical properties of the solutions of this model. Then, two types of re-weighted 11-algorithms will be developed from both the perspectives of primal and dual spaces, respectively. The primal re-weighted 11-algorithms will be derived through the 1st-order approximation of the so-called merit functions for sparsity. The dual re-weighted 11-algorithms for the general 10-model will be developed based on the reformulation of the general 10-model as a certain bilevel programming problem under the assumption of strict complementarity. We conduct numerical experiments to demonstrate the efficiency of the primal and dual re-weighted 11-algorithms and compare with some existing algorithms. We also establish a general stability result for a class of 11-minimization approach which is broad enough to cover many important special cases. Unlike the existing stability results developed under the null space property and restricted isotonic property, we use a classic Hoffman's theorem to establish a restricted-weak-RSP-based stability result for this class of 11-minimization approach.

[发布机构] University:University of Birmingham;Department:School of Mathematics

[关键词] Q Science;QA Mathematics