Research On Theory And Algorithm Of High Dimensional Data Reconstruction Under L₁ Minimization Frame

With the rapid development of information technology,especially internet,internet of things,and cloud computing,people nowadays often face a wide variety of data with large volume and high dimensionality,so how to analyze these high-dimensional massive data and mine their essence of information has attracted the interest of researchers in various fields.In recent years,the sparse modeling method represented by compressed sensing has received much attention because of its effectiveness in processing high-dimensional data.The related theories and applications have gradually become research hotspots in the field of applied mathematics,statistics,electronic communication engineering,and computer science.However,compared with the continuously expanding different types of high-dimensional massive data,existing sparse modeling methods cannot effectively deal with sparse learning problems in unconventional situations that are realistically problematic,resulting in people often failing to obtain satisfactory results.Therefore,it is of great scientific significance to establish a targeted sparse data method based on the actual background of the application problem,and to develop relevant theoretical and algorithmic research.This thesis systematically studies some theory and algorithms of block sparse compressed sensing,low rank matrix recovery under complete perturbation and noise folding and so on.The main research results are as follows:In the scenario of block sparse compressed sensing,with the basic technique of sparse representation of polytope with block structure,the high-order reconstruction condition based on block restricted isometry property and associating estimation error of reconstruction are obtained when 0<t<4/3.At the same time,an example is constructed to show that this recovery guarantee is optimal.In addition,it is studied how many measurements are needed to satisfy reconstruction conditions based on block RIP with high probability when the measurement matrix is a Gaussian random matrix.Finally,the numerical experiments further verify the theoretical results and the effectiveness of the l₂/l₁minimization method.In the setting of impulse noise,a stable model is proposed,and the optimal recovery guarantee and the corresponding upper bound estimation of reconstruction error are obtained.Meanwhile,the corresponding algorithm convergence conditions are established.Based on the synthetic block sparse signal and the real FECG（fetal electrocardiogram）signal,the numerical experimental results show that the reconstruction performance of the new algorithm is robust and effective in the presence of high impulse noise.Besides,for the three kinds of impulse noises considered in this thesis,the bound of the l_pnorm that holds with a high probability is given.In the context of complete perturbation,the traditional low rank matrix is extended to a completely perturbed case,and a novel low rank matrix recovery model is proposed.Based on the restricted isometry property and the Frobenius-robust rank null space property,the sufficient conditions for the reconstruction guarantee and the associating upper bound estimation of the reconstruction error are obtained.In particular,when the results of this thesis degenerate into the vector case,not only the previous restricted isometry reconstruction conditions are improved,but also the upper bound estimation of the recovery error is reduced.The results of numerical experiments further demonstrate the effectiveness of the proposed method.In the background of noise folding,the problem of recovery of low rank matrix recovery is studied.The results show that for most measurement schemes used in compressed sensing,the traditional model is equivalent to that of the whitening.The main difference is that the noise variance of the noisy model is expanded by mn/M factor of factor.Here m,n respectively denote the number of row and column of the matrix to be recovered,and M stands for the number of samples.In addition,based on the two kinds of null space properties,the recovery guarantees and the error estimates of reconstruction are given respectively,and the number of samples required to satisfy the first recovery condition is obtained.Furthermore,for non-Gaussian noise case,it is further explored and the corresponding theoretical results of recovery guarantee are given.Finally,the effectiveness of the proposed method is verified by numerical experiments.