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

THE MINIMUM-RANK GRAM MATRIX COMPLETION VIA FIXED POINT CONTINUATION METHOD

作　　者：马玥 

机构地区：[1]中科院数学与系统科学研究院,数学机械化重点实验室,北京100190

出　　处：《系统科学与数学》2010年第11期1501-1511,共11页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(60821002/F02,60911130369,10871194)资助课题

摘　　要：仿射限制条件下的低秩矩阵的恢复问题广泛地出现在控制、信号处理及系统识别等许多领域中.此问题可以凸松弛为带仿射限制条件的矩阵核范数的极小化问题.尽管后者能够转化为标准的半定规划问题求解,但是对于规模较大的矩阵其产生的计算量也很大.为此提出一种新的求解Gram矩阵核范数极小化问题的一阶算法—改进的不动点迭代算法(FPC-BB),并给出了算法的收敛性分析.算法以不动点迭代算法(FPC)中的算子分裂技术为基础,通过改进阈值算子T_v来求解低秩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）.

关 键 词：低秩Gram矩阵 平方和 核范数 

分 类 号：O177.91[理学—数学]