本期将介绍小编在第一篇论文中提出的一个算法,量子奇异值阈值(quantum singular value thresholding,QSVT)算法。第一篇小论文的发表心得一文中提到,这个算法小编花了大概半年多才完成设计,后续又针对该算法设计了一个小型实例的量子线路,基于qit库在matlab上进行了简单的实验验证。因此对这个算法的介绍会比论文中描述的详细一些。希望对大家有所帮助。

今天咱们聊的简单一些,介绍下这个算法的前世:经典的奇异值阈值(singular value thresholding,SVT)

本期导读

  1. SVT定义
  2. SVT应用

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;
第三步:做乘法。根据左右奇异向量和更新后的奇异值重新构成新的矩阵。

SVT应用

起源

在我接触量子矩阵机(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的应用场景

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

图6 SVT的应用场景

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

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

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

小结

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

注:

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

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

入门量子机器学习领域,也许可以从解读Phase Estimation算法开始

发表评论

后才能评论

评论(1)

  • zhangshihao 量子达人 2018年11月3日

    奇异值阈值算法可用于矩阵恢复和矩阵填充,但未必是矩阵恢复领域性能最好的方法,比如常用的还有 凸优化工具包 cvx 中的 sedumi, sdpt3 方法等;这是否是开始审稿人不太重视将其量子化的原因呢(笑,随便猜的~~)从论文可以看出姐姐你的数学功底很强啊~~