基于加权Schatten-1/2范数的低秩矩阵近似算法

Weighted Schatten-1/2 Norm Minimization for Low-Rank Matrix Approximation

摘要: 本文提出加权的Schatten-1/2拟范数求解低秩矩阵近似问题，该模型以加权的Schatten-1/2拟范数为目标函数，观测矩阵为约束。通过基于阈值的加权不动点迭代算法求解。该方法通过分配不同权值体现奇异值的重要性可更好地近似原来的低秩假设。另一方面，针对奇异值计算量大的问题引入约化奇异值分解。数值实验结果表明，该方法具有较快的收敛速度。

Abstract: In this paper, the low-rank matrix approximation problem is discussed with a weighted Schatten quasi-norm as the objective function, constrained by partial obtained data. The weights are in-troduced to measure the importance of different rank components. A weighted fixed point iterative thresholding algorithm is proposed based on the fixed point representation theory. The con-vergence analysis of the algorithm is provided. Numerical examples illustrate the effciency of our method.

1. 引言

低秩矩阵近似的目的是提取关键信息代替或恢复原始数据。随着其在大数据处理中的明显优势以及理论的深入研究，低秩矩阵近似技术已广泛地应用于解决图像恢复 [1]、遥感技术 [2]、推荐系统 [3] 等各类实际问题。例如，在图像恢复中，灰度图像可以用低秩矩阵或近似低秩矩阵表示。但某些特殊情况可能导致图像的一些灰度值丢失，如破损照片中的划痕和污迹，图像中的文字覆盖等。因此有必要对丢失的灰度值进行还原，以恢复原始图像。Candės [4] 将低秩矩阵近似问题描述为以下优化问题

$\begin{array}{l}\min rank\left(X\right)\\ s.t.X_{i,j}=M_{i,j},\forall \left(i,j\right)\in \Omega \end{array}$ (1.1)

$X\in R^{m\times n}$， $\Omega$ 表示待恢复矩阵M中可观测元素下标的集合。Candės分析了问题(1.1)的计算复杂度并证明其为NP-hard问题。随后，作为rank函数的凸包络，核范数被提出用来逼近问题(1.1)的目标函数

$\begin{array}{l}\underset{X}{\min }{\Vert X\Vert }_{\text{*}}\\ s.t.X_{i,j}=M_{i,j},\forall \left(i,j\right)\in \Omega \end{array}$ (1.2)

其中 ${\Vert X\Vert }_{*}={\Sigma }_k{\sigma }_k$， ${\sigma }_k$ 为X的奇异值， $k=1,\cdots ,r,r=\min \left\{m,n\right\}$。相关理论分析表明 [4]，相比于问题(1.1)，凸优化问题(1.2)更容易解决。

针对问题(1.2)出现了一些突破性的方法和成果 [5] [6] [7] [8]，然而，核范数需要最小化所有奇异值的和，使得近似效果不太理想 [9] [10] [11]。一般来说，较大的奇异值包含了数据矩阵的主要信息。图像灰度矩阵的较大奇异值包含了主要的边缘和纹理信息，因此处理奇异值时应小幅度收缩较大的奇异值，同时尽可能多的收缩较小的奇异值 [12]。为了更合理地度量不同奇异值的重要性，Gu [13] 提出了加权核范数模型解决问题(1.2)。加权核范数定义为 ${\Vert X\Vert }_{W,*}=\left|{\Sigma }_k{\omega }_k{\sigma }_k\right|$，其中 $W={\left({\omega }_1,{\omega }_2,\cdots ,{\omega }_r\right)}^{\text{T}}$， ${\omega }_k\ge 0$ 为奇异值 ${\sigma }_k$ 的非负权值， $k=1,2,\cdots ,r$。

在实际应用中，测量噪声普遍存在，以上方法的优化性能会下降，甚至会严重偏离初始问题(1.1)。为了更准确地逼近，非凸函数方法如 $Schatten\text{-}p\left(0<p<1\right)$ ( $S_p$ )拟范数被用来近似问题(1.1)中的目标函数

$\begin{array}{l}\underset{X}{\min }{\Vert X\Vert }_p^p\\ s.t.X_{i,j}=M_{i,j},\forall \left(i,j\right)\in \Omega \end{array}$ (1.3)

