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!
cited_by
cites cdi_FETCH-LOGICAL-c370t-602ad97947637abbd4b82037378dafe12bfb3aa33910229d75175c40f4672fcd3
container_end_page 2032
container_issue 9
container_start_page 2015
container_title Science China. Mathematics
container_volume 58
creator Chen, YongQiang
Luo, ZiYan
Xiu, NaiHua
description 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.
doi_str_mv 10.1007/s11425-015-5052-y
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_1744730218</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><cqvip_id>665849994</cqvip_id><sourcerecordid>1744730218</sourcerecordid><originalsourceid>FETCH-LOGICAL-c370t-602ad97947637abbd4b82037378dafe12bfb3aa33910229d75175c40f4672fcd3</originalsourceid><addsrcrecordid>eNp9kD9PwzAQxS0EElXpB2CLmFgM_pc4HlEFtFIlFpgtJ7ETV07c2gmi3x5XqRi54e6G97unewDcY_SEEeLPEWNGcohwDnOUE3i6AgtcFgKmRq7TXnAGOSnpLVjFuEepqECM0wXYbpQz2dgFHTvvGju0mbatHr6Vm3SmXOuDHbs-Mz5kUfe20cYOdtRZr8Zgf7La9wenR-uHO3BjlIt6dZlL8PX2-rnewN3H-3b9soM15WiEBSKqEVwwXlCuqqphVUkQ5ZSXjTIak8pUVClKBUaEiIbnmOc1Q4YVnJi6oUvwON89BH-cdBxlb2OtnVOD9lOUmLP0GSK4TFI8S-vgYwzayEOwvQoniZE8Jyfn5GRKTp6Tk6fEkJmJSTu0Osi9n8KQPvoXergYdX5oj4n7cyqKvGRCCEZ_ARiTfQ4</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1744730218</pqid></control><display><type>article</type><title>Half thresholding eigenvalue algorithm for semidefinite matrix completion</title><source>Springer Nature</source><creator>Chen, YongQiang ; Luo, ZiYan ; Xiu, NaiHua</creator><creatorcontrib>Chen, YongQiang ; Luo, ZiYan ; Xiu, NaiHua</creatorcontrib><description>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.</description><identifier>ISSN: 1674-7283</identifier><identifier>EISSN: 1869-1862</identifier><identifier>DOI: 10.1007/s11425-015-5052-y</identifier><language>eng</language><publisher>Beijing: Science China Press</publisher><subject>Algorithms ; Applications of Mathematics ; Convergence ; Eigenvalues ; Iterative methods ; Mathematical models ; Mathematics ; Mathematics and Statistics ; Optimization ; Regularization ; Robustness ; 全局最优解 ; 半正定矩阵 ; 参赛作品 ; 对称矩阵 ; 收敛性分析 ; 特征值 ; 算法 ; 阈值</subject><ispartof>Science China. Mathematics, 2015-09, Vol.58 (9), p.2015-2032</ispartof><rights>Science China Press and Springer-Verlag Berlin Heidelberg 2015</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c370t-602ad97947637abbd4b82037378dafe12bfb3aa33910229d75175c40f4672fcd3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Uhttp://image.cqvip.com/vip1000/qk/60114X/60114X.jpg</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Chen, YongQiang</creatorcontrib><creatorcontrib>Luo, ZiYan</creatorcontrib><creatorcontrib>Xiu, NaiHua</creatorcontrib><title>Half thresholding eigenvalue algorithm for semidefinite matrix completion</title><title>Science China. Mathematics</title><addtitle>Sci. China Math</addtitle><addtitle>SCIENCE CHINA Mathematics</addtitle><description>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.</description><subject>Algorithms</subject><subject>Applications of Mathematics</subject><subject>Convergence</subject><subject>Eigenvalues</subject><subject>Iterative methods</subject><subject>Mathematical models</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Optimization</subject><subject>Regularization</subject><subject>Robustness</subject><subject>全局最优解</subject><subject>半正定矩阵</subject><subject>参赛作品</subject><subject>对称矩阵</subject><subject>收敛性分析</subject><subject>特征值</subject><subject>算法</subject><subject>阈值</subject><issn>1674-7283</issn><issn>1869-1862</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2015</creationdate><recordtype>article</recordtype><recordid>eNp9kD9PwzAQxS0EElXpB2CLmFgM_pc4HlEFtFIlFpgtJ7ETV07c2gmi3x5XqRi54e6G97unewDcY_SEEeLPEWNGcohwDnOUE3i6AgtcFgKmRq7TXnAGOSnpLVjFuEepqECM0wXYbpQz2dgFHTvvGju0mbatHr6Vm3SmXOuDHbs-Mz5kUfe20cYOdtRZr8Zgf7La9wenR-uHO3BjlIt6dZlL8PX2-rnewN3H-3b9soM15WiEBSKqEVwwXlCuqqphVUkQ5ZSXjTIak8pUVClKBUaEiIbnmOc1Q4YVnJi6oUvwON89BH-cdBxlb2OtnVOD9lOUmLP0GSK4TFI8S-vgYwzayEOwvQoniZE8Jyfn5GRKTp6Tk6fEkJmJSTu0Osi9n8KQPvoXergYdX5oj4n7cyqKvGRCCEZ_ARiTfQ4</recordid><startdate>20150901</startdate><enddate>20150901</enddate><creator>Chen, YongQiang</creator><creator>Luo, ZiYan</creator><creator>Xiu, NaiHua</creator><general>Science China Press</general><scope>2RA</scope><scope>92L</scope><scope>CQIGP</scope><scope>~WA</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7TB</scope><scope>8FD</scope><scope>FR3</scope><scope>KR7</scope></search><sort><creationdate>20150901</creationdate><title>Half thresholding eigenvalue algorithm for semidefinite matrix completion</title><author>Chen, YongQiang ; Luo, ZiYan ; Xiu, NaiHua</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c370t-602ad97947637abbd4b82037378dafe12bfb3aa33910229d75175c40f4672fcd3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2015</creationdate><topic>Algorithms</topic><topic>Applications of Mathematics</topic><topic>Convergence</topic><topic>Eigenvalues</topic><topic>Iterative methods</topic><topic>Mathematical models</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Optimization</topic><topic>Regularization</topic><topic>Robustness</topic><topic>全局最优解</topic><topic>半正定矩阵</topic><topic>参赛作品</topic><topic>对称矩阵</topic><topic>收敛性分析</topic><topic>特征值</topic><topic>算法</topic><topic>阈值</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Chen, YongQiang</creatorcontrib><creatorcontrib>Luo, ZiYan</creatorcontrib><creatorcontrib>Xiu, NaiHua</creatorcontrib><collection>维普_期刊</collection><collection>中文科技期刊数据库-CALIS站点</collection><collection>维普中文期刊数据库</collection><collection>中文科技期刊数据库- 镜像站点</collection><collection>CrossRef</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>Technology Research Database</collection><collection>Engineering Research Database</collection><collection>Civil Engineering Abstracts</collection><jtitle>Science China. Mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Chen, YongQiang</au><au>Luo, ZiYan</au><au>Xiu, NaiHua</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Half thresholding eigenvalue algorithm for semidefinite matrix completion</atitle><jtitle>Science China. Mathematics</jtitle><stitle>Sci. China Math</stitle><addtitle>SCIENCE CHINA Mathematics</addtitle><date>2015-09-01</date><risdate>2015</risdate><volume>58</volume><issue>9</issue><spage>2015</spage><epage>2032</epage><pages>2015-2032</pages><issn>1674-7283</issn><eissn>1869-1862</eissn><abstract>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.</abstract><cop>Beijing</cop><pub>Science China Press</pub><doi>10.1007/s11425-015-5052-y</doi><tpages>18</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1674-7283
ispartof Science China. Mathematics, 2015-09, Vol.58 (9), p.2015-2032
issn 1674-7283
1869-1862
language eng
recordid cdi_proquest_miscellaneous_1744730218
source Springer Nature
subjects Algorithms
Applications of Mathematics
Convergence
Eigenvalues
Iterative methods
Mathematical models
Mathematics
Mathematics and Statistics
Optimization
Regularization
Robustness
全局最优解
半正定矩阵
参赛作品
对称矩阵
收敛性分析
特征值
算法
阈值
title Half thresholding eigenvalue algorithm for semidefinite matrix completion
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T19%3A41%3A41IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Half%20thresholding%20eigenvalue%20algorithm%20for%20semidefinite%20matrix%20completion&rft.jtitle=Science%20China.%20Mathematics&rft.au=Chen,%20YongQiang&rft.date=2015-09-01&rft.volume=58&rft.issue=9&rft.spage=2015&rft.epage=2032&rft.pages=2015-2032&rft.issn=1674-7283&rft.eissn=1869-1862&rft_id=info:doi/10.1007/s11425-015-5052-y&rft_dat=%3Cproquest_cross%3E1744730218%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c370t-602ad97947637abbd4b82037378dafe12bfb3aa33910229d75175c40f4672fcd3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1744730218&rft_id=info:pmid/&rft_cqvip_id=665849994&rfr_iscdi=true