Singular Value Thresholding (SVT) 奇异值阈值

大家好，又见面了，我是你们的朋友全栈君。

[本文链接：http://blog.csdn.net/shanglianlm/article/details/46009387，转载请注明出处]

为了求解问题

因为它是非凸的，我们求解一个它的近似算法

对于一个大的$\tau$值，它可以用下列等式接近

其中第一项为核范式（奇异值的和），第二项为Frobenius范式。

1. Singular Value Thresholding (SVT) 奇异值阈值

   * 奇异值收缩(singular value shrinkage)*

   首先我们考虑一个秩为$r$的矩阵$X \in R^{n_{1} x n_{2}}$的奇异值分解如下：
   
   其中 $U$ 和 $V$ 分别为 $n_{1} × r$ 和 $n_{2} × r$ 的正交矩阵，奇异值为$\rho_{i}$非负的。

   对于每个$\tau ≥ 0$，我们有软阈值操作$D_{\tau}$:
   
   其中$t_{+}$表示的$t$非负部分，即 $t_{+}=max(0, t)$。换句话说，这个软阈值操作仅仅应用于矩阵 X <script type=”math/tex” id=”MathJax-Element-56″>X</script> 的奇异值上，使它们趋于零。这也是为什么我们将其成为奇异值收缩(singular value shrinkage)的原因。

   * Singular Value Thresholding (SVT) 奇异值阈值*

   又因为奇异值收缩(singular value shrinkage)是核范式的近似操作(具体证明见[3])，因此上式可以转化为：
   

   它的迭代方式为：
   

   这个算法受到压缩感知中迭代算法的启发，在迭代过程中对矩阵进行SVD，然后将较小的奇异值设置为0，生成新的矩阵进行迭代。该算法运算速度快，对于高位低秩矩阵的恢复非常有效。

2. 用拉格朗日乘子法解释

   原问题为：

   

   其拉格朗日函数为：

   

   强对偶成立，且拉格朗日函数的鞍点是原函数与对偶问题的最优解，即

   

   其迭代解为：

   

参考或延伸材料：
[1] 斯坦福SVT软件
[2] Generalized Singular Value Thresholding
[3] A singular value thresholding algorithm for matrix completion
[4] Exact Matrix Completion via Convex Optimization