${\Vert X\Vert }_p={\left({\displaystyle {\sum }_k{\sigma }_k^p}\right)}^{\frac{1}{p}}$。问题(1.3)可由MM (Majorization-Minimization)迭代算法 [14] 计算数值解。然而，由于目标函数非凸、非光滑、非Lipschitz连续的性质，使得解析解难以求解 [13] [15] [16] [17] [18]。另一方面，参数p的变化也会对问题(1.3)产生很大影响。文献 [19] 指出当 $p\in \left[\frac{1}{2},1\right)$，近似结果相对理想，当 $p\in \left[0,\frac{1}{2}\right)$

时，结果基本不具参考性。Ding [14] 提出了问题(1.3)的一阶必要性条件，并通过解析阈值的不动点算法求解其迭代式。

基于加权核范数模型和 $S_p$ 拟范数，本文主要研究低秩矩阵近似模型

$\begin{array}{l}\min {\Vert X\Vert }_{W,S_p}^p\\ s.t.X_{i,j}=M_{i,j},\forall \left(i,j\right)\in \Omega \end{array}$ (1.4)

其中 ${\Vert X\Vert }_{W,S_p}^p={\displaystyle {\sum }_k{\omega }_k{\sigma }_k^p}$。当 ${\omega }_i=1$ 且 $p=1$ 时，问题(1.4)退化为问题(1.2)。

论文的其他部分安排如下。在第2部分中，根据奇异值的重要性，构造相对应的权值以更好的逼近rank函数。同时指出权值对不动点迭代算法效果的影响，即当权值越小，算法的综合性能越好。第3节使用约化的SVD(singular value decomposition)以减少奇异值计算量大的问题，并给出了基于阈值的不动点迭代算法及其收敛性。第4节，对比实验验证了算法的有效性。

下面给出本文的符号说明。不失一般性，假设 $m\ge n$。对于给定的矩阵 $X,Y\in R^{m\times n}$，

$\langle X,Y\rangle =trace\left(Y^{\text{T}}X\right)$， $trace\left(X\right)={\displaystyle {\sum }_i{X}_{i,i}}$， ${\Vert X\Vert }_F={\left({\displaystyle {\sum }_{i,j}{X}_{i,j}^2}\right)}^{\frac{1}{2}}={\left({\displaystyle {\sum }_{i=1}^n{\sigma }_i^2}\right)}^{\frac{1}{2}}$。向量 $x,y\in R^n$， ${\Vert x\Vert }_2={\left({\displaystyle {\sum }_{i=1}^n{x}_i^2}\right)}^{\frac{1}{2}}$，

$\langle x,y\rangle =x^{\text{T}}y$。

2. 全局必要最优条件

为更好地刻画矩阵的低秩结构，文献 [19] 指出 $S_{\frac{1}{2}}$ 拟范数正则化具有低秩无偏理论的特点。在本节中，

取 $p=\frac{1}{2}$，给出加权 $S_{\frac{1}{2}}$ 拟范数正则化模型和相应的不动点迭代算法。

阈值和加权处理

假设 $M\in R^{m\times n}$ 是一个秩为r的实数矩阵， $Y\in R^{m\times n}$ 是由M的可观测元素构成的矩阵，问题(1.4)的目的是找到最小秩矩阵 $X\in R^{m\times n}$ 近似M。Ding [19] 通过引入Tikhonov正则项，将问题(1.4)描述为以下形式

$\underset{X}{\min }\frac{1}{2}{\Vert P_{\Omega }\left(X\right)-P_{\Omega }\left(Y\right)\Vert }_F^2+{\Vert X\Vert }_{W,S_{\frac{1}{2}}}^{\frac{1}{2}}$ (2.1)

其中 ${\Vert X\Vert }_{W,S_{\frac{1}{2}}}^2={\displaystyle {\sum }_{i=1}^{\min \{m,n\}}{\omega }_i{\delta }_i}$， ${\omega }_i$ 为权值， ${\delta }_i$ 为奇异值， $P_{\Omega }(·)$ 为集合 $\Omega$ 的投影。

问题(2.1)的非凸和非光滑性使得问题不易求解。利用以下结论可以将问题(2.1)转化为可分离的问题进行求解。

