稀疏表达：向量、矩阵与张量

《稀疏表达：向量、矩阵与张量》由会员分享，可在线阅读，更多相关《稀疏表达：向量、矩阵与张量（17页珍藏版）》请在金锄头文库上搜索。

1、稀疏表达是近年来 SP, ML, PR, CV 领域中的一大热点，文章可谓是普天盖地，令人目 不暇给。老板某门课程的课程需要大纲，我顺道给扩展了下，就有了这个上中下三篇介绍性 质的东西。遗憾的是，我在绝大多数情况下实在不算是一个勤快的人，这玩意可能充满 bug， 更新也可能断断续续，尽请诸位看官见谅了。顺道一提，ICCV09 有一个相关的 tutorial 。 据传博文里公式数量和其人气是成反比例关系的，一个公式可以驱散 50%的读者，我 写完这个（上）之后点了点公式数量，觉得大约是要无人问津了。所以，在介绍稀疏表达之 前，让我们先来展示下其在 computer vision 中的应用，吸引下

2、眼球。 首先是图像恢复（以前有人贴过 Obama 还记得不），由左侧图像恢复出右侧结果 然后是类似的图像 inpainting 然后是图像去模糊，左上为输入模糊图像，右下为输出清晰图像及估计的相机运动 （其 实是 PSF），中间均为迭代过程: 再然后是物体检测（自行车），左侧输入图像，中间为位置概率图，右侧为检测结果 当然我个人还推荐 Yi Ma 的 sparse face，这个在对抗噪声的效果上很棒，比如下图中 左侧的那张噪声图像（你能辨认是哪位不？这方法可以！） 且说 sparse representation 这个概念，早在 96-97 年的时候就火了一把。最著名的大 约要数 Natur

3、e 上的某篇文章，将稀疏性加入 least square 的 regularization，然后得到了具 有方向特性图像块（basis）。这样就很好的解释了初级视皮层（V1）的工作机理，即对于 线段的方向选择特性 。 几乎同一时期 ， 著名的 LASSO 算法也被发表在 J. Royal. Statist. Soc B。Lasso 比较好的解决了 least square (l2 norm) error + l1 norm regularization 的问题。然 而，这个时候绝大多数人没有意识到（或者没法解决）这 l1 norm 和稀疏性之间的联系。其 实早在这之前，Osher 等人提出的

4、Total Variation （TV）已经包含了 l1 norm 的概念了， 只不过 TV 原本是连续域上的积分形式。（啥？你不知道 Osher想想 Level Set 吧） 在进入现代的压缩感知、稀疏表示这一课题前，让我们来首先回顾下这一系列问题的 核心，即线性方程组 其中矩阵，通常而言是满秩的。向量。 现在已知，求解 。学过线性代数的同学可能都会说：这个不难啊，因为， 故 而这个方程组是欠定的，所以有无穷多组解啊，咱还可以算算基础解系啥的 但是如果我们希望其解 尽可能的稀疏：比如（即 中非零元个数） 尽可能的小。 那么问题就会变得比较微妙了，下图给出了问题的形象示意。 换言之给定 m 维

5、空间中一组过完备的基，如何选择最少个数的基向量，重构 给定向量，其严格定义可以写成 时光之轮播快到 20032004 年，Donoho K-SVD tsp 06; Online dictionary learning for sparse coding, ICML 09 & JMLR 10。前两种都是 batch 的方法，后一种是 online 的，据个人测试 最后一种的方法比前两者要快很多很多.下面这个是我利用ICML09的方法从1200张彩色 图像中训练出一组过完备基，具有比较好的方向特性。 最后，还记得本文开头的那些 demo 么？INRIA 做了一个 sparse representa

