一种求解矩阵填充问题的混合增广拉格朗日乘子算法

一种求解矩阵填充问题的混合增广拉格朗日乘子算法

0混合增广拉格朗日乘子矩阵填充算法近年来，矩阵填充问题引起了许多科学家的研究兴趣。矩阵填充问题是将已知的元素嵌入样本矩阵，并使用重建的低秩矩阵接近样本矩阵，这与计算机视觉接近。矩阵填充问题首次由Cand’es和Recht有关凸优化问题（1）的研究，已经有大量的成果．例如，Fazel本文提出的混合型增广拉格朗日乘子矩阵填充算法是通过定义混合型奇异值阈值算子，将经典的增广拉格朗日乘子算法进行改进后得到的．具体是对ALM算法运行中奇异值分解所产生的阈值进行混合型奇异值阈值算子处理．当迭代次数逐渐增加时，就会发现在奇异值数量减少，奇异值的数值减小的同时，矩阵填充的计算效率极大提高，从而节约了计算花费．因此，新算法在求解矩阵填充问题上明显优于经典的增广拉格朗日乘子算法．首先先给出一些定义：其中σ定义2（硬阈值算子）其中变量σ∈R，τ是阈值．定义3（软阈值算子）其中变量σ定义4（奇异值阈值算子）在本文中，我们提出一种新的混合型奇异值阈值算子：当阈值σ定义5（混合型奇异值阈值算子）对于任意参数τ≥0,z>1，矩阵的秩是r,其中也就是说，当σ1该算法1.1增广拉格朗日乘子算法在这一节中，我们简要介绍增广拉格朗日乘子算法，以便于后文数值实验中算法比较．增广拉格朗日乘子法表示矩阵的奇异值分解，算法1增广拉格朗日乘子法（ALM算法）给定采样集合Ω，采样矩阵D=P1.2基于lam的新算法在这一节中，我们提出新算法．具体步骤如下：算法2混合增广拉格朗日乘子（HALM）算法．给定采样集合Ω，采样矩阵D=P第3-4步同ALM算法．与ALM算法相比，我们提出的新算法HALM是在其基础上进行改进后得到的，具体是将ALM算法运行中奇异值分解所产生的阈值进行混合型奇异值阈值算子处理．在数值实验中，我们发现，当迭代次数逐渐增加时，奇异值数量减少，奇异值的数值也在减小，矩阵填充的计算效率极大提高，从而节约了计算花费，进而优化了算法．2新算法halm中的混合阈值算子的运行时间在本节中，我们对ALM算法和HALM算法进行了比较，所有的数值实验都是在机器类型为Intel(R)Core(TM)i7-6700CPU@3.40GHZ，内存16GB,Windows7系统的个人机上用Matlab(R2016a）进行的，也就是说实验中所选取的M和P在数值实验中，M∈R此外，对于两个算法，我们选取参数τ接下来，在新算法HALM中混合阈值算子中参数z的选择，我们选取了n=1000,1500,2000的矩阵，比较不同的z和n在运行时间上的差异．当n=1000,1500,2000时，新算法HALM的运行时间始终随着z的变化而变化，而当参数z选取z=1.4时，新算法HALM的运行时间普遍较低．因此，在新算法HALM中，我们选择混合阈值算子的参数z=1.4.从4个表中我们看到新算法HALM在计算时间上总是少于ALM算法的．针对同规模的矩阵而言，随着采样率p的增加，新算法HALM和ALM算法的迭代次数相差不大，但新算法HALM在时间上明显少于ALM算法；针对相同的采样率而言，随着矩阵大小的变化，当p∈{0.3,0.4,0.5,0.6}时，新算法HALM的收敛性和运行时间都优于ALM算法，特别是矩阵规模越大越明显，这些都说明新算法HALM的有效性和可行性．3增广拉格朗日乘子算法本文先提出了一种新的阈值算子：混合型奇异值阈值算子．然后将该算子与经典的算法增广拉格朗日算法相结合，得到了一种新的矩阵填充算法，即混合型增广拉格朗日乘子算法．与增广拉格朗日乘子算法相比，该算法具有更高的精度．由表1-4可以看出，在相同参数下，我们的算法在运行时间上明显优于增广拉格朗日乘子算法．在新提出的算法中，对阈值的混合处理节省了大部分时间，能够有效地填充矩阵．这些都是基于一般