A Study On Exact Recovery Conditions In Sparse Recovery Problems

As a sparse optimization on Rn,compressed sensing,aiming to reconstruct the original data from few measurements interrupted with noise or partially lost,has attracted extensive attention and developed rapidly in recent years with a range of applications including signal processing,image inpainting,medical imaging and so on.With the development of modern information theory and technology,high-dimensional data with complex structures such as face images,surveillance videos and multi-spectral images become ubiquitous in many research areas.In this thesis,we focus on the sparse optimization problems as extensions of applying compressed sensing to conplex high-dimensional data and overcome the NP-hardness of the original problems by relaxing the problems to the tractable formulations,including the problem of finding the sparsest solution to the system of linear equalities and inequalities,low-rank matrix recovery problem and lowrank tensor recovery problem.So far,a large number of efficient algorithms for solving the relaxations have been proposed,however,there are little investigation on the theory of the successful recovery.This thesis has made some research of the exact recovery conditions for the extended sparse optimization problems.The author's major contributions are outlined as follows:1.We consider the exact recovery conditions for the problem of finding the sparsest solution to the system of absolute value equations(AVEs).Utilizing the equivalence between the system of AVEs and a bilinear program,the problem of finding the sparest solution to the system of AVEs is equivalent to an l0-minimization problem under some linear equalities and inequalities constraints under an assumption which has been used extensively to study the system of AVEs.Based on the methodology of the range space property,we first propose the necessary and sufficient conditions for the uniqueness of the optimal solution to the relaxation,then prove that under those conditions this unique solution is exactly the sparsest solution to the system of AVEs.Inspired by the analysis and results,we discuss the exact recovery conditions to guarantee the equivalence between the problem of finding the sparsest solution to the system of linear equalities and inequalities and its convex relaxation,and give some examples to verify the theoretical results.2.We consider a nonconvex relaxation of low-rank matrix recovery(LMR),called the Schatten-p quasi-norm minimization(0 < p < 1)instead of the previous nuclear norm minimization.We derive a restricted p-isometry property(p-RIP)for exact reconstruction of LMR via Schatten-p quasi-norm minimization,and determine how many random,Gaussian measurements are needed to guarantee the p-RIP to hold with high probability.3.We concentrate on low-rank tensor recovery problem and extended three kinds of exact recovery conditions from matrix space(low-rank matrix recovery)to tensor space.Besides,we consider a new tensor recovery model which includes both the noisy case and the noiseless case,named as minimum n-rank approximation(MnRA),and propose an appropriate iterative hard thresholding algorithm to solve this problem.We show that the iterative sequence generated by the proposed algorithm is globally linearly convergent to the true data with the rate 1/2 under some conditions,while for the noisy case the distance between the iterative sequence and the true data is decreased quickly associated with the noise.Some preliminary numerical results are reported and demonstrate the efficiency of the proposed algorithms.