• 论文 • 上一篇    下一篇

基于改进的不动点迭代算法的低秩Gram矩阵的恢复

马玥   

  1. 中科院数学与系统科学研究院, 数学机械化重点实验室, 北京 100190
  • 收稿日期:2010-10-26 修回日期:1900-01-01 出版日期:2010-11-25 发布日期:2010-11-25

马玥. 基于改进的不动点迭代算法的低秩Gram矩阵的恢复[J]. 系统科学与数学, 2010, 30(11): 1501-1511.

MA Yue. The Minimum-Rank Gram Matrix Completion via Fixed Point Continuation Method[J]. Journal of Systems Science and Mathematical Sciences, 2010, 30(11): 1501-1511.

The Minimum-Rank Gram Matrix Completion via Fixed Point Continuation Method

MA Yue   

  1. Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190
  • Received:2010-10-26 Revised:1900-01-01 Online:2010-11-25 Published:2010-11-25
仿射限制条件下的低秩矩阵的恢复问题广泛地出现在控制、信号处理及系统识别等许多领域中.此问题可以凸松弛为带仿射限制条件的矩阵核范数的极小化问题.尽管后者能够转化为标准的半定规划问题求解,但是对于规模较大的矩阵其产生的计算量也很大.为此提出一种新的求解~Gram矩阵核范数极小化问题的一阶算法---改进的不动点迭代算法(FPC-BB),并给出了算法的收敛性分析.算法以不动点迭代算法(FPC)中的算子分裂技术为基础,通过改进阈值算子~$\D_\nu$来求解低秩~Gram 矩阵的恢复问题.同时,还引入~Barzilai-Borwein技术进行参数的选取,提高了算法的收敛速度.
数值实验显示算法不仅能够很快地将低秩~Gram矩阵精确地恢复出来,对于一些非低秩矩阵的恢复问题也能得出较好的结果.
The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm
minimization. Although the latter can be transformed into a semidefinite
programming problem, which is computationally expensive to solve when the matrices are large. In this paper, we propose a new modified fixed point iterative algorithm for solving the nuclear norm minimization problem and prove the convergence of the algorithm. By using the Barzilai-Borwein technique to accelerate the convergence, we get a fast and robust algorithm, which we call
FPC-BB (Fixed Point Continuation with Barzilai-Borwein Technique).

MR(2010)主题分类: 

()
[1] 戚妮,罗勇,林望. 基于类Lyapunov函数的非线性切换系统的Reach-While-Stay性质验证[J]. 系统科学与数学, 2019, 39(12): 1964-1971.
[2] 林望,吴敏,杨争锋,曾振柄. 基于符号数值混合计算的混成系统Lyapunov函数构造[J]. 系统科学与数学, 2012, 32(5): 610-625.
[3] 郭峰. SDPTools:基于Maple的高精度求解SDP软件包[J]. 系统科学与数学, 2010, 30(11): 1512-1521.
[4] 李轶. 一类半正定多项式的配平方和算法[J]. 系统科学与数学, 2008, 28(4): 490-504.
[5] 梅长林;张文修. 利用局部加权拟合方法检验线性回归关系[J]. 系统科学与数学, 2002, 22(4): 467-480.
阅读次数
全文


摘要