A Greedy Multistage Convex Relaxation Algorithm Applied to Structured Group Sparse Reconstruction Problems Based on Iterative Support Detection

We propose a new effective algorithm for recovering a group sparse signal from very limited observations or measured data. As we know that a better reconstruction quality can be achieved when encoding more structural information besides sparsity, the commonly employed l2,1-regularization incorporating the prior grouping information has a better performance than the plain l1-regularized models as expected. In this paper we make a further use of the prior grouping information as well as possibly other prior information by considering a weighted l2,1 model. Specifically, we propose a multistage convex relaxation procedure to alternatively estimate weights and solve the resulted weighted problem. The procedure of estimating weights makes better use of the prior grouping information and is implemented based on the iterative support detection (Wang and Yin, 2010). Comprehensive numerical experiments show that our approach brings significant recovery enhancements compared with the plain l2,1 model, solved via the alternating direction method (ADM) (Deng et al., 2013), either in noiseless or in noisy environments