引理1 [20] 假设 $A,B\in R^{m\times n}$， $\sigma \left(A\right)={\left[{\sigma }_1\left(A\right),\cdots ,{\sigma }_r\left(A\right)\right]}^{\text{T}},\sigma \left(B\right)={\left[{\sigma }_1\left(B\right),\cdots ,{\sigma }_r\left(B\right)\right]}^{\text{T}}$ 分别为矩阵 $A,B$ 的奇异值，并且 ${\sigma }_1\left(A\right)\ge \cdots \ge {\sigma }_r\left(A\right),{\sigma }_1\left(B\right)\ge \cdots \ge {\sigma }_r\left(B\right),r=\min \left\{m,n\right\}$。

则不等式 $tr\left(A^{\text{T}}B\right)\le tr\left(\sigma {\left(A\right)}^{\text{T}}\sigma \left(B\right)\right)$ 成立当且仅当存在正交矩阵 $U\in R^{m\times r},V\in R^{n\times r}$，使得

$A=U{\displaystyle {\sum }_{A}V},B=U{\displaystyle {\sum }_{B}V}$ (2.2)

${\Sigma }_A,{\Sigma }_B$ 分别为矩阵 $A,B$ 的奇异值矩阵。

引理2 [21] 假设 $Y\in R^{m\times n}$，且有 $Y=U{\displaystyle \sum V^{\text{T}}}$， $\Sigma =diag\left({\sigma }_1,\cdots ,{\sigma }_r\right),{\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r,$ $r=\min \left\{m,n\right\}$。问题(2.1)最优解的SVD为 $X=U\Delta V^{\text{T}}$，其中 $\Delta =diag\left({\delta }_1,\cdots ,{\delta }_r\right)$， ${\delta }_i\ge {\delta }_j$， $i\ge j$。 ${\delta }_i$ 是如下优化问题的解

$\begin{array}{l}\underset{{\delta }_1,\cdots ,{\delta }_r}{\min }{\displaystyle {\sum }_i^r\left[{\left({\delta }_i-{\sigma }_i\right)}^2+{\omega }_i{\delta }_i^{\frac{1}{2}}\right]}\\ s.t.{\delta }_i\ge 0,{\delta }_i\ge {\delta }_j,i\le j,i=1,\cdots ,r\end{array}$ (2.3)

引理1和引理2表明问题(2.1)可以转化为可分离问题(2.3)求解。对于问题(2.3)，讨论其一般项的求解。为文章的完整性起见，将文献 [19] 的证明整理如下。

引理3假设 $y\in R^n,\lambda >0,$ 令 $f_{\lambda }\left(x\right):={\left(x-y\right)}^2+\lambda x^{\frac{1}{2}}$。问题

$h_{\lambda }\left(y\right)=\underset{x\ge 0}{\arg \min }\left\{f_{\lambda }\left(x\right)\right\}$ (2.4)

的解可以表示为

$h_{\lambda }\left(y\right)=\{\begin{array}{c}{h}_{\lambda }\left(y\right),y>\frac{3}{4}{\lambda }^{\frac{2}{3}}\\ 0,y>\frac{3}{4}{\lambda }^{\frac{2}{3}}\end{array}$ (2.5)

其中

$h_{\lambda }\left(y\right)=\frac{2}{3}y\left(1+\cos \left(\frac{2\pi }{3}-\frac{2}{3}{\Phi }_{\lambda }\left(y\right)\right)\right)$ (2.6)

${\Phi }_{\lambda }\left(y\right)=\arccos \left(\frac{\lambda }{8}{\left(\frac{y}{3}\right)}^{-\frac{3}{2}}\right)$ (2.7)

证明： $\forall y\in R^n$， ${\Vert y\Vert }_{\frac{1}{2}}^{\frac{1}{2}}$ 是连续可微的。令 $f_{\lambda }\left(x\right)$ 的一阶导数为零

$y_i-x_i+\lambda \frac{sign\left(y_i\right)}{4\sqrt{\left|y_i\right|}}=0$ (2.8)

当且仅当 $x>0$ 时，(2.8)有非负解， $x\le 0$ 时， $f_{\lambda }\left(x\right)$ 有唯一解 $x=0$。因此，仅考虑 $x>0$ 的情况。

令 $\sqrt{\left|y_i\right|}=\eta ,y_i={\eta }^2$。当 $x_i>\frac{3}{4}{\lambda }^{\frac{2}{3}}$ 时，有

${\eta }^3-x_i\eta +\frac{\lambda }{4}=0$ (2.9)

假设 $r=\sqrt{\frac{\left|x_i\right|}{3}},q=\frac{\lambda }{8},\Phi =\arccos \left(\frac{q}{3}\right),$ (2.9)的三个解可以表示为： ${\eta }_1=-2r\cos \left(\frac{\Phi }{3}\right),$

${\eta }_2=2r\cos \left(\frac{\pi }{3}+\frac{\Phi }{3}\right),$ ${\eta }_3=2r\cos \left(\frac{\pi }{3}-\frac{\Phi }{3}\right)$ [11]。经验证， ${\eta }_3=2r\cos \left(\frac{\pi }{3}-\frac{\Phi }{3}\right)$ 是问题(2.4)的最优解，且解

的形式为

$y_i=\frac{2}{3}{x}_i\left(1+\cos \left(\frac{2\pi }{3}-\frac{2}{3}\lambda {\Phi }_{\lambda }\left(x_i\right)\right)\right)$ (2.10)

当 $x_i>\frac{3}{4}{\lambda }^{\frac{2}{3}}$ 时，证明与上述类似。

定义1 $\forall \lambda >0$, 向量阈值函数定义为

$H_{\lambda }\left(x\right):=\left(h_{\lambda }\left(x_1\right),h_{\lambda }\left(x_2\right),\cdots ,h_{\lambda }\left(x_n\right)\right),\forall x=\left(x_1,x_2,\cdots ,x_n\right)\in R^n$ (2.11)

$h_{\lambda }\left(x\right)$ 的形式如(2.5)所示。

假设秩为 $r$ 的矩阵 $Y\in R^{m\times n}$ 的SVD为 $Y=U{\displaystyle \sum V^{\text{T}}}$， $U\in R^{m\times r}、V\in R^{n\times r}$ 均为列正交矩阵， $\Sigma \in R^{r\times r}$ 为奇异值非增的对角矩阵。

对 $\forall \lambda >0$，由向量阈值函数可以定义矩阵阈值函数

${{\rm H}}_{\lambda }\left(Y\right):=U{\displaystyle {\sum }_{H_{\lambda }}{V}^{\text{T}}}$ (2.12)

${\Sigma }_{H_{\lambda }}=diag\left(H_{\lambda }\left({\sigma }_1\right),\cdots ,H_{\lambda }\left({\sigma }_r\right)\right)$。因此，问题(2.1)可以由矩阵阈值函数求解。本节的后续内容将会介绍由(2.12)表示的问题(2.1)解的形式以及权重对奇异值的影响。

引理3给出了当矩阵维数为1时的解的情况，现在考虑矩阵 $Y\in R^{m\times n}$。

定理1当且仅当权重满足 $0\le {\omega }_1\le \cdots \le {\omega }_r$ 时，问题(2.1)最优解的奇异值满足 ${\delta }_1\ge \cdots \ge {\delta }_r$。

证明：由引理2和引理3，问题(2.1)可分离出子问题

$f_{\delta }\left(x\right):={\left(\sigma -\delta \right)}^2+\omega {\delta }^{\frac{1}{2}}$ (2.13)

文献 [19] 指出， $f_{\delta }\left(x\right)$ 有唯一解 $h_{\omega }\left(\delta \right)$。

首先，证明当 ${\omega }_i<{\omega }_j$ 时，有 $h_{{\omega }_i}\ge h_{{\omega }_j}$。

当 $y<\frac{3}{4}{\omega }_i^{\frac{2}{3}}$ 且 $y<\frac{3}{4}{\omega }_j^{\frac{2}{3}}$ 时，由(2.5)，有 $h_{{\omega }_i}=h_{{\omega }_j}=0$。结论 $h_{{\omega }_i}\ge h_{{\omega }_j}$ 成立。

当 $y>\frac{3}{4}{\omega }_i^{\frac{2}{3}}$ 且 $y<\frac{3}{4}{\omega }_j^{\frac{2}{3}}$ 时，显然有 $h_{{\omega }_j}=0$。另一方面，由引理3的证明，当 $y>0$ 时有 $h_{{\omega }_i}>0$。因此，结论 $h_{{\omega }_i}\ge h_{{\omega }_j}$ 成立。

当 $y>\frac{3}{4}{\omega }_i^{\frac{2}{3}}$ 且 $y>\frac{3}{4}{\omega }_j^{\frac{2}{3}}$ 时，通过函数 $h_{\omega }\left(\delta \right)$ 的单调性证明结论。因为 $y>\frac{3}{4}{\omega }^{\frac{2}{3}}$，且 $\frac{\omega }{8}{\left(\frac{x}{3}\right)}^{-\frac{2}{3}}\in \left(0,1\right)$，则由(2.7)可得 ${\Phi }_{\omega }\left(y\right)\in \left(0,\frac{\pi }{2}\right)$，由此可得函数 $\cos \left(\frac{2}{3}-\frac{2}{3}{\Phi }_{\omega }\left(y\right)\right)$ 单调递减。因此， $h_{{\omega }_i}\ge h_{{\omega }_j}$ 成立。

然后，对给定 $\omega >0$，以下不等式显然成立

$\frac{2}{3}{y}_i\left(1+\cos \left(\frac{2\pi }{3}-\frac{2}{3}\Phi \right)\right)>\frac{2}{3}{y}_j\left(1+\cos \left(\frac{2\pi }{3}-\frac{2}{3}\Phi \right)\right),\forall y_i>y_j$.

综合两方面的证明，可以得到结论

$h_{{\omega }_i}\left(y_i\right)\ge h_{{\omega }_j}\left(y_j\right),\forall {\omega }_i<{\omega }_j,y_i>y_j$.

证毕。

文献 [14] [22] 将矩阵问题转化为易于求解的向量问题，同时表明非凸问题可以用阈值法解决。

引理4 [14] 令 $\lambda >0$，假设秩为 $r$ 的矩阵 $Y\in R^{m\times n}$ 的SVD为 $Y=U{\displaystyle {\sum }_Y{V}^{\text{T}}}$，对应的矩阵阈值函数为

${{\rm H}}_{\lambda }\left(Y\right):=U{\displaystyle {\sum }_{H_{\lambda }(\sigma )}{V}^{\text{T}}}$ (2.14)

则

${{\rm H}}_{\lambda }\left(Y\right):=\underset{X\in R^{m\times n}}{\arg \min }\left\{{\Vert X-Y\Vert }_F^2+\lambda {\Vert X\Vert }_{\frac{1}{2}}^{\frac{1}{2}}\right\}$ (2.15)

3. 最优算法及其收敛性分析

本节将给出非凸、非光滑和非Lipschitz连续的 $S_{\frac{1}{2}}$ 拟范数正则化问题全局最优解的不动点表示理论。 $\forall \mu >0,Z\in R^{m\times n}$，定义

$\begin{array}{l}{C}_W\left(X\right):={\Vert P_{\Omega }\left(X\right)-P_{\Omega }\left(Y\right)\Vert }_F^2+{\Vert X\Vert }_{W,\frac{1}{2}}^{\frac{1}{2}}\\ C_{W,\mu }:=\mu \left(C_W\left(X\right)-{\Vert P_{\Omega }\left(X\right)-P_{\Omega }\left(Z\right)\Vert }_F^2\right)+{\Vert X-Z\Vert }_F^2.\\ B_{\mu }\left(Z\right):=Z+\mu \left(P_{\Omega }\left(Y\right)-P_{\Omega }\left(X^{*}\right)\right)\end{array}$ (3.1)

定理2对 $\forall {\omega }_i,\mu >0$，假设正则化模型(2.1)的最优解为 $X^{*}$。令

$B_{\mu }\left(X^{*}\right):=X^{*}+\mu \left(P_{\Omega }\left(Y\right)-P_{\Omega }\left(X^{*}\right)\right)$

且 $B_{\mu }\left(X^{*}\right)$ 的SVD为

$U^{*}{\displaystyle {\sum }_{B_{\mu }\left(X^{*}\right)}{\left(V^{*}\right)}^{\text{T}}}$

则

$X^{*}\in {{\rm H}}_W\left(B_{\mu }\left(X^{*}\right)\right)$ (3.2)

因此，最优解的第i个奇异值为

${\sigma }_i\left(X^{*}\right)=\{\begin{array}{c}{h}_{{\omega }_i\mu ,\frac{1}{2}}\left({\sigma }_i\left(B_{\mu }\left(X^{*}\right)\right)\right),{\sigma }_i\left(B_{\mu }\left(X^{*}\right)\right)>\frac{\sqrt[3]{54}}{4}{\left({\omega }_i\mu \right)}^{\frac{2}{3}}\\ 0,{\sigma }_i\left(B_{\mu }\left(X^{*}\right)\right)\le \frac{\sqrt[3]{54}}{4}{\left({\omega }_i\mu \right)}^{\frac{2}{3}}\end{array}$ (3.3)

其中

$h_{{\omega }_i}\left(y\right)=\{\begin{array}{c}{h}_{{\omega }_i\mu ,\frac{1}{2}}\left({\sigma }_i\right)，{\sigma }_i>\frac{\sqrt[3]{54}}{4}{\left({\omega }_i\mu \right)}^{\frac{2}{3}}\\ 0，{\sigma }_i\le \frac{\sqrt[3]{54}}{4}{\left({\omega }_i\mu \right)}^{\frac{2}{3}}\end{array}$ (3.4)

$h_{{\omega }_i，\frac{1}{2}}\left({\sigma }_i\right)=\frac{2}{3}y\left(1+\cos \left(\frac{2\pi }{3}-\frac{2}{3}{\Phi }_{{\omega }_i}\right)\right)$ (3.5)

${\Phi }_{{\omega }_i}\left(y\right)=\arccos \left(\frac{{\omega }_i\mu }{8}{\left(\frac{y}{\sqrt[3]{54}}\right)}^{-\frac{2}{3}}\right)$ (3.6)

证明：

$\begin{array}{c}{C}_{W,\mu }\left(X,Z\right):=\mu \left(C_W\left(X\right)-{\Vert P_{\Omega }\left(X\right)-P_{\Omega }\left(Z\right)\Vert }_F^2\right)+{\Vert X-Z\Vert }_F^2\\ =\Vert X\Vert -2\langle X,Z+\mu \left(P_{\Omega }\left(Y\right)-P_{\Omega }\left(Z\right)\right)\rangle +\mu {\Vert X\Vert }_{W,S_{\frac{1}{2}}}^{\frac{1}{2}}\\ +\Vert Z\Vert +\mu {\Vert P_{\Omega }\left(Y\right)\Vert }_F^2-\mu {\Vert P_{\Omega }\left(Z\right)\Vert }_F^2\end{array}$

$\begin{array}{c}=\Vert X\Vert -2\langle X,B_{\mu }\left(Z\right)\rangle +\mu {\Vert X\Vert }_{W,S_{\frac{1}{2}}}^{\frac{1}{2}}\\ +\Vert Z\Vert +\mu {\Vert P_{\Omega }\left(Y\right)\Vert }_F^2-\mu {\Vert P_{\Omega }\left(Z\right)\Vert }_F^2\\ ={\Vert X-B_{\mu }\left(Z\right)\Vert }_F^2+\mu {\Vert X\Vert }_{W,S_{\frac{1}{2}}}^{\frac{1}{2}}+\Vert Z\Vert \\ +\mu {\Vert P_{\Omega }\left(Y\right)\Vert }_F^2-\mu {\Vert P_{\Omega }\left(Z\right)\Vert }_F^2-{\Vert B_{\mu }\left(Z\right)\Vert }_F^2\end{array}$ (3.7)

(3.7)的最后一个等式表明，最小化 $C_{W,\mu }\left(X,Z\right)$ 相当于求解问题

$\underset{X\in R^{m\times n}}{\min }\left\{{\Vert X-B_{\mu }\left(Z\right)\Vert }_F^2\text{+}\mu {\Vert X\Vert }_{W,S_{\frac{1}{2}}}^{\frac{1}{2}}\right\}.$ (3.8)

假设 $X^{*}$ 是 $C_W\left(X\right)$ 的全局最优解，由文献 [11] 可知， $X^{*}$ 也是 $C_{W,\mu }\left(X,X^{*}\right)$ 的全局最优解。显然(3.2)成立。

类似于问题(2.3)的求解方法，问题(3.8)可分离的求解

$\min \left\{x_i^2-2x_i{\left[B_{\mu }\left(Z\right)\right]}_i\text{+}\mu {\omega }_i{\left|x_i\right|}^2\right\}$ (3.9)

令(3.9)函数的一阶导数为0

$x_i^2-{\left[B_{\mu }\left(Z\right)\right]}_i\text{+}\mu {\omega }_i\frac{\text{sign}\left(x_i\right)}{4\sqrt{\left|x_i\right|}}=0$ (3.10)

由引理3的证明， ${\left[B_{\mu }\left(Z\right)\right]}_i$ 满足不等式 ${\left[B_{\mu }\left(Z\right)\right]}_i>\frac{3}{4}{\left({\omega }_i\mu \right)}^{\frac{2}{3}}$。文献 [11] 表明只需比较 $f_{{\omega }_i}\left(h_{{\omega }_i,\frac{1}{2}}\right)$ 和 $f_{{\omega }_i}\left(0\right)$ 即可得到原问题的最优解。经验证，当且仅当 $\left|{\left[B_{\mu }\left(Z\right)\right]}_i\right|\le \frac{\sqrt[3]{54}}{4}{\left({\omega }_i\mu \right)}^{\frac{2}{3}}$ 时有 $f_{{\omega }_i}\left(h_{{\omega }_i,\frac{1}{2}}\right)\le f_{{\omega }_i}\left(0\right)$。后

续证明与引理3类似。

证毕。

定理2给出了问题(1.4)最优解的形式。以上证明表示可以用阈值不动点迭代算法求解非凸、非光滑、非Lipschitz问题(1.4)。不动点算法的基本框架描述如下。

优化问题的结果取决于正则化参数的选择，即权重向量。将第k次迭代的 ${\omega }_i$ 取为

${\omega }_i=\frac{\sqrt{96}}{9{\mu }_0}{\left({\left[\sigma \left(X_k\right)\right]}_{r_k}\right)}^{\frac{3}{2}}$ (3.11)

$r_k$ 表示矩阵 $X_k$ 的秩。为延续 ${\omega }_k$ 的取值，将向量 ${\omega }_k$ 更新为

${\omega }_{k+1}=\max \left\{\bar{\lambda },\min \left\{\eta {\omega }_{k,}\frac{\sqrt{96}}{9{\mu }_0}{\left({\left[\sigma \left(X_k\right)\right]}_{r_k}\right)}^{\frac{3}{2}}\right\}\right\}$ (3.12)

其中 $\eta \in \left(0,1\right)$ 为常数， $\bar{\lambda }$ 为足够小的正实数。显然序列 $\left\{{\omega }_k\right\}$ 单调减小且收敛。采用延续技术改进的不动点算法如算法2所示。

在算法2中，主要的计算量来自奇异值分解。Drineas [23] 提出了一种近似的SVD算法代替传统的SVD以减少计算成本，完整的阈值不动点迭代算法如算法3所示。

下面给出算法3的收敛性分析。

引理5 [19] 给定 $\lambda >0,\mu \in \left(0,1\right]$， $\left\{X_k\right\}$ 为(3.2)生成的序列，则

(1) 假设 $X^{\text{*}}$ 为 $\left\{X_k\right\}$ 的任一聚点，则 $C_{\lambda }\left(X_k\right)$ 单调递减收敛于 $C_{\lambda }\left(X^{\text{*}}\right)$，

(2) $X_k$ 是渐进正则的，即 ${\lim }_{k\to \infty }\Vert X_{k+1}-X_k\Vert =0$，

(3) $\left\{X_k\right\}$ 的任一聚点均为问题(1.4)的全局最优解。

4. 实验结果与分析

在本节中，WHFPA的有效性将通过一些实验来说明。

在WHFPA和HFPA (基于阈值的不动点迭代算法)中，终止准则取为

$\frac{{\Vert X_{k+1}-X_k\Vert }_F}{\max \left\{1,{\Vert X_k\Vert }_F\right\}}<xtol,$

评估WHPFA和HFPA结果X与原始矩阵M之间的接近度

$rel:=\frac{{\Vert M-\bar{X}\Vert }_F}{{\Vert M\Vert }_F}.$

在约化SVD算法中，设置样本cs的个数随矩阵的秩而变化。另外，初始矩阵 $X_0$ 由矩阵可观测元素组成，初始权值 $W_0$ 设为初始矩阵 $X_0$ 的奇异值。生成随机矩阵的方法如下。随机生成秩为r的矩阵

$M_L\in R^{m\times r}$， $M_R\in R^{n\times r}$，则 $M=M_L{M}_R^T$。 $SR=\frac{p}{mn}$ 为采样比，p是采样数。此外，对于矩阵类型的定义 [19] 如下。一个矩阵称为“简单”的满足： $\frac{p}{r\left(m+n-r\right)}\times SR>0.5$， $\frac{p}{r\left(m+n-r\right)}>2.6$，“复杂”矩阵定义为 $\frac{p}{r\left(m+n-r\right)}\times SR\le 0.5$， $\frac{p}{r\left(m+n-r\right)}\le 2.6$。

由于 $S_{\frac{1}{2}}$ 阈值不动点迭代算法比SVP (Singular Value Projection) [24]，MSS (Muti-Schatten p norm Surrogate) [25]，SVT [26] (Singular Vaule Thresholding)等方法更有效 [19]，其中SVT解决的是秩最小化问题，SVP用于Tikhonov正则化问题，MSS用于解决Schatten-p正则化问题。本文只比较HFPA和WHFPA两种方法，与其他方方法的比较不再赘述。在相同的测试环境下，算法时间越短，准确率越高，效果越好。给出了各矩阵在维数、秩和抽样比上结果的差异。

4.1. 相同的尺寸，不同的抽样比和等级

取m = n = 100，设xtol = 10⁻⁶，矩阵M的秩r从8增加到20，采样比SR分别为0.307、0.451、0.589、0.720。

对于每个子问题，随机生成100个矩阵进行测试，结果如表1所示。在约化SVD算法中设置cs = 35，μ = 0.9。实验结果表明，HFPA和WHFPA的精度相似，在10⁻⁶左右。在时间上，WHFPA将会比HFPA整体短一些。一般来说，两种方法相比，在维数小且矩阵为“困难”的情况下，WHFPA比HFPA更有效。

Table 1. Comparison of HFPA and WHFPA for randomly created small but hard matrices (m = n = 100, r = 8:4:20, xtol = 10−6)

表1. HFPA和WHFPA关于随机矩阵的比较m = n = 100, r = 8:4:20, xtol = 10⁻⁶)

4.2. 相同的采样比，不同的维度和等级

我们将维数从500增加到2000，采样比为0.570，取xtol = 10⁻⁴。

随机生成100个矩阵进行测试，最终得到如下结果，详见表2。在表2中，设置μ = 0.24，在约化SVD中设置可变参数cs。HFPA和WHFPA的精度相似，在10⁻⁴左右。在时间上，维数越大，WHFPA与HFPA差距越明显。两种方法相比，在维数大且矩阵为“困难”的情况下，WHFPA比HFPA更有效。

Table 2. Comparison of HFPA and WHFPA for randomly created large but hard matrices (SR = 0.570, xtol = 10−4)

表2. HFPA和WHFPA关于随机矩阵的比较(SR = 0.570, xtol = 10⁻⁴)

4.3. 有噪声的随机矩阵

假设带噪声的矩阵定义为

$B_{ij}=M_{ij}+Z_{ij}$

其中，矩阵 $Z\in R^{m\times n}$ 是方差为 $\sigma$，零均值的高斯矩阵。设置μ = 0.9，分别在方差10⁻²和10⁻¹的噪声矩阵下进行试验，矩阵维数设置为m = n = 1000，取xtol = 10⁻⁴。实验数据详见表3。WHFPA比HFPA的精度好，在10⁻⁴左右。在时间上，HFPA是WHFPA的2倍。两种方法相比，在有噪声的情况下，WHFPA比HFPA更有效。

Table 3. Comparison of HFPA and WHFPA for randomly created noise disturbance matrices (m = n = 1000, xtol = 10−4)

表3. HFPA和WHFPA关于有噪声随机矩阵的比较(m = n = 1000, xtol = 10⁻⁴)

5. 结论

本文利用 $S_{\frac{1}{2}}$ 拟范数正则化方法，提出了一种基于奇异值贡献度的权重处理方法。针对非凸、非光滑、非Lipschitz优化问题，首先给出了阈值不动点迭代算法中权值对奇异值的影响，然后给出了经过延续处理以及约化奇异值分解的改进算法。实验结果表明，WHFPA性能优于HFPA，说明了算法的有效性。