Study On Exact Relaxation Theory Of Nonnegative Sparse Optimization

The nonnegative sparse optimization is to find the sparsest solution of an underdeter-mined linear equation with the nonnegative constraints, making use of the sparsity of the variable under consideration. In the vector space, it is essentially the nonnegative l0norm minimization; while in the matrix space, it becomes the semidefinite matrix rank minimiza-tion. Owing to the wide applications in DNA microarrays, quantum state tomography, medical imaging, spectroscopy, sensor location and hidden Markov models together with the close connection with inverse problems,principal component analysis, combinatorial optimization, linear optimization and semidefinite optimization, the nonnegative sparse optimization has attracted much attention of both mathematicians and engineers in many application areas, and obtained rapid development in recent years. This thesis is mainly concerned with the solution property and the exact relaxation conditions.Chapter1briefly introduces the significance and mathematical models of nonnegative sparse optimization, and reviews the research status of the relaxation theory.In chapter2, we discuss the solution property of the nonnegative sparse optimiza-tion. For the nonnegative sparse optimization over vector space, we introduce the special partition for the space Rn in the light of the l0norm function, based on which we show that any two distinct solutions of the desired problem must have different support sets. hence we prove that any solution to the underlying problem must be one of the extreme points of the feasible set. This can lay the foundation for the heuristic algorithms or some new relaxations of the underlying combinatorial problem. For the nonnegative sparse op- timization over matrix space, we show that when the eigenvalue decomposition of any two different solutions share the same orthogonal matrix, the corresponding eigenvalue vectors can not share the same support set.In chapter3, we investigate the generalized Z-matrix exact relaxation condition for both the convex and nonconvex relaxations of the nonnegative sparse optimization over vector space. Firstly, by introducing the concept of generalized Z-matrix and least ele-ment theory, we investigate the feasibility of the nonnegative l0norm optimization under some conditions. Moreover, we show that if the observation vector is nonnegative and the measurement matrix is a generalized Z-matrix, the aforementioned problem and its linear/lp (0<p<1) relaxation share the unique common solution, which is exactly the least element solution.Meanwhile, under our condition, one can accurately recover a k-sparse vector with only no less than k linear measurements.At the end of this part, we analyze the application in the single input single output interference channel where our recovery condition fit perfectly.In chapter4, we devote to the RIP type exact relaxation conditions for both convex and nonconvex relaxations of the nonnegative sparse optimization. Section1provides some properties of the eigenvalue decomposition of real symmetric matrices. In section2, by defining the constants NRIC and NROC. we give the existence and uniqueness condition of the solution to the nonnegative sparse optimization over vector space, and further get the exact recovery condition of the above program via both the linear and lp relaxation. In section3we discuss the uniqueness condition of the solution to the nonnegative sparse optimization over matrix space, and propose sufficient condition for the exact recovery via both the semidefinite and Schatten p-norm relaxations. In particular, we get the recovery condition that is independent of the parameter p.In chapter5, some generalizations are studied and several future issues are discussed. Since the nonnegative orthant and the semidefinite matrix cone are special cases of the so-called symmetric cone, some useful properties of solution sets of symmetric cone opti-mization problems are explored in the first section. By reviewing the existing results on the nonnegative optimization, four possible research issues are pointed out which deserve future study.