Theory And Computation Of Sparse Recovery And Sparse Optimization Via ?₁-minimization

Low-complexity structures of models such as sparsity and low-rankness play a growingly important role in contemporary computational and applied mathematics, signal processing, and statistics science. A commonly concerned inverse problem is how to efficiently exploit low-complexity structure so that one can recover a certain objective from incomplete（possibly randomized） measurements. This indeed becomes a hot topic recently and attracts lots of attention from many fields such as compressive sensing, imaging/signal processing, high-dimensional statistics, machine learning, big data, and more.In this thesis, we focus on sparse recovery and sparse optimization via ?₁-minimization--an extremely efficient and simple way to access ill-posed linear inverse problem, and offer four contributes:The first contribution concerns sparse recovery conditions of ?₁-minimization. Establishing guarantees for unique and robust sparse recover in ?₁-minimization lies in the central of sparse recovery theory. Many concepts like coherence, null space property,restricted isometry property（RIP） and more were created for this assignment. However,existing works mainly consider the sufficiency but usually ignore the necessity of guarantees, and more badly, feasible approaches to verify such guarantees are seriously absent. To go beyond the traditional wisdom, we study the dual certificate condition which was previously known to be a sufficient condition guaranteeing solution uniqueness in?₁-minimization. We show that it is also necessary and its idea applies broadly to other types of ?₁-minimization problems, including ?₁analysis minimization, decomposable norm minimization, and gauge function minimization. In addition, we construct concrete ways to verify our studied conditions.The second contribution concerns restricted eigenvalues of structured random matrices. Random matrix is an important analysis tool for compressive sensing and dimension reduction. The biggest advantage of structured random matrices over ordinary random matrix should be its fast multiply with vectors. With the help of recent decoupling techniques and matrix-valued Bernstein inequalities and as well the Laplace transform technique, we prove a concentration property for a class of structured random matrices with random column sign. This property is then used to show a nearly desired Johnson-Lindenstrausslemma. By the link between JL lemma and RIP, the results developed here could be used to analyze the RIP of that class of structured random matrices.The third contribution concerns two types of classic algorithms in sparse optimization--the linearized Bregman algorithm for compressive sensing and the singular value thresholding algorithm for matrix completion, both of which are very efficient. The big drawback of them is how to choose parameters. To overcome it, on one hand we propose strongly convex ?₁-minimization models and deduce parameter estimations; on the other hand, we propose dual gradient methods to solve general strongly convex ?₁-type models by combining the idea of duality and the framework of proximal point operator. To ensure rates of linear convergence of gradient methods, current theory regularly assumes that the objective functions are strongly convex. We propose a new concept, named restricted strong convexity, to guarantee globally linear convergence; the proposed concept is strictly weaker than the strong convexity and hence can be satisfied by a more widely class of functions.The last but not least contribution develops iteratively reweighted least square（IRLS） methods. By combining the proximal liearized technique and the idea of iteratively reweighted least squares method, we propose proximal linearized iteratively reweighted least square（PL-IRLS） algorithms for a class of nonconvex and nonsmooth problems.The proposed methods cover almost all the ?₁-minimization models discussed in the thesis. Theoretically, with the help of the Kurdyka- ?ojasiewicz property, we prove that each bounded sequence generated by PL-IRLS globally converges to a critical point of the approximated problem. To the best of our knowledge, this is the first global convergence result of applying the IRLS idea to solve nonconvex and nonsmooth problems.We close this thesis by figuring out seven future directions and three open problems.The seven directions are: The theory and application of convex analysis and optimization; Estimation of high dimension from geometrical perspective; Subgradient methods for large scale problems; Nonconvex optimization and globally convergence; Parallel algorithms for large scale problems; Randomized operator splitting and primal-dual method.