6、tion 的 matlab 工具包 SPAMS，虽然不开源，但其效率（大部分时候）是现有公开工具包之冠（底 层用了 intel 的 MKL），利用这个工具包，几行简单的 matlab 代码就可以几乎实现以上提 及的所有 demo 了.大家有兴趣的话，欢迎尝试_ 下期预告 ： 借着collaborative filter的东风 ， Candes在08年又挖出了matrix completion 的新坑。于是，当向量的 1 范数推广到矩阵的迹范数（trace norm）之后 开始正文之前，咱首先得说明一下，这篇东西偏向于理论，各位看官可以自行跳过某些部分。 这方面的工作奠基人同样也是 compre

7、ssive sensing 的大牛之一 E.J Candes （Donoho 的得 意门生），以及 Candes 的学生 Ben Recht，前者刚从 caltech 被挖到 stanford，后者目前 刚到 wisconsin 做 AP。Candes 大牛，stanford 统计系出生，师从 Donoho。Candes 原来 的主要工作集中在小波分析上（实际上 C 牛非常多产），比如著名的 curvelets 以及 ridgelets，04 年左右开始和 Tao 合作从事 compressive sensing 的理论工作，这里有他的 简要介绍。 继续唠叨，上回说到借着 collaborat

8、ive filtering 的东风，矩阵的稀疏表示受到了广泛的 关注。说到矩阵的稀疏性，大部分看官可能有所误解。这个矩阵稀疏表示严格而言可以分为 两种： 1. 矩阵元素的稀疏性，即矩阵非 0 元个数相对较少。参照向量的范数，同样可以定义矩阵 的 0 范数，并将其松弛到矩阵的 1 范数的优化问题。 2. 矩阵奇异值的稀疏性，即矩阵奇异值中非 0 元的个数（即矩阵的秩）相对较少。仿照向 量情况下 0 范数与 1 范数的关系，同样可以将其松弛的到迹范数 （trace norm） 的优化问题。 咱下面会分别聊聊这两个问题。首先，咱的出发点是 machine learning 中的 collaborat

9、ive filtering，这个概念并不是啥新东西了，最早大约可以追朔到 1992 的某篇同名 文章。这玩意是做啥的呢，通俗的说，每次你在淘宝上闲逛的时候，下面都会有一行推荐商 品。这些个网络服务商（淘宝，Amazon, Ebay）就在想了，如果这个推荐系统做的足够好， 那么消费者（比如你我）的购物欲望就会得到刺激，这个销量也就上去了。实际上，这和超 市里玲琅满目的货架是一个道理。 这里就得提提 Netflix Prize 这件事了，话说 netflix 是家在线 dvd 租赁公司，这公司就 抱了同样的想法。不过这家公司想了个主意：该公司提供数据，出资 100 万美刀，奖励研 发这个推荐系统算

10、法的小组，并要求这些算法发表在学术会议或期刊之上。这可以算是现实 版的百万富翁了（学术和 money 两不误），于是 collaborative filtering 着实火了一把（比 如SIGKDD上的不少文章） 。 最终历时两年 ， 由AT&T实验室成员组成的BellKors Pragmatic Chaos 赢得了这 100 万刀。顺到一提，国内也有不少家伙参与了这个 Prize，比如排名第二 的 Ensemble 组里就能看到中科院某所学生的身影。 这个推荐系统咋做呢？我们先从简单的模型开始。以 netflix 为例，netflix 有个影评系 统，在你租完 DVD 以后会让你打分（1-5

11、 分）。当然不是所有人都会认真去打，实际上只 有少数家伙会给打分（这世界上懒人何其之多）。同样，对每个用户而言，他也只可能给部 分看过的 DVD 打分。假设现在有个用户和 部电影，如果把所有评分列成一张大表，可 以得到矩阵。其中，每一行对应一个用户的评分，每一列对应一部电影的用 户评价。可以想象，这个矩阵中只有少部分元素是已知的（图 1）。 从现有的用户数据，来预测未知的用户数据，这就是 collaborative filtering 了。那么这 个东西怎么实现呢？解释起来难，做起来容易，这个模型放在在 topic model 里叫做 Probabilistic latent semantic

