Some Theories And Algorithms On Structured Sparse Data Reconstruction

It has been for a long time a great challenge to exactly/robustly reconstruct the original data from its as few as possible observation.Especially with the era of big data coming,the significance and urgency of this issue has become even more prominent.In recent years,many sparse data reconstruction methods represented by compressed sensing are taken se-riously because of their efficiency in dealing with high-dimensional data,and the related theories,algorithms and applications have gradually become hot topics of signal processing,statistics,computer science and electronic communications,etc.However,with the in-depth research,people gradually found that,many methods that are used to deal with the sparse data reconstruction can not well tackle some structured sparse data.Therefore,it is of great importance to establish some novel and targeted methods to tackle such structured sparse data,and then study their related theories and algorithms.In this dissertation,we mainly focus on three representative structured sparse problems,including compressed sensing,block-sparse compressed sensing and matrix completion.The achievements can be summarized as follows.In the context of compressed sensing,we introduce anl_q?q?2?constraint for noise to a nonconvexl_1-2method,and then propose and investigate anl_q-l_1-2method.We theoretically establish the reconstruction condition and the error estimate of robust reconstruction for our proposed problem.In particular,our obtained recovery condition has been proved to be better than existing ones.The resultant experimental results further illustrate the efficiency of our proposed method.In the context of block-sparse compressed sensing,firstly,we extend anl_1-2method used to deal with the sparse signals to the block-sparsity,and propose and investigate anl₂/l_1-2method.We study this method both in its theoretical and numerical aspects.The obtained numerical experiments indicate that,when measurement matrices are highly block-coherent,our proposed method can perform much better than previousl₂/l₁andl₂/l_p?0<p<1?methods in dealing with block-sparse data.Secondly,Based on the coherence theory,we investigate a nonconvexl₂/l_p?0<p<1?method,and obtain some theoretical results on reconstruction conditions and the error estimate of robust reconstruction.We also conduct some experiments to confirm our theoretical results.In the context of matrix completion,we propose a novel algorithm that combines both the?global?low-rank and?local?smoothness priors of matrices.In our algorithm,the low-rankness and smoothness of matrices are characterized by their nuclear norm and a modified second-order total variation.These two kinds of priors help each other and hence largely improve the efficiency of matrix completion.We compare our algorithm with some state-of-the-art matrix completion algorithms,and all the numerical results further indicate that,when matrices to be reconstructed have certain local smoothness,our algorithm can perform much better than the others.