Half thresholding eigenvalue algorithm for semidefinite matrix completion

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...

Full description

Saved in:
Bibliographic Details
Published in:Science China. Mathematics 2015-09, Vol.58 (9), p.2015-2032
Main Authors: Chen, YongQiang, Luo, ZiYan, Xiu, NaiHua
Format: Article
Language:English
Subjects:
Algorithms
Applications of Mathematics
Convergence
Eigenvalues
Iterative methods
Mathematical models
Mathematics
Mathematics and Statistics
Optimization
Regularization
Robustness
全局最优解
半正定矩阵
参赛作品
对称矩阵
收敛性分析
特征值
算法
阈值
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1674-7283
1869-1862
DOI:10.1007/s11425-015-5052-y