矩阵秩极小化问题的一种快速求解算法

2023-09-27崔安刚

榆林学院学报 2023年5期

关键词：情形灰度重构

崔安刚,杨宏

(榆林学院数学与统计学院,陕西榆林 719000)

近年来,矩阵秩极小化问题受到了很多来自于不同领域研究者的广泛关注。它已经被广泛地应用于系统识别与控制、人脸识别、图像处理等领域。在数学上,矩阵秩极小化问题可以表示为如下矩阵优化问题[1-3]:

(1)

其中b∈Rp,A∶Rm×n→RP是一个仿射变换映射,p(≤mn)表示采样数。不失一般性,本文假设m≤n.

迭代硬阈值(Iterative Hard Thresholding, IHT[3])算法是求解矩阵秩极小化问题(1)的一个非常有效的经典方法。但是IHT算法对噪声非常敏感,在噪声情形下往往具有较慢的收敛速度。因此设计一种可以快速求解无约束矩阵秩极小化问题(1)的快速算法是一个值得研究的问题。

本文将在IHT算法的基础之上设计一种快速求解矩阵秩极小化问题(1)的迭代阈值算法,使其具有收敛速度快的特点。

1 预备知识

定义1[3]给定矩阵Y∈Rm×n,考虑其奇异值分解Y=U[Diag(σ),0]VT,其中U和V分别是m×n和n×n的正交矩阵,σ=(σ1,σ2,…,σm)T表示矩阵Y的按从大到小排列的奇异值向量。对于给定的正整数r(1≤r≤m),定义矩阵硬阈值算子Hr∶Rm×n→Rm×n为:

Hr(X)=U[Diag(Hr(σ)),0]VT,

其中Hr(σ)表示硬阈值算子,它的作用是只保留σ中前r个大的元素,其余元素设置为0。

2 快速迭代硬阈值算法

求解矩阵秩极小化问题(1)的IHT算法可以描述为:初始化X0∈Rm×n,k=1,

Xk=Hr(B(Xk-1)),

(2)

其中B(Xk-1)=Xk-1+A*(b-A(Xk-1)),A*表示A的伴随算子。

为了加速IHT算法,本文借鉴文献[4]中的加速技巧,将IHT算法修正为:初始化X0∈Rm×n,Y1=X0,k=1,

(3)

其中p,q>0,δ∈(0,4],t1=1。本文将修正IHT算法(3)称为快速迭代硬阈值(Fast Iterative Hard Thresholding, FIHT)算法。FIHT算法的优点是它可以通过控制参数p,q,δ的取值,使其具有较快的收敛速度。

3 数值实验

本节将通过数值实验来验证FIHT算法的有效性。本实验考虑将FIHT算法应用到随机低秩矩阵补全和低秩灰度图像补全问题中,并和IHT算法作比较。算法的停机准则定义为:

或者最大迭代步数3000。利用相对误差

来评估算法所产生的最优解Xopt,其中X*表示真实的低秩矩阵。给定采样率sr∈(0,1],采样数p可以通过Matlab命令p=round(sr*m*n)确定。在FIHT算法中,设定p=0.1,q=50,δ=4。

3.1 随机低秩矩阵补全

首先,考虑随机低秩矩阵的补全问题。为了方便起见,假设m=n,并且生成秩为r=30的n×n矩阵X*=N1N2,其中N1∈Rn×r和N2∈Rr×n是两个高斯随机矩阵。对于有噪声的情形,假设X*被随机噪声ɑE所污染,其中E∈Rm×n表示高斯随机矩阵,ɑ>0表示噪声水平。

表1展示了在无噪声情形下采样数为sr=0.45时IHT算法与FIHT算法重构随机低秩矩阵的数值结果比较。表2展示了在有噪声情形下采样数为sr=0.45时IHT算法与FIHT算法重构随机低秩矩阵的数值结果比较,在实验中,噪声强度ɑ设定为0.005。结果显示,无论是在无噪声情形下还是在有噪声情形下,FIHT算法在保证重构精度的同时,算法的收敛速度也明显快于IHT算法。