• 论文 • 上一篇    下一篇

基于均值的Toeplitz矩阵填充的子空间算法

刘丽霞1, 王川龙2   

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

    国家自然科学基金(11371275).

刘丽霞, 王川龙. 基于均值的Toeplitz矩阵填充的子空间算法[J]. 计算数学, 2017, 39(2): 179-188.

Liu Lixia, Wang Chuanlong. THE SUBSPACE ALGORITHM WITH MEAN VALUE FOR TOEPLITZ MATRIX COMPLETION[J]. Mathematica Numerica Sinica, 2017, 39(2): 179-188.

THE SUBSPACE ALGORITHM WITH MEAN VALUE FOR TOEPLITZ MATRIX COMPLETION

Liu Lixia1, 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 030012, China
  • Received:2016-05-10 Online:2017-05-15 Published:2017-07-18
本文提出一种基于均值的Toeplitz矩阵填充的子空间算法.通过在左奇异向量空间中对已知元素的最小二乘逼近,形成了新的可行矩阵;并利用对角线上的均值化使得迭代后的矩阵保持Toeplitz结构,从而减少了奇异向量空间的分解时间.理论上,证明了在一定条件下该算法收敛于一个低秩的Toeplitz矩阵.通过不同已知率的矩阵填充数值实验展示了Toeplitz矩阵填充的新算法比阈值增广Lagrange乘子算法在时间上和精度上更有效.
This paper proposes a subspace algorithm with mean value for the Toeplitz matrix completion.By the least squares approximation to the known entries in the left singular vector space,this algorithm forms a new feasible matrix,and the matrices generated by iteration keep Toeplitz structure by making use of averaging the diagonal entries.So that,the new algorithm reduces the time of decomposition in the singular vector space.In theory,we prove that the algorithm converges to a Toeplitz matrix with low rank under reasonable conditions.Finally,numerical experiments with different known entry ratio show the new algorithm can be faster and achieve higher precision than the ALM (augmented Lagrange multiplier) algorithm for Toeplitz matrix completion.

MR(2010)主题分类: 

()
[1] Zhang L, Lieven V. Interior-point method for nuclear norm approximation with application to system identification[J]. SIAM. J. Matrix Anal. A., 2010, 31(3):1235-1256.

[2] Amit Y, Fink M, Srebro N, Ullman S. Uncovering shared structures in multiclass classification[A]. 24th International Conference on Machine Learning(ICML), 2007, 17-24.

[3] Argyriou A, Evgeniou T, Pontil M. Multi-task feature learing[J]. Adv. Neural Information Processing Systems, 2007, 19:41-48.

[4] Eldén L. Matrix Methods in Data Mining and Pattern Recognization[A]. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2007, 10(4):377-379.

[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] Tomasi C, Kanade T. Shape and motion from image streams under orthography:a factorization method[J]. Int. J. Comput Vision, 1992, 9:137-154.

[7] Bertalmio M, Sapiro G, Caselles V, Ballester C. Image inpainting[J]. Comput. Grapher, (SIGGRAPH 2000), 2000, 34:417-424.

[8] Bennett J, Lanning S. The netflix prize[J]. In Proceedings of KDD Cup and Workshop, 2007.

[9] Fazel M, Hindi H, Boyd S P. A rank minimization heuristic with application to minimum order system approximation[A]. Proc. Am. Control Conf., 2001, 6:4734-4739.

[10] Fazel M. Matrix rank minimization with applications[D]. Stanford University, 2002.

[11] Candès E J, Plan Y. Matrix completion with noise[J]. Proceedings of the IEEE, 2010, 98(6):925-936.

[12] 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.

[13] 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.

[14] 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.

[15] Haldar J P, Hernando D. Rank-Constrained Solutions to Linear Matrix Equations Using PowerFactorization[J]. IEEE Signal Process. Lett., 2009, 16(7):584-587.

[16] Keshavan R H, Montanari A, Sewoong O. Matrix Completion From a Few Entries[J]. IEEE Trans. Inform. Theory, 2010, 56(6):2980-2998.

[17] Lee K, Bresler Y. ADMiRA:Atomic Decomposition for Minimum Rank Approximation[J]. IEEE Trans. Inform. Theory, 2010, 56(9):4402-4416.

[18] Wang Z, Lai M J, Lu Z, Fan W, Davulcu H, Ye J. Orthogonal Rank-One Matrix Pursuit for Low Rank Matrix Completion[J]. SIAM J. Sci. Comput., 2015, 37(1):488-514.

[19] Candès E J, Recht B. Exact matrix completion via convex optimization[J]. Found. Comput. Math., 2009, 9(6):717-772.

[20] 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.

[21] 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.

[22] 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.

[23] 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.

[24] Dai W, Milenkovic O. SET:an algorithm for consistent matrix completion[A]. IEEE International Conference on Acoustics, Speech, and Signal Processing, 2010, 3646-3649.

[25] 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.

[26] Chen C, He B, Yuan X. Matrix completion via an alternating direction method[J]. Ima. J. Numer. Anal., 2012, 32(1):227-245.

[27] Yuan M, Joseph R, Zou H. Structured variable selection and estimation[J]. Annals of Applied Statistics, 2009, 3(4):1738-1757.

[28] 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.

[29] Jain P, Netrapalli P, Sanghavi S. Low-rank matrix completion using alternating minimization[J]. Statistics, 2012, 665-674.
[1] 冯艳昭, 张澜. 子空间约束下矩阵方程ATXB+BTXTA=D的解及最佳逼近[J]. 计算数学, 2020, 42(2): 246-256.
[2] 吴敏华, 李郴良. 求解带Toeplitz矩阵的线性互补问题的一类预处理模系矩阵分裂迭代法[J]. 计算数学, 2020, 42(2): 223-236.
[3] 贾仲孝, 孙晓琳. 计算矩阵函数双线性形式的Krylov子空间算法的误差分析[J]. 计算数学, 2020, 42(1): 117-130.
[4] 夏雨晴, 张振跃. 子空间聚类的重建模型及其快速算法[J]. 计算数学, 2019, 41(1): 1-11.
[5] 郭峰. 非线性耦合Schrödinger-KdV方程组的一个局部能量守恒格式[J]. 计算数学, 2018, 40(3): 313-324.
[6] 韩如意, 王川龙. Toeplitz矩阵填充的四种流形逼近算法比较[J]. 计算数学, 2018, 40(3): 325-336.
[7] 周茜, 雷渊, 乔文龙. 一类线性约束矩阵不等式及其最小二乘问题[J]. 计算数学, 2016, 38(2): 171-186.
[8] 李姣芬, 张晓宁, 彭振, 彭靖静. 基于交替投影算法求解单变量线性约束矩阵方程问题[J]. 计算数学, 2014, 36(2): 143-162.
[9] 刘仲云, 刘成志, 张育林. 对称正定Toeplitz方程组的多级迭代求解[J]. 计算数学, 2012, 34(4): 397-404.
[10] 张春赛, 胡良剑. 时滞均值回复θ过程及其数值解的收敛性[J]. 计算数学, 2011, 33(2): 185-198.
[11] 顾桂定,朱文跃. 多右端非对称位移方程组的种子投影方法[J]. 计算数学, 2004, 26(2): 211-224.
[12] 白中治,仇寿霞. 关于具优势对称部分的不定线性代数方程组的分裂极小残量算法[J]. 计算数学, 2002, 24(1): 113-128.
阅读次数
全文


摘要