Half thresholding eigenvalue algorithm for semidefinite matrix completion  

作　　者：CHEN YongQiang LUO ZiYan XIU NaiHua 

机构地区：[1]Department of Mathematics, Beijing Jiaotong University [2]College of Mathematics and Information Science, Henan Normal University [3]The State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University

出　　处：《Science China Mathematics》2015年第9期2015-2032,共18页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.11431002,71271021 and 11301022);the Fundamental Research Funds for the Central Universities of China(Grant No.2012YJS118)

摘　　要：The semidefinite matrix completion(SMC) problem is to recover a low-rank positive semidefinite matrix from a small subset of its entries. It is well known but NP-hard in general. We first show that under some cases, SMC problem and S1/2relaxation model share a unique solution. Then we prove that the global optimal solutions of S1/2regularization model are fixed points of a symmetric matrix half thresholding operator. We give an iterative scheme for solving S1/2regularization model and state convergence analysis of the iterative sequence.Through the optimal regularization parameter setting together with truncation techniques, we develop an HTE algorithm for S1/2regularization model, and numerical experiments confirm the efficiency and robustness of the proposed algorithm.The semidefinite matrix completion（SMC） problem is to recover a low-rank positive semidefinite matrix from a small subset of its entries. It is well known but NP-hard in general. We first show that under some cases, SMC problem and S1/2relaxation model share a unique solution. Then we prove that the global optimal solutions of S1/2regularization model are fixed points of a symmetric matrix half thresholding operator. We give an iterative scheme for solving S1/2regularization model and state convergence analysis of the iterative sequence.Through the optimal regularization parameter setting together with truncation techniques, we develop an HTE algorithm for S1/2regularization model, and numerical experiments confirm the efficiency and robustness of the proposed algorithm.

关 键 词：semidefinite matrix completion S1/2relaxation half thresholding eigenvalue algorithm conver-gence 

分 类 号：O241.6[理学—计算数学]