Research On Theorems And Algorithms In Block-sparse Representation

Sparse representation (or sparse component analysis, sparse coding) has receivedmuch attention in recent years. It is applied to image processing, blind sourceseparation, compressed sensing and pattern recognition, etc. In fact, due to its highvalue in theory and promising applications in practice, sparse representation has beenone of the hottest topics in signal processing.In the standard sparsity model, a vector is called sparse if it has a few nonzeroelements, and the nonzero elements can appear anywhere in the vector. Recently, therehas been growing interest in sparse signals that exhibit additional structure, e.g.block-sparsity, tree-sparsity, graph-sparsity, etc. Structure sparsity has been foundwide applications in many scientific areas, especially in the areas of multi-bandcommunications, structured compressed sensing, image processing, backgroundsubtracted image, etc. In all of these structures, the simplest and most important isblock structure, i.e. the nonzero elements are appearing in blocks. Exist theoreticalresults and algorithms are almost based on block-sparsity. This thesis is also focus onblock-sparsity. The main contributions of this thesis include:1. The recoverability of block-sparse signals by convex relaxation methods isanalyzed for underdetermined linear model. In previous works, some explicit but“pessimistic” recoverability results which associate with the dictionary were presented.This thesis shows the recoverability of block-sparse signal are associated with theblock structure when a random dictionary is given. Several probability inequalitiesare obtained to show how the recoverability changes along with the block structureparameters, such as the number of nonzero blocks, the block length, the dimension ofthe measurements and the dimension of the block-sparse representation signal.Also, it concludes that if block-sparse structure can be considered, the recoverabilityof the signals will be improved. Numerical examples illustrate the availability of thepresented theoretical results.2. A block fixed point continuation algorithm for block-sparse reconstruction isproposed. The convex relaxation model for block-sparse reconstruction is difficult to solve due to its mixed norm. Although2/1-optimization program (L-OPT)can formulate it as second-order cone programming (SOCP) problem and solve it byusing standard software packages, it is computationally expensive due to the Hessianof the objective function is needed and do not suit for large scale problems. In thisthesis, extending fixed point continuation (FPC) method to block-wise cases byincorporating block coordinate descent (BCD) technique, a first-order algorithmcalled block fixed point continuation (BFPC) is proposed to solve the unconstrainedconvex relaxation model. BFPC includes only matrix-vector multiplication, whichcomputational complexity is low. Numerical examples show the proposed algorithmexhibit good accuracy and robustness.3. Split Bregman algorithms for block-sparse reconstruction, including bothconstrained form and unconstrained form, are proposed. Block fixed pointcontinuation algorithm and some state of the art algorithms are designed to solve theunconstrained block-sparse reconstruction problem, in which the penalty parameter isimportant but difficult to choose. Bregman algorithm, which is motivated by theBregman distance, can solve the problem by fixing the penalty parameter and “addingback the noise”. Split technique can simplify the problem by “de-coupling” thevariables in different norms. Convergence results of the proposed algorithms are givenand proven. Numerical examples show the proposed algorithm exhibit good efficiencyand robustness.4. Algorithms for multiple measurement vector (MMV) problem are proposed. Inmultiple measurement vector problem, all vectors are assumed to be jointly sparse, i.e.nonzero elements are concentrated in common rows. Multiple measurement vectorcan cast to a specific block-sparse problem which has the same block length. In thisthesis, block fixed point continuation algorithm and split Bregman algorithms aredesigned to solve multiple measurement vector problem. Furthermore, MagneticResonance Imaging (MRI) can be seen as a multiple measurement vector problem andbe solved by proposed algorithms. Numerical results show the validity of theproposed algorithma for real-world data.