量子奇异值阈值算法QSVT（一）

今天咱们聊的简单一些，介绍下这个算法的前世：经典的奇异值阈值（singular value thresholding，SVT）。

SVT的定义很容易理解，设输入矩阵为Y，Y的左奇异向量矩阵为U，右奇异向量矩阵为V，奇异值为$\sigma_j$，其中$\sigma_1>\sigma_2>…..>\sigma_r$。

设奇异值阈值SVT算子表示为D_tau, 其中tau为阈值参数。通过SVT的作用，原始矩阵Y的左右奇异向量矩阵不变，奇异值同时收缩了tau（即奇异值同时减去tau值，若结果大于0，则将其作为新的奇异值；否则，将新的奇异值置为0）。

图1 singular value thresholding

举个简单的例子，图1中右中绿色方框的矩阵为输入矩阵Y，经过奇异值分解后，得到图中左边黄色方框标注的左右奇异向量矩阵和奇异值。

设阈值tau=5，则所有的奇异值均减去5，减去5之后的值若大于0，则直接作为新的矩阵的奇异值；若减去5之后的值小于0，则将奇异值设置为0。

最终将左右奇异向量和新的奇异值相作用，得到新的矩阵即为SVT作用在矩阵Y之后的输出。

以上是SVT的定义和简单的举例，应该很容易理解。简单总结下：

SVT可以理解为简单的三步操作。

第一步：做分解。对矩阵做奇异值分解，得到左右奇异向量和奇异值；

第二步：做减法。把奇异值根据参数tau进行收缩，如果奇异值大于tau，新的奇异值等于原来的减去tau，否则就得到0；

第三步：做乘法。根据左右奇异向量和更新后的奇异值重新构成新的矩阵。

在我接触量子矩阵机（SMM）算法之前，我并不认识SVT，只知道它和奇异值分解很像，那SVT究竟有什么用？它的应用会不会很窄？如果是这样，作为研究对象，它的影响力就会小很多。

这个问题当时我并没有考虑到，因为在研究这个算法时，我的目标是设计SMM的量子算法，并非SVT算法本身。非常感谢涂老师提出的这个宝贵问题。

于是针对该问题，我对SVT进行了一周左右的调研。我在Web of Science里搜索题目中包括singular value thresholding的文章，找到了近20篇文献，其中近3年（2015年-2017年）的在当时一共有8篇文章。然后又以最新的一篇文章为基础（IEEE transactions on pattern analysis and machine intelligence 出版年: 2017-Mar-03），搜索了一些参考文献。

通过这些文章及其参考文献，总共选取了大约30篇左右的文献，在Xmind（一个思维导图工具）中进行关键词和关键信息的提取，目的是总结SVT的应用场景。在这30多篇文章中，发现了一个共同的关键词：Low-rank。如图2所示。

图2 SVT应用的文献调研

这个关键字引出了新概念的学习，关于低秩的介绍，官方语言是：在线性代数中，一个矩阵A的列秩是A的线性独立的纵列的极大数。这个理解起来有点晦涩（晦涩的解释我总是记不住）。

于是针对这个概念在网上搜索了蛮久的，最终找到了一个比较简单的解释，它是以图像为例进行的说明，即：矩阵的秩描述了图像中信息的简单与复杂的程度。如图3所示。

图 3 低秩矩阵

我们打个比方，比如图3左边的草原图，如果都是草，重复的元素很多，元素很相似，这时候表示这张草原图的矩阵的秩就会很低。如果再加一些其他元素呢？比如图3右边这一张，变幻莫测的乌云、芬芳的花朵、一小片树木。这时候图中包含的信息多了、丰富了，矩阵的秩也就变大了。

我们再重复下这个观点：矩阵的秩描述了图像中信息的简单与复杂的程度。

从图像检索的角度看，图像基本是可以通过低秩重构的。举一个简单的例子，如图4所示。这张图呢，可以转换成矩阵表示的形式。然后我们对它先做一个奇异值分解，这时候通过奇异值进行图像的重构。可以看到由不同个奇异值重构之后的图片效果。是不是很有趣？

图4 奇异值分解的举例

那么低秩和我的研究对象SVT之间有怎样的关系呢？我们再来看一些低秩的应用场景。

我们从具体的场景切入这个问题。

首先设想这样一个场景，夜晚、大雨，我们开着车，“”雨刷“”刷刷刷的刷着，雨太大，尤其像南京的梅雨季节，雨刷刷的再快，还是看不清路，是不是很危险。这时候有一个高科技的车前窗，透过它，你可以看到一个晴朗夜晚的路面。是不是很神奇？这个车前窗在未来就是人工智能的产物。这里面包含了一个重要的应用：也就是场景1中的去雨痕。

此外，还有很多有趣的场景。包括把有阴影遮挡的人脸进行还原、监视视频的运动分离、图像修复/图像去燥、等等，如图5所示。

图5 Low-rank 应用场景

这些场景是在前面提到的论文中提取出的一些典型场景，这些场景要解决的问题，都可以转换为低秩问题。这些问题的解决方法，又都可以采用SVT算法。

最后，我们回到SVT的应用场景。

图6 SVT的应用场景

秩最小化通常是一个万能的正则化工具，可以用来获得一个矩阵的低秩的解。

通常它可以转换为易于求解的问题，比如核范数最小化（Nuclear Norm Minimization，NNM），这些转化后的问题又可以通过迭代的执行SVT算法求解。

所以SVT作为一个基本的算法模块，在智能计算中具有很广泛的应用。当然这些论文中除了采用原始的SVT算法，也有很多它的变形算法。我的研究对象是原始的SVT算法。

关于经典的SVT今天就介绍到这里，主要通过一些图解介绍了两个概念：SVT和低秩，以及它们的应用场景。下一期就介绍正式的QSVT算法，敬请期待。

注：

作者：Duan.Bojia (QubitLab)
编辑：Zoe
校对：量豆豆

本文原创，首发在《量子机器学习》微信公众号，欢迎关注。最后感谢Zoe在量子客对本文的再次整理、校验与编辑。