Page 104 - 应用声学2019年第4期

564 2019 年 7 月

√
引入折中因子λ(λ = 1/ m，m为矩阵 W 的行 在这里，利用增广拉格朗日函数来求解问
数)，将双目标优化问题 (1) 转化为一个单目标优化 题 (3)，可以得到如下函数：
问题 [16] ：
Lag(D, X, Y , µ)
min rank(D) + λ∥X∥ 0
= ∥D∥ ∗ + λ∥X∥ 1 + ⟨Y , W − D − X⟩
s.t. W = D + X. (2) 2
+ µ∥W − D − X∥ /2. (5)
F
由于求解问题 (2) 属于 NP 问题，所以需要进
关于增广拉格朗日乘子法目前存在两种方法，
行进一步转化。由于矩阵的秩的凸包是矩阵的核
流程见表1 和表 2，其中在求解时，需要借助 Shrink-
范数 (其值等于矩阵的奇异值之和)，矩阵的 0 范数
age算子：
的凸包是矩阵 1 范数 (其值等于矩阵的元素绝对值

之和)，因此将问题 (2) 可以转化为下面的凸优化问 a − δ, a ∈ (δ, +∞),



题 [15] ：
H δ (a) = a + δ, a ∈ (−∞, −δ), (6)



min ∥D∥ ∗ + λ∥X∥ 1  0, a ∈ [−δ, δ],
s.t. W = D + X, (3)
式(6)中，a ∈ R，δ > 0。
求解方法包括增广拉格朗日乘子法 (Augmented
Lagrange multiplier, ALM) 和加速近端梯度 (Ac- 表 2 不精确的增广拉格朗日乘子法
celerated proximal gradient, APG)算法 [16] 。 Table 2 Inexact augmented Lagrange multiplier
1.2.1 增广拉格朗日乘子法
算法二：不精确增广拉格朗日乘子法
增广拉格朗日乘子法可以求解如下问题： (Inexact augmented Lagrange multiplier, IALM)
输入：数据矩阵 W ，最大迭代次数 Item 以及参数 λ
min f(M)
1. Y 0 = W ;µ 0 > 0; k = 0.
s.t. h(M) = 0, (4)
2. 如果不收敛，开始下面的循环
( )
其中，f : R → R，h : R → R 。 3. (U, S, V ) = svd W − X k + Y k ;
n
m
n
µ k
T
表 1 精确的增广拉格朗日乘子法 4. D k+1 = UH −1(S)V ;
µ
k ( )
Y k
Table 1 Exact augmented Lagrange multiplier 5. X k+1 = H λµ −1 W − D k+1 − ; % 更新 X
k µ k
6. Y k+1 = Y k + µ k (W − D k+1 − X k+1 );
算法一：精确增广拉格朗日乘子法 7. 更新 µ k 和 k;
(Exact augmented Lagrange multiplier, EALM)
8. 结束循环
输入：数据矩阵 W ，最大迭代次数 Item 以及参数 λ
输出：稀疏矩阵 X
1. Y ∗ = W ;µ 0 > 0; k = 0.
0
2. 如果不收敛，开始下面的循环
1.2.2 加速近端梯度算法
∗
∗
3. D 0 = D , X 0 = X , j = 0;
k+1 k k+1 k
加速近端梯度算法，也叫加速逼近梯度法，可
4. 如果不收敛，开始下面的循环
( Y ∗ ) 以求如下问题：
5. (U, S, V ) = svd W − X j + k ;
k+1
µ k
j+1 T
6. D = UH −1(S)V ; min f(M) = g(M) + h(M)/µ, (7)
k+1 µ
k ( Y ∗ )
7. X j+1 = H −1 W − D j+1 + k ; % 更新 X
k+1 λµ k+1
k µ k 其中，函数g(M)和h(M)是凸函数。
8. 更新 j;
将加速近端梯度算法运用于求解问题 (3)。凸
9. 结束循环;
优化问题转化为
10. Y ∗ = Y ∗ + µ k (W − D j+1 − X j+1 );
k+1 k k+1 k+1
2
11. 更新 µ k 和 k; min ∥D∥ ∗ + λ∥X∥ 1 + ∥W − D − X∥ /2µ. (8)
F
12. 结束循环
那么当 µ 逐渐趋近于 0 时，问题 (8) 的解也就是问
输出：稀疏矩阵 X
题 (3)的解。求解这个问题的主要步骤见表3。