• 论文 • 上一篇    

Toeplitz矩阵填充的四种流形逼近算法比较

韩如意1, 王川龙2   

  1. 1. 太原理工大学数学学院, 太原 030024;
    2. 太原师范学院工程科学计算山西省高等学校重点实验室, 太原 030619
  • 收稿日期:2017-09-07 出版日期:2018-09-15 发布日期:2018-08-08
  • 通讯作者: 王川龙,E-mail:clwang1964@163.com.
  • 基金资助:

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

韩如意, 王川龙. Toeplitz矩阵填充的四种流形逼近算法比较[J]. 计算数学, 2018, 40(3): 325-336.

Han Ruyi, Wang Chuanlong. THE COMPARISON OF FOUR MANIFOLD APPROXIMATION ALGORITHMS FOR TOEPLITZ MATRIX COMPLETION[J]. Mathematica Numerica Sinica, 2018, 40(3): 325-336.

THE COMPARISON OF FOUR MANIFOLD APPROXIMATION ALGORITHMS FOR TOEPLITZ MATRIX COMPLETION

Han Ruyi1, Wang Chuanlong2   

  1. 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
  • Received:2017-09-07 Online:2018-09-15 Published:2018-08-08
本文提出Toeplitz矩阵填充的四种流形逼近算法。在左奇异向量空间中对已知部分运用最小二乘法逼近,形成新的可行矩阵;并将对角线上的元素分别用均值,l1范数,l范数和中间数四种方法逼近使得迭代后的矩阵仍保持Toeplitz结构,节约了奇异向量空间的分解时间。最终找到合理的低秩矩阵来逼近未知的高秩矩阵,进而精确地完成Toeplitz矩阵的填充。理论上,分析了在一定条件下算法的收敛性。实验上,通过取不同的采样密度进行数值实验展示了四种算法的优劣。实验结果说明均值算法和l范数算法大多用的时间较少,但是当采样密度和矩阵规模较大时,中间数算法的精度较高。
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.

MR(2010)主题分类: 

()
[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] 刘嘉诚, 陈先进, 段雅丽, 李昭祥. 改进的PNC方法及其在非线性偏微分方程多解问题中的应用[J]. 计算数学, 2022, 44(1): 119-136.
[2] 李姣芬, 秦树娟, 张丽, 候文婷. 多元统计分析中一类矩阵迹函数最小化问题的有效算法[J]. 计算数学, 2021, 43(1): 70-86.
[3] 吴敏华, 李郴良. 求解带Toeplitz矩阵的线性互补问题的一类预处理模系矩阵分裂迭代法[J]. 计算数学, 2020, 42(2): 223-236.
[4] 刘丽霞, 王川龙. 基于均值的Toeplitz矩阵填充的子空间算法[J]. 计算数学, 2017, 39(2): 179-188.
[5] 刘仲云, 刘成志, 张育林. 对称正定Toeplitz方程组的多级迭代求解[J]. 计算数学, 2012, 34(4): 397-404.
[6] 袁永新,戴华. 线性流形上的广义中心对称矩阵反问题[J]. 计算数学, 2005, 27(4): 383-394.
[7] 周富照,胡锡炎,张磊. 线性流形上对称正交对称矩阵逆特征值问题[J]. 计算数学, 2003, 25(3): 281-292.
[8] 张忠志,胡锡炎,张磊. 线性流形上Hermite-广义反Hamilton矩阵反问题的最小二乘解[J]. 计算数学, 2003, 25(2): 209-218.
[9] 黄艾香,刘之行,张引娣. 基于近似惯性流形的后验Galerkin的方法[J]. 计算数学, 2001, 23(3): 289-298.
[10] 张磊,谢冬秀,胡锡炎. 线性流形上双对称阵逆特征值问题[J]. 计算数学, 2000, 22(2): 129-138.
[11] 李开泰,侯延仁. N-S方程一般近似惯性流形构造和逼近[J]. 计算数学, 1999, 21(3): 269-282.
[12] 廖安平. 线性流形上矩阵方程AX=B的一类反问题及数值解法[J]. 计算数学, 1998, 20(4): 371-376.
阅读次数
全文


摘要