计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  在线办公 | 
计算数学  2018, Vol. 40 Issue (3): 325-336    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |   
Toeplitz矩阵填充的四种流形逼近算法比较
韩如意1, 王川龙2
1. 太原理工大学数学学院, 太原 030024;
2. 太原师范学院工程科学计算山西省高等学校重点实验室, 太原 030619
THE COMPARISON OF FOUR MANIFOLD APPROXIMATION ALGORITHMS FOR TOEPLITZ MATRIX COMPLETION
Han Ruyi1, Wang Chuanlong2
1. Institution of Mathematics, Taiyuan University of Technology, Taiyuan 030024, China;
2. Higher Education Key Laboratory of Engineering Science Computing in Shanxi Province, Taiyuan Normal University, Taiyuan 030619, China
 全文: PDF (397 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 本文提出Toeplitz矩阵填充的四种流形逼近算法。在左奇异向量空间中对已知部分运用最小二乘法逼近,形成新的可行矩阵;并将对角线上的元素分别用均值,l1范数,l范数和中间数四种方法逼近使得迭代后的矩阵仍保持Toeplitz结构,节约了奇异向量空间的分解时间。最终找到合理的低秩矩阵来逼近未知的高秩矩阵,进而精确地完成Toeplitz矩阵的填充。理论上,分析了在一定条件下算法的收敛性。实验上,通过取不同的采样密度进行数值实验展示了四种算法的优劣。实验结果说明均值算法和l范数算法大多用的时间较少,但是当采样密度和矩阵规模较大时,中间数算法的精度较高。
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词矩阵填充   Toeplitz矩阵   流形   l1范数   l&infin   范数     
Abstract: This paper proposes four manifold approximation algorithms for toeplitz matrix completion. A new feasible matrix is formed by using the least squares method in the left singular vector space. And the elements on the diagonal are approximated by the mean value, the l1 norm, the l norm and the intermediate value to make the iterative matrix keep the Toeplitz structure. So that, the algorithm reduces the time of decomposition in the singular vector space. Finally find a reasonable low rank matrix to approximate the unknown high rank matrix, and then accurately complete the Toeplitz matrix completion. In theory, the convergence of the algorithm under certain conditions is analyzed. In experiment, numerical experiments are carried out by taking different sampling densities to show the advantages and disadvantages of the four algorithms. The experimental results show that the mean value algorithm and the l norm algorithm are mostly used for less time, but the precision of the intermediate value algorithm is higher when the sampling density and matrix size are large.
Key wordsmatrix completion   Toeplitz matrix   Manifold   l1 norm   l norm   
收稿日期: 2017-09-07;
基金资助:

国家自然科学基金(11371275)和山西省自然科学基金(201601D011004)资助.

通讯作者: 王川龙,E-mail:clwang1964@163.com.     E-mail: clwang1964@163.com
引用本文:   
. Toeplitz矩阵填充的四种流形逼近算法比较[J]. 计算数学, 2018, 40(3): 325-336.
. THE COMPARISON OF FOUR MANIFOLD APPROXIMATION ALGORITHMS FOR TOEPLITZ MATRIX COMPLETION[J]. Mathematica Numerica Sinica, 2018, 40(3): 325-336.
 
[1] Bennett J,Lanning S.The netflix prize[J].In Proceedings of KDD Cup and Workshop,2007.
[2] Bertalmio M,Sapiro G,Caselles V,Ballester C.Image inpainting[J].Comput.Grapher,(SIGGRAPH 2000),2000,34:417-424.
[3] Argyriou A,Evgeniou T,Pontil M.Multi-task feature learing[J].Adv.Neural Information Processing Systems,2007,19:41-48.
[4] Tomasi C,Kanade T.Shape and motion from image streams under orthography:a factorization method[J].Int.J.Comput Vision,1992,9:137-154.
[5] Mesbahi M,Papavassilopoulos G P.On the rank minimization problem over a positive semidefinite linear matrix inequality[J].IEEE Transactions on Automatic Control,1997,42:239-243.
[6] Moon Y S,Park P G,Kwon W H.Delay-dependent robust stabilization of uncertain state-delayed systems[J].Internation Journal of Control,2001,74(14):1447-1455.
[7] Candès E J,Plan Y.Matrix completion with noise[J].Proceedings of the IEEE,2010,98(6):925-936.
[8] Chen P,Suter D.Recovering the missing components in a large noisy low-rank matrix:application to sfm source[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26:1051-1063.
[9] Abernethy F,Evgeniou T,Vert J P.A new approach to collaborative filtering:operator estimation with spectral regularization[J].Journal of Machine Learning Research,2009,10:803-826.
[10] Nicolas Boumal,Absil P A.RTRMC:A Riemannian trust-region method for low-rank matrix completion[A].Annual conference on Neural Information Processing Systems 25th,2011,24:406-414.
[11] Keshavan R H,Montanari A,Sewoong O.Matrix Completion From a Few Entries[J].IEEE Trans.Inform.Theory,2010,56(6):2980-2998.
[12] Lee K,Bresler Y.ADMiRA:Atomic Decomposition for Minimum Rank Approximation[J].IEEE Trans.Inform.Theory,2010,56(9):4402-4416.
[13] Candès E J,Recht B.Exact matrix completion via convex optimization[J].Found.Comput.Math.,2009,9(6):717-772.
[14] Toh K C,Yun S.An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems[J].Pacific J.Optimi.,2010,6:615-640.
[15] Cai J F,Candès E J,Shen Z.A singuar value thresholding algorithm for matrix completion[J].SIAM J.Optim.,2010,20:1956-1982.
[16] Lin Z,Chen M,Wu L,Ma Y.The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[M].UIUC Technicial Report UIUL-ENG-09-2214,2010.
[17] Lin Z,Ganesh A,Wright J,Wu L,Chen M,Ma Y.Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix[A].IEEE International Workshop on Computational Advances in Multi-sensor Adaptive Processing,Aruba,Dutch Antilles,2009,56(3):707-722.
[18] Dai W,Milenkovic O.SET:an algorithm for consistent matrix completion[A].IEEE International Conference on Acoustics,Speech,and Signal Processing,2010,3646-3649.
[19] Ma S,Goldfarb D,Chen L.Fixed point and Bregman iterative methods for matrix rank minimization[J].Math.Program.,2011,128(1-2):321-353.
[20] Chen C,He B,Yuan X.Matrix completion via an alternating direction method[J].Ima.J.Numer.Anal.,2012,32(1):227-245.
[21] Yuan M,Joseph R,Zou H.Structured variable selection and estimation[J].Annals of Applied Statistics,2009,3(4):1738-1757.
[22] Ma Y,Zhi L.The minimum-rank gram matrix completion via modified fixed point continuation method[A].International Symposium on Symbolic and Algebraic Computation 36th,2011,241-248.
[23] Jain P,Netrapalli P,Sanghavi S.Low-rank matrix completion using alternating minimization[J].Statistics,2012,665-674.
[24] 刘丽霞,王川龙.基于均值的Toeplitz矩阵填充的子空间算法[J].计算数学,2017,2(39):179-188.
[1] 王川龙, 张江梅. 基于F-模的Hankel矩阵填充的保结构阈值算法[J]. 计算数学, 2018, 39(1): 60-72.
[2] 刘丽霞, 王川龙. 基于均值的Toeplitz矩阵填充的子空间算法[J]. 计算数学, 2017, 39(2): 179-188.
[3] 杨平, 徐康丽, 蒋耀林. K-power系统在 Grassmann流形上的单侧模型降阶方法[J]. 计算数学, 2016, 37(1): 41-56.
[4] 刘仲云, 刘成志, 张育林. 对称正定Toeplitz方程组的多级迭代求解[J]. 计算数学, 2012, 34(4): 397-404.
[5] 徐仲,安晓虹,陆全. 求解周期三对角Toeplitz方程组的一种新修正算法[J]. 计算数学, 2008, 29(4): 291-295.
[6] 余品能, 王煜. Toeplitz矩阵相乘的一种新快速算法[J]. 计算数学, 2008, 29(3): 207-216.
[7] 彭小飞,黎稳. Hermite Toeplitz 类系统的预因子[J]. 计算数学, 2008, 29(3): 197-206.
[8] 雷渊,廖安平. 线性流形上一类矩阵方程的最佳逼近问题[J]. 计算数学, 2007, 28(1): 1-10.
[9] 袁永新,戴华. 线性流形上的广义中心对称矩阵反问题[J]. 计算数学, 2005, 27(4): 383-394.
[10] 陆全,徐仲,叶正麟. Toeplitz矩阵之逆矩阵的新分解式及快速算法[J]. 计算数学, 2005, 26(3): 191-197.
[11] 周富照,胡锡炎,张磊. 线性流形上对称正交对称矩阵逆特征值问题[J]. 计算数学, 2003, 25(3): 281-292.
[12] 张忠志,胡锡炎,张磊. 线性流形上Hermite-广义反Hamilton矩阵反问题的最小二乘解[J]. 计算数学, 2003, 25(2): 209-218.
[13] 黄艾香,刘之行,张引娣. 基于近似惯性流形的后验Galerkin的方法[J]. 计算数学, 2001, 23(3): 289-298.
[14] 张磊,谢冬秀,胡锡炎. 线性流形上双对称阵逆特征值问题[J]. 计算数学, 2000, 22(2): 129-138.
[15] 李开泰,侯延仁. N-S方程一般近似惯性流形构造和逼近[J]. 计算数学, 1999, 21(3): 269-282.

Copyright 2008 计算数学 版权所有
中国科学院数学与系统科学研究院 《计算数学》编辑部
北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发
技术支持: 010-62662699 E-mail:support@magtech.com.cn
京ICP备05002806号-10