英语原文共 8 页
加权核规范最小化及其在图像去噪中的应用
摘要
作为低秩矩阵分解的凸松弛问题，核规范最小化近年引起了重要的研究兴趣。标准核范数最小化将每个奇异值均等地规则化以追求目标函数的凸性。然而，这极大地限制了它的能力和处理许多实际问题的灵活性（例如去噪），其中奇异值具有明确的物理性质意义，应该区别对待。在本文中我们研究加权核规范最小化（WNNM）问题，其中奇异值分配不同权重。在不同的加权条件下分析了WNNM问题的解决方案。然后，我们通过图像非局部自相似性将所提出的WNNM算法应用于图像去噪。实验结果清楚地表明所提出的WNNM算法优于许多最先进的去噪算法，如在定量测量和视觉感官视觉上都是品质的BM3D。
1.简介
低秩矩阵逼近是一种基于低秩矩阵退化观测的复原方法，在计算机视觉和机器学习中有着广泛的应用。例如，由人脸图像构成的矩阵的低秩性使我们能够对遮挡/损坏的人脸进行重建。Netlix用户数据矩阵的秩较低，主要是由于用户的选择受几个共同因素的影响。静态摄像机拍摄的视频片段具有清晰的低秩特性，可以根据低秩特性进行背景建模和前景提取。研究还表明，在自然图像中由非局部相似斑块构成的矩阵具有较低的秩，可以用于高性能的图像恢复任务。由于凸和非凸优化技术的迅速发展，近年来对低秩矩阵逼近的研究越来越多，许多重要的模型和算法也得到了报道。
低秩矩阵近似方法一般可分为两类:低秩矩阵分解(LRMF)方法和核范数最小化(NNM)方法。给定一个矩阵Y, LRMF的目标是找到一个矩阵X，它在一定的数据保真度函数下尽可能接近于Y，同时能够分解成两个低秩矩阵的乘积。从经典奇异值分解(SVD)到许多L1-范数鲁棒LRMF算法，已经提出了多种LRMF方法。
LRMF问题本质上是一个非凸优化问题。低秩矩阵近似的另一个研究方向。矩阵X的核范数，表示为，被定义为其奇异值的总和，即，表示X的第i个奇异值。NNM旨在是用X逼近Y，同时最小化X的核范数。NNM的一个显著优点是，它是对具有一定数据保真度项的非凸LRMF问题最紧密的凸松弛，因此近年来引起了极大的研究兴趣。一方面，Candes和Recht证明了通过求解NNM问题可以很好地恢复大多数低秩矩阵;另一方面，Cai等人证明了基于NNM的低秩矩阵逼近问题具有F-范数数据保真度，可以通过对观测矩阵奇异值的软阈值化操作轻松解决。也就是说，
（1）
其中是一个正常数，可以通过（2）得到，其中是Y的SVD，是带有参数lambda;的对角矩阵的软阈值函数。对于中的每一个对角函数，有（3）。上述奇异值软阈值方法已被广泛应用于解决基于NNM的子空间聚类问题，如矩阵补全、鲁棒主成分分析(RPCA)、低秩纹理和低秩表示(LRR)。
虽然NNM在低秩矩阵逼近中得到了广泛的应用，但它仍然存在一些问题。为了追求凸性质,核标准规范将每个奇异值同样对待,因此,软阈值算子在（3）中用相同的量收缩每一个奇异值。然而，这忽略了我们通常对矩阵奇异值的先验知识。例如，矩阵中的列(或行)向量通常位于低维子空间中;较大的奇异值通常与主要的投影方向有关，因此最好减少对奇异值的收缩，以保留主要数据分量。显然，NNM及其相应的软阈值算子并没有利用这种先验知识。虽然(1)中的模型是凸的，但是它没有足够的灵活性来处理许多实际问题。Zhang等人提出了一种截断核规范正则化(TNNR)方法。然而，TNNR的灵活性还不够，它进行了二元决策，即是否规范特定的奇异值。
为了提高核范数的灵活性，提出了加权核范数，并对其最小化问题进行了研究。矩阵X的加权核范数定义为
（4）
其中和是指定给的非负权重。加权核范数最小化(WNNM)在一般情况下是非凸的，比NNM更难求解。到目前为止，关于WNNM问题的研究还很少。
本文详细研究了具有F-范数保真度的WNNM问题。对不同权值条件下的解进行了分析，提出的WNNM算法与NNM问题的算法一样有效。WNNM对NNM进行了推广，极大地提高了NNM的灵活性。基于对问题的先验知识和理解，可以引入不同的权值或加权规则，而WNNM则有利于对潜在数据的估计。
作为一个重要的应用，我们采用了提出的WNNM算法对图像进行去噪。图像去噪的目的是通过噪声观测来估计潜在的干净图像。图像去噪作为低水平视觉中的一个经典和基础问题，多年来得到了广泛的研究;然而，去噪是研究和评价统计图像建模技术的理想实验平台，因此仍然是一个活跃的研究课题。近年来，图像非局部自相似(NSS)技术的应用极大地提高了图像的去噪性能。NSS先验指的是，对于自然图像中给定的局部图像块，可以在整个图像中找到许多与其相似的图像块。基准BM3D算法和最先进的LSSC和NCSR算法都是基于NSS先验的。直观地，通过将非局部相似的图像块向量叠加到一个矩阵中，这个矩阵应该是一个低秩矩阵，并且具有稀疏的奇异值。Wang等人在[26]中验证了这一假设，他们称之为非局域谱先验。因此，利用低秩矩阵近似方法可以设计去噪算法。采用NNM方法进行视频去噪。在[9]中，Dong等人将NNM和-范数组稀疏性相结合用于图像恢复，并得到了极具竞争力的结果。本文的贡献是双重的。首先，详细分析了WNNM优化问题，并给出了不同权值条件下的求解方法。其次，我们采用提出的WNNM算法进行图像去噪，以证明其在低水平视觉应用中的巨大潜力。实验结果表明，WNNM算法不仅在PSNR指标上优于现有的去噪算法，而且在局部结构保存上也优于现有的去噪算法，使得去噪效果更加直观。
2. 加权核范数的低秩极小化
2.1 问题
如第1节所述，低秩矩阵近似可以通过低秩矩阵分解和核范数最小化(NNM)来实现，而核范数最小化可以是一个凸优化问题。由于在[6]中证明了NNM可以很好地恢复大多数低秩矩阵，并且在[3]中证明了NNM可以有效地求解。更具体地说，(1)中的NNM模型通过对奇异值进行软阈值化得到解决方案 (参见(2))，利用F-范数度量观测数据矩阵Y与潜在数据矩阵X之间的差值(参见(3))。NNM对X的奇异值的处理是相等的。因此，相同的软阈值(即lambda;)将被应用到所有的奇异值,如(3)所示。这不是很合理,因为不同的奇异值可能有不同的重要性,因此他们应该区别对待。为此，我们使用(4)中定义的加权核范数对X进行正则化，并提出以下加权核范数最小化(WNNM)问题
（5）
然而，由于(5)中的目标函数一般不是凸函数，因此WNNM问题比NNM问题更难优化。在[3]中，采用子梯度法推导出NNM的解;遗憾的是，由于子梯度条件不再满足，类似的推导不能应用于WNNM。在第2.2节中，我们将详细讨论WNNM的求解。显然，当所有权值相同时，NNM是WNNM的一个特例。我们的解决方案将覆盖[3]中NNM的解决方案，而我们的推导要比[3]中基于复杂子梯度的推导简单得多。
2.2 优化
在分析WNNM的优化问题之前，我们首先给出了三个引理。
引理1：满足，我们有
（1）
（2）
引理2：具有和，如果权重满足，我们有，其中，，
引理3：和对角非负矩阵具有非升序对角元素，令为A的SVD，我们有
其中I是单位矩阵，和是矩阵A和W的第i个奇异值，和时，取得最大值。
上述引理的证明可在补充材料中找到。然后我们得到如下定理，它保证(5)中WNNM问题解的列空间和行空间仍然位于观测数据矩阵Y的对应空间中。
定理1：，由表示它的SVD，对于(5)中具有非负权向量w的WNNM问题，其解可以写为,其中是下面优化问题的解
（6）
证明：由表示U的互补空间的正交基集，我们可以将X写成，其中和分别是子空间U和中的分量。然后我们有
（引理1）
类似的，对于行空间基数V，我们有
正交矩阵U和V不会改变F范数和加权核范数，因此我们有
因此,如果我们有解决方案(6)的最小化问题,解决原WNNM问题(5)可以得。
基于上述引理和定理，我们讨论了WNNM问题在三种情况下的解:权值为非升序，为任意序，为非降序。
2.2.1 权重按非升序排列
根据定理1，我们得到(5)中WNNM问题在时的全局最优解。我们有下面的定理。
定理2。当权值满足时，(5)中的WNNM问题具有全局最优解
其中是Y的SVD，是具有权重向量的广义软阈值算子
证明：考虑到（6）中的优化问题，假设是一个对角矩阵，它具有与矩阵B相同的对角元素，我们有
（引理2）
因此,在这样一个权量条件下, (6)中的最优解有一个对角形式。sum;和都是对角矩阵,通过对每个元素软阈值处理得到解。根据定理1中的结论,(5)的最优解是。
定理2极大地扩展了[3]中的定理2.1(本文用(1)-(3)来描述)。我们证明了如果权值是非升序的，不一定具有相同的值，WNNM问题仍然是凸的，并且仍然可以通过对不同阈值的奇异值进行软阈值化得到最优解。Cai等人在[3]中给出的定理2.1是我们定理2的一个特例。与[3]中基于复杂子梯度的证明相比，我们的证明更加简洁。
2.2.2权重按任意顺序排列
在权值不是非升序而是任意序的情况下，(5)中的WNNM问题是非凸的，因此我们不能得到它的全局最小值。我们提出一种迭代算法来求解。
在定理1中，我们证明了(5)的解可以通过解(6)得到。设为B的SVD，我们迭代地解决以下优化问题
(7)
其中I是单位矩阵。
步骤1:给定非负对角矩阵Lambda;，我们求解
根据Frobenius范数的定义，我们有
（引理3）
并且P和Q的最优解是矩阵Lambda;的SVD的列和行基，由于Lambda;已经是对角矩阵，因此P和Q是置换矩阵，其使得对角矩阵具有非递增的有序对角元素。
步骤2：给定对角矩阵P和Q，我们求解
由于是一个具有非上升有序元素的对角矩阵，我们有
可以对对角矩阵的每一个元素进行软阈值处理操作。因为P和Q是只改变对角元素位置的置换矩阵，我们有
经过上述两个步骤之间的迭代，(6)可以通过对对角线元素进行排序并收缩奇异值来迭代求解:
（8）
基于定理1的结论，的最终估计可以由得到。
2.2.3权重按非降序排列
最后，我们考虑另一个特殊但非常有用的例子，即权值按非降序排列。基于2.2.2节提出的迭代算法，我们有以下推论。
推论1：如果权重满足，第2.2.2节中描述的迭代算法将有一个固定点
证明：在(8)中，将初始化为任意具有非升序对角元素的对角矩阵，我们有
因此，，我们有和，在软阈值处理操作后，仍然满足非升序。因此在下一个迭代中，P和Q仍然是单位矩阵，(7)的优化达到一个定点。基于定理1的结论，我们通过得到X的定点估计。
推论1中的结论是非常重要和有用的。矩阵的奇异值总是按非升序排列，较大的奇异值通常对应于数据矩阵中更重要的分量的子空间。因此，我们最好缩小较大的奇异值，也就是说，在加权核范数中分配较小的权重给较大的奇异值。在这种情况下，推论1保证了我们所提出的迭代算法有一个固定点。此外，这个固定点具有解析形式(即)。因此，在实践中，我们不需要真正的迭代，而是直接在一个步骤中获得所需的解决方案，这使得所提出的方法非常有效。在接下来的第3节中，我们将看到，推论1为我们提供了一种有效的去噪算法，其去噪性能优于几乎所有我们能找到的最先进的去噪算法。
3.WNNM用于图像去噪
图像去噪的目的是从嘈杂的观察y = x n重建原始图像x，其中n是含有零均值和方差的加性高斯白噪声。去噪不仅是许多视觉应用的重要预处理步骤，也是评价统计图像建模方法的理想实验平台。非局部意味着[1]的开创性工作引发了基于非局部自相似(NSS)的图像去噪方法的广泛研究。NSS指的是在自然图像中存在许多重复的局部模式，而那些与给定图像块相似的非局部的图像块可以在很大程度上帮助重建。基于NSS的图像去噪算法，如BM3D[7]、LSSC[22]和NCSR[10]，都取得了最先进的去噪效果。
对于图像y中的局部图像块，我们可以通过块匹配[7]等方法在整个图像(实际上，在一个足够大的局部窗口中)中搜索它的非局部相似的图像块。将这些非局部相似的图像块叠加到一个矩阵中，用表示，得到，其中和分别是原始图像和噪声的图像块矩阵。直观地说，应该是一个低秩矩阵，而低秩矩阵近似方法可以用来估计。通过对所有去噪后的图像进行聚类，可以对整个图像进行估计。事实上，在[15]中采用了NNM方法对视频进行去噪。我们将提出的WNNM模型应用于，估计用于图像去噪。通过使用噪声方差来对F-norm数据保真度项进行归一化，得到如下能量函数:
（9）
显然，现在的关键问题是权重向量w的确定。对于自然图像，我们有一个普遍的先验知识，即的较大奇异值比较小奇异值更重要，因为它们代表了的主要分量的能量。在去噪的应用中，奇异值越大，应该对奇异值的压缩越小。因此,一个自然的想法是分配给的权量，即第i个奇异值应该与成反比。我们让
（10）
其中cgt;0，是一个常数，n是在中相似图像块的数量，是为了避免除以零。
根据上述权重的定义，在2.2.3提出的WNNM算法可以直接用来解决模型(9),但仍有一个问题
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