12、 analysis （PLSA），放在代数里叫做矩阵分解（Matrix Fatorization）或者矩阵填充（Matrix Completion），这里就只能形象的解释下。虽然用户 千奇百怪、电影成千上万，但总可以归结为若干类型：比如有腐女向、宅男向电影之分，再 比如有悲剧也有喜剧。如果把这些 latent factor 画成一个空间，那么不同的用户群体应当位 于这个 latent factor 空间的不同位置，体现了不同用户的喜好。如果可以把用户喜好连同潜 在的 latent factor 一同计算出来，预测也自然水到渠成了。从某种角度来看，奇异值分解过 程也就是上述的剥离 latent

13、factor 和用户喜好的过程 ， 这其中的 philosophy 可以参见这篇文 章。 咱首先要谈的是矩阵奇异值的稀疏性，为此先来回忆下奇异值分解。 1. 奇异值非负，即 2. 奇异值非 0 元的个数即为矩阵的秩（rank） 如果把奇异值写成对角矩阵的形式（比如 SVD 分解的标准形式），其对角元为 。进一步，矩阵的迹范数（trace norm）定义为矩阵奇异值之和， 即有 现在我们可以把 collaborative filtering 的基本问题回顾一下，给定一张推荐数据表 ，已知其下标子集中的元素 （也就是有评分的部分） ，如何恢复这个矩阵？ 这就是 matrix completion

14、的问题了 乍眼一看，这基本就是 mission impossible 了，即使只有一个元素未知，这个矩阵也 不可能唯一。但是如果我们加一些限制条件，这个问题就变得有趣起来了。Candes 考虑的 是这么一个问题： 其中表示在子集上的投影（即只取子集上的对应元素）。实际上，同样的问题可以 有不同的表达形式，如果把这个优化问题稍作调整，可以得到相对容易解释的模型： 其中 Frobenius 范数也就是矩阵的 2 范数。从这个式子来看，我们希望找到这么一个矩阵 ，使得其在已有的数据上和用户评分尽可能的一致（2 范数意义下），同时具有比较低 的秩（受到上限的约束）。这里对于秩的约束，很多时候是为了降低

15、模型自身的复杂度 （比如 collaborative filtering，multiple instance learning）。当然，这里也可以看成是一个 fidelity term + regulariztion term 的经典形式。 实际上矩阵的 rank 是一个不那么友好的函数，rank 自身是非凸、不连续的，最后的结 果就是对于 rank 的优化问题是 NP 难的。类比 0 范数与 1 范数的关系，矩阵的秩 （rank） 相当于这个对角阵的 0 范数；矩阵的迹范数（trace norm）相当于这个对角矩 阵的 1 范数。为此，如果这个对角矩阵足够稀疏，即矩阵的秩，那 么可参照向量的

16、稀疏表示，利用矩阵的迹范数(trace norm)代替矩阵的秩（rank）。 同样，由于迹范数(trace norm)是凸的，上式是一个凸优化问题，故而必有唯一的最优解。 如果这种近似是可以接受的，那么这个问题自然也就解决了。 这种近似靠谱么？这就是 Candes 和 Recht 回答的关键问题。Candes 从 random orthogonal model 出发，证明了在此假设下从某个秩为 的真实矩阵中均匀 抽取 个元素，且满足(这里不妨设，反之只需要转置即可) 则凸优化问题的唯一最优解至少以概率逼近原始矩阵，即有 其中均为某常数。更进一步，如果矩阵的秩 足够小，对于元素数量 的要求会进一步 降低。 咱来聊聊这个结果，这说明在 random orthogonal model 假设成立的条件下，如果 相 对于比较小，那么只需要知道这个矩阵中约个元素，就可以很高的概 率恢复出这个矩阵。举例而言，如果我们有一个秩为 10 的矩阵，那我们大 致只需要从中随机抽取约 270 万个元素就可以（以很高概率）恢复出原始矩阵了(当然 270 万貌似也是一个很大的数，但原始