The Theory Of Tail Minimization Approaches For Spark-level Jointly Sparse Recovery And Applications

Compressed sensing theory is a milestone in the field of signal processing and applied math-ematics.It has become a popular topic due to the low signal sampling rates and the com-pressed data.Sparse recovery is one of the most important tasks in compressed sensing.Most of the signals in the real world are sparse（most of the coefficients are zero）.There-fore,the reconstruction of signals is not only theoretically feasible,but also there are many feasible algorithms to solve it.The jointly sparse recovery（also known as the multiple mea-surement vectors（MMV）problem）is an important structured row sparse signal recovery problem.It can improve the signal recovery performance and better correspond to the simul-taneous processing of multiple relevant signals in practical application scenarios.Therefore,the MMV problem has received amount of attentions.However,when the sparsity is large,the state-of-the-art algorithms is not always capable of achieving accurate and effective joint sparse signal recovery,which restricts the further extensions of these algorithms to solve even near-sparse problems in engineering practice.A typical MMV problem is the sparse representation of the array orientation（DOA estimation）problem,and the drawbacks of the above algorithms will lead to the degradation of resolution and estimation accuracy of the estimator.In this thesis,we address the key problems and difficulties in the MMV problem of the spark-level sparsity,including the existence of the unique solution to the MMV problem,the design of the jointly sparse recovery solution algorithm,the performance analyses and recovery guarantees of the algorithm,and the applications to the DOA estimation problem.The main contents are summarized as follows.1.The rank of the sparse signals brought by multiple measurement vectors（MMV）augments the performance of joint sparse recovery.In general,suppose the sparsity level k is less than or equal to[rank（X）+spark（A）-1]/2,the sparsest solution of the MMV problem is unique and recoverable via various methods.It is shown in this thesis that the unique solution of the sparsity level k up to spark（A）-1 actually exists in a measure theoretical point of view.More specifically,even when[rank（X）+spark（A）-1]/2≤k<spark（A）,the solution to AX=Y is still unique with full Lebesgue measure in every k-sparse coordinate space.This phenomenon is fully confirmed by the MMV tail-_2,1minimization technique（tail-min）.The mechanism is to estimate the support T relative to the true support S of the jointly sparse matrix and minimize the energy in the complement T^cof T during each iteration.Extensive numerical tests conducted by the MMV tail-_2,1minimization and_2,1minimization are demonstrated to confirm the findings.The tail minimization procedure exhibits the most prominent effectiveness for the larger sparsity levels among all known techniques.Furthermore,the phenomenon that the traditional _2,1minimization actually fails to recover X with k≥[spark（A）-1]/2 is investigated from the same perspective of measure theory.2.This thesis presents detailed analyses of the uniqueness and robustness of the pro-posed MMV tail-_2,1minimization algorithm.To begin with,an MMV tail-null-space prop-erty（MMV-tail-NSP）is derived,which is shown to be necessary and sufficient for the unique solution of the MMV tail minimization problem.The MMV-tail-NSP condition is also shown to be more likely to hold than that of the conventional MMV-NSP for any given MMV basis pursuit problem.Furthermore,the equivalence between SMV-tail-NSP and MMV-tail-NSP is demonstrated.This result shows that the verification process in the MMV case can be relatively simplified by the conclusion of the SMV case with the lower com-plexity.Secondly,two recovery guarantees and error bound analyses are also derived based on the MMV-robust-tail-NSP condition and merely the MMV-tail-NSP assumption,respec-tively.The second one,based on the MMV-tail-NSP,is more straightforward and novel,and can also derive a new upper bound on the reconstruction error of the basis pursuit.Study shows that the MMV tail-minimization approach is among the most effective techniques.Finally,all the theoretical results are verified by visual numerical simulations performed by the quantum-behaved particle swarm optimization（QPSO）.It is worth mentioning that both theoretical and experimental results show that the proposed algorithm is still sufficiently robust for large dimensional signals.3.Generally speaking,unique sparse solution exists for sparsity level k<K₀≡[rank（X）+spark（A）-1]/2.We observe in extensive empirical tests that the MMV tail-_2,1minimization approach is capable of recovering signals of the sparsity level up to spark（A）,even for rank（X）k,significantly beyond the rank-enriched upper bound K₀.This phenomenon is now known to be the measure theoretical uniqueness solution of the MMV problem.To analyze the greater recovery capacity of the MMV tail-_2,1mini-mization approach,two necessary and sufficient conditions for the unique solution are es-tablished.It is shown that these two tail-_2,1solution conditions are equivalent and more likely to hold than comparable conditions of the conventional _2,1minimization approach.Furthermore,theoretical recovery guarantee analyses of the tail-minimization approach are carried out.Specifically,two recovery probability estimates are derived.These successful recovery probabilities are shown to approach 1 not only as the number of measurements L increases（exponentially）but also as|T^c∩S|→0,where T is an estimation of the support index set S.That the MMV tail-_2,1minimization algorithm can recover signals of sparsity level beyond K₀and approaching spark（A）is sufficiently illustrated from these recovery probabilities.4.The tail-minimization approach is applied to solve the direction of arrival（DOA）estimation problems.First of all,the intrinsic mechanism for the effective denoising perfor-mance of the tail-minimization algorithm is analyzed qualitatively from the perspective of optimization theory.Both the proposed algorithm and the basis pursuit can be considered as a bivariate optimization problem.However,there is some interaction between the two vari-ables in the basis pursuit,whereas those in the proposed algorithm are independent of each other.Moreover,numerical experiments on the support recovery under the random matrix show that the tail-min approach is still capable of recovering the true support set of the signal with high probability even when a unique solution no longer exists.Last but not least,the advantages of the tail-min approach are also reflected in numerous aspects such as handling low signal-to-noise ratio（SNR）,limited number of snapshots,and correlated source signals.Results are more accurate with higher resolution as well.It is also capable of detecting the number of sources and estimating DOAs simultaneously.