Algorithms For Low-Rank Semidefinite Matrix Recovery Problems

Low-rank semidefinite matrix recovery problems arise in diverse areas such as sig-nal and image processing, finance, control, graph theory, system identification etc. It is a hot research topic due to the wide applications and the computation challenge from the involved non-convex and discontinuous matrix rank function, which results in the NP-hardness in general cases. To make it tractable, the convex nuclear norm relaxation technique has been widely used in the literature but its efficiency is not universal. In this thesis, efficient and robust algorithms will be designed for the low-rank semidefinite matrix recovery problem based on the nonconvex relaxation model, the rank regulariza-tion model, and the least-squares model with low-rank constraint.As a special case, the low-rank semidefinite matrix completion (SMC) problem will firstly be discussed in theory and in computation. In the theoretical aspect, some exact relaxation conditions are proposed to guarantee that the SMC problem and its corresponding S1/2 relaxation model share a unique solution. By establishing a fixed point equation of some symmetric matrix half thresholding operator for the global op-timal solutions of S1/2 regularization model, we give an algorithm framework for the regularization problem and state its convergence analysis. An HTE algorithm is then developed for the implementation with the optimal regularization parameter setting and truncation techniques. Numerical experiments confirm the efficiency and robustness of the proposed algorithm.For low-rank semidefinite matrix recovery problems, we establish its nonconvex Sp regularization model. By developing the symmetric matrix p-thresholding operator representation theory, we establish some necessary condition for global optimal solu-tions of Sp regularization model, and also provide the exact lower bound for the positive eigenvalues at global optimal solutions to the regularized model. To ensure the desired low-rank property, a sufficient condition is further proposed. Based upon the theoretical analysis, a p-thresholding eigenvalues algorithm is then developed and its convergence analysis is established. Numerical results demonstrate that our method can effectively solve these problems.For low-rank semidefinite matrix recovery problems, we also establish the rank regularization model. By applying the closed-form solutions of the involved essential subproblem, we prove that global optimal solutions of the rank regularization model are fixed points of a symmetric matrix hard thresholding operator. A hard thresholding algorithm is then designed with the fixed point iteration based on the symmetric matrix hard thresholding operator. Convergence analysis is stated and numerical experiments are provided to confirm the efficiency and stability of the proposed algorithm.For the least-squares problem with low-rank constraint, the majorization scheme is employed to convert the original problem to a metric projection problem onto the non-convex rank-constrained semidefinite matrix cone. A necessary condition for global optimal solutions of the original problem is then established by means of the projec-tion operator onto this non-convex cone. The closed-form of the involved projection allows us to implement a majorization algorithm for the original low-rank semidefinite matrix recovery problem. Convergence analysis indicates that any accumulation point of the sequence generated by our method satisfies the necessary condition for global optimality.