The Sparse Way:From Signal Recovery,to Image Reconstruction,and To Phase Retrieval

According to some special structures of high-dimensional data,such as sparsity and low-rankness,specific information can be recovered from linear or non-linear in-complete observations.This is the inverse problem in data science,which is concerned by many scholars.This problem's core is the sparse optimization.It includes Sparse signal recovery,low rank matrix completion/recovery,sparse phase retrieval,image re-construction,low rank tensor completion/recovery,deep learning,sparse optimization algorithm,etc.This thesis explores the theory and algorithm of these sparse and low rank optimization problems.The main contribution of this thesis can be stated as follows.The first one is the theory of sparse signal recovery via the convex l1 minimiza-tion.First,we get sufficient conditions under the cumulative coherence to guarantee accurate or stable recovery of sparse signals.Secondly,we estimate the approximate degree of prediction loss of the Lasso solver and Dantzig selector under the cumula-tive coherent famework.Finally,we also demonstrate the advantages of cumulative coherent conditions through numerical experiments.The second one is theory and algorithm of sparse signal recovery via the nonconvex l1-?l2(0<??1)minimization.In order to recover signal from observations with impulsive noise,we introduce two new model:the l1-?l2 minimization with l1 constraint-l1-?l2-LAD,l1-?l2 minimization with Dantzig selector constraint-l1-?l2-DS.We give sufficient conditions based on l1-restricted isometry property,which can guarantee the sparse signal exact or stable recovery.In order to compute l1-?l2 minimization,we also introduce the unconstraint model-l1-?l2-PLAD.Based on difference of convex function algorithm(DCA)and ADMM,we design l1-?l2LA algorithm with provably convergence.Our numerical examples show that when the measurement matrix is ill-conditioned(i.e,the coherence is larger than 0.99).our method is better than some existing convex and nonconvex methods.The third one is the reconstruction and restoration of the image based on the sparsity regularity.We notice an interesting phenomenon,that is,the gradient trans-formation matrix of the image u(especially for images with piece constant regions)Dxu,Dxu is not only sparse but also low rank.We propose a model called com-pressed total variation(CTV)to characterize this prior information of the image.To solve this model,we have designed a specific algorithm with provably convergence,which is based on ADMM.The tests examples include for magnetic resonance imaging(MRI)reconstruction,image denoising and image deblurring.The tests show that our proposed model not only restores the non-smooth edges and fine details of the image,but also preserves the shape of the main object in the image.The fourth one is inertial proximal ADMM for multi-block convex optimization problem and affine phase recovery.Firstly,for the multi-block convex optimization problem with separable objective function,we propose an inertial proximal ADMM(Prox-IADMM)algorithm,which is a nontrivial extension of the inertial proximi-ty ADMM algorithm for two convex optimization problems with separable objective functions.Our method requires no restrictions on the original model,only minor modifications to the iterative scheme of the classical ADMM algorithm.Under some very mild conditions,we get the global convergence of the objective function and the generated sequence.As an application of our proposed algorithm,we consider the sparse affine phase recovery problem.By lifting techniques,the convex relaxation of the rank of the matrix-the nuclear norm,the convex relaxation of the sparsity-l1 nor-m.we establish an model,which is called compressive affine phase retrieval via lifting(CAPRL).The objective function of this model contains two variables-the sparse vec?tor x,a sparse and low rank positive semi-definite matrix X;the constrained condition of this model is X=xxT.And it also contain data fitting term in the noisy case.We design concrete algorithm based on the proposed Prox-IADMM,to solve the CAPRL model.The numerical tests show that sparse signals can be recovered accurately or stably from sparse afnne phase recovery measurements.The numerical experiments comparing other ADMM algorithms show that the proposed Prox-IADMM requires fewer iterations and has a faster convergence rate.