logo资料库

稀疏表示方法综述.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.58M 资料格式：docx 举报 版权申诉
第1页 / 共28页
第2页 / 共28页
第3页 / 共28页
第4页 / 共28页
第5页 / 共28页
第6页 / 共28页
第7页 / 共28页
第8页 / 共28页
资料共28页，剩余部分请下载后查看
    一，引言
    1.1稀疏表示方法的分类
    二，具有不同范数约束的稀疏表示问题
    2.1具有范数最小化稀疏表示
    2.2具有范数最小化稀疏表示
    2.3具有范数的最小化稀疏表示
    2.4具有和
    三,贪婪策略逼近算法(the greedy strategy approximation）
    3.1匹配追踪算法
    3.2正交匹配追踪算法
    3.3匹配追踪算法的流程
    四,约束最优化策略(constrained optimization strategy)
    4.1梯度投影稀疏重建(gradient projection sparse reconstruct
    4.2 基于内点法的稀疏表示策略(interior-point based sparse repre
    4.3基于交替方向法（ADM）的稀疏表示策略(alternating direction meth
    五,基于逼近算法的最优化策略(proximity algorithm based optimizat
    5.1软阈值算子(soft thresholding or shrinkage operator)
    5.2迭代收缩阈值算法（ISTA）
    5.3快速迭代收缩阈值算法（FISTA）
    5.4基于可分表示的稀疏重建（SpaRSA）
    5.5基于范数约束的稀疏表示(
    总结
    六,参考文献
    摘要 稀疏表示已经引起了很多来自信号处理，图像处理，计算机视觉和模式识别 领域专家的注意。稀疏表示同时在理论研究和实际运用中表现出优秀的特性，许 多不同算法被提出用于解决稀疏表示。本文旨在提供一个对稀疏表示综合性和前 瞻性的综述，向研究者提供有用的借鉴。我们可以从不同的角度将稀疏表示方法 分类。例如，从稀疏约束中最小化范数的方法出发，我们粗略地将它们分为五组： 1）具有 0l 范数最小化稀疏表示；2）具有 pl 范数的最小化稀疏表示；3）具有 1l 范 数最小化稀疏表示；4）具有 2,1l 范数最小化稀疏表示；5）具有 2l 范数最小化稀疏 表示。本文提供了系数表述综合性的全局概览。稀疏表示算法同时也可以经验性 地分为四组：1）贪婪算法趋近；2）约束最优化；3）基于逼近算法的最优化。 其中每一类的不同的算法的基本原理，文中都做了分析说明。 关键字：稀疏表示，压缩感知，贪婪算法，约束最优化
    目录 一，引言....................................................................................................................... 1 1.1 稀疏表示方法的分类............................................................................. 2 二，具有不同范数约束的稀疏表示问题................................................................... 3 2.1 具有 0l 范数最小化稀疏表示..................................................................3 2.2 具有 1l 范数最小化稀疏表示.................................................................. 4 2.3 具有 pl 范数的最小化稀疏表示..............................................................5 2.4 具有 2,1l 和 2l 范数最小化稀疏表示.........................................................5 三,贪婪策略逼近算法(the greedy strategy approximation）..................................... 6 3.1 匹配追踪算法......................................................................................... 6 3.2 正交匹配追踪算法................................................................................. 7 3.3 匹配追踪算法的流程............................................................................. 8 四,约束最优化策略(constrained optimization strategy)............................................. 8 4.1 梯度投影稀疏重建(gradient projection sparse reconstruction)............9 4.2 基于内点法的稀疏表示策略(interior-point based sparse representation strategy)......................................................................................10 4.3 基于交替方向法（ADM）的稀疏表示策略(alternating direction method based sparse representation strategy).................................................. 12 五,基于逼近算法的最优化策略(proximity algorithm based optimization strategy) 14 5.1 软阈值算子(soft thresholding or shrinkage operator)......................... 14 5.2 迭代收缩阈值算法（ISTA）................................................................ 15 5.3 快速迭代收缩阈值算法（FISTA）.......................................................16 5.4 基于可分表示的稀疏重建（SpaRSA）............................................... 17 5.5 基于 1/2l 范数约束的稀疏表示( 1/2l -norm regularization based sparse representation)....................................................................................................19 总结............................................................................................................................. 21 六,参考文献................................................................................................................ 22
    一，引言 随着数学的发展，线性表示方法（LRBM）已经得到充分的研究，同时也得 到了足够多的关注[1] [2]。作为线性表示方法中最具代表性的一种，稀疏表示方 法已经被证明是一种解决大范围应用领域问题非常强有力的工具，尤其在信号处 理，图像处理，机器学习和机器视觉领域，比如图像去噪，去模糊，图像修复， 超分辨率重构，视觉跟踪，图像分类和图像分割[3]。稀疏表示在解决此类问题 方面展现了巨大的潜力。 从其根源来看，稀疏表示和压缩感知（CS）是直接联系着的，其中压缩感知 是近年来最为流行的热点之一。Donoho[11]首先提出来压缩感知的原始概念，压 缩感知理论认为，如果一个信号是稀疏的或者是可压缩的，那么原始信号可以仅 根据一部分观测到的数据重建，这些观测数据远小于香农采样定理所需的数据。 Candes[13]，从数学的观点解释了压缩感知原理的工作原理，例如 运用傅里叶变 换中一部分参数，原始的信号就能被精确重建。Baraniuk[12]对压缩感知做了一 个详实的分析，同时提出了一个对不同信号重建算法解决方案的特殊解释。所有 这些工作[11]-[17]奠定了压缩感知理论的基础，并且为将来的研究提供了理论基 础。因此，很多基于压缩感知理论的算法被提出，用于解决不同领域中的各种问 题。压缩感知理论通常包含三个基本成分：稀疏表示，编码度量，和和重建算法。 作为压缩感知理论不可或缺的先决条件，稀疏表示理论[4][7][10][17]是用于克服 许多领域出现的问题的作为显著的技术。例如，稀疏表示方法是一种新颖的采样 稀疏可压缩信号的方法，并且已经被成功的运用于信号处理之中[4]-[6] 近年来，稀疏表示吸引了众多人的关注，而且许多实例显示它在不同领域具 有绝对好处。其中一个例子就是图像分类，图像分类的基本目标就是将测试图像 正确地放在预先定义的类别中。事实证明，从人类视神经的特性角度来看，自然 图像能够被稀疏表示。基于稀疏表示的分类方法（SRC）首先假定测试样本能够 充分的被来自同一物体的训练样本完全表示。SRC 利用训练样本的线性组合去表 示测试样本，并且计算线性表示系统的系数，然后利用稀疏表示系数和训练样本 计算重建残差。测试样本会被分成一系列不同的类，使得重建残差最小。文献[20] 证明，当待分类的图像存在毁坏或者伪装时，基于稀疏表示的图像分类方法表现 出很大的优越性。在这种情况下每一张自然图像能够被稀疏表示，同时稀疏表示 理论能够被用于完成挺像分类任务 1
    1.1 稀疏表示方法的分类 我们可以从不同的角度出发，将稀疏表示理论分为不同的种类。由于不同的 方法都有自己动机，想法，顾虑，因此从分类学的观点出发，存在很多种策略将 现存的稀疏表示方法分为不同的类。例如，从原子的观点出发，我们可以将现有 的稀疏表示方法分为两类：基于朴素采样的稀疏表示方法和基于字典学习的稀疏 表示方法。然而，根据原子标签是否给定，稀疏表示和学习方法可以粗略地分为 三组：监督学习，半监督学习和无监督学习。根据稀疏约束，稀疏表示方法可以 分为两类，基于结构约束的稀疏表示方法和基于稀疏约束的稀疏表示方法。此外， 在图像分类领域，就使用原子的方式，基于表示的分类方法包含两个主要类别： 基于全局表示的方法，和基于局部表示的方法[21]，其中基于全局的表示方法使 用所有类别的训练样本来表示测试样本，而基于局部的表示方法使用每一类或几 个类的训练样本来表示测试样本。大部分稀疏表示方法是基于全局的方法。一个 典型的具有代表性的局部稀疏表示方法是两象限测试样本稀疏表示方法（TPTSR） [9]。从使用的方法来看，稀疏表示方法可以被分为两类：纯粹稀疏表示和混合 稀疏表示。文献[23]表明，稀疏表示算法可粗略地分为三类：凸松弛，贪心法和 组合方法。文献[24][25]从稀疏问题建模和问题求解出发，将稀疏分解分为两部 分：贪心算法和凸松弛算法。如果从做优化的角度出发，稀疏表示问题可以被分 为四个最优化问题：光滑凸问题，非光滑非凸问题，光滑非凸问题，非光滑凸问 题。Schmidt et al.[26]综述了一些解决 1l 范数约束问题的最优化方法，并且粗略第 将这些方法分为三分最优化策略：子梯度方法，非约束逼近方法，约束最优化方 法。 在本文中，现有的稀疏表示方法被分为四类：贪婪策略逼近（the greedy strategy approximation），约束最优化策略(constrained optimization strategy)，基于 逼近的最优化策略(proximity algorithm based optimization strategy)和基于同论算 法的稀疏表示(homotopy algorithm based sparse representation)。 （1）在贪婪策略逼近算法中，目标主要是解决具有 0l 范数最小化稀疏表达 方法。由于该问题是 N-P 难问题[27]，贪婪算法为解决该困难提供了近似的解决 方法。贪婪算法在每次迭代中寻找局部最优解，最终趋近全局最优解。 （2）在约束最优化策略中，其核心的思想是寻找一种方式，通过将非光滑 凸的 1l 范数最小问题替换成光滑而凸的可微最优化问题，将不可微最优化问题 转换为可微最优化问题。也就是说，约束最优化策略将 1l 范数最小问题，替换 成了具有相同约束条件的原始非约束问题。如果原始非约束问题通过形式变换， 能够转换为具有约束条件的可微问题，那么考虑到 1l 范数最小是全不可微的这 2
    一事实，问题就变得简单了。 （3）逼近算法可以看作是解决具有非光滑，约束，大尺度或分散特性的最 优化问题的强大工具。在基于近邻算法的最优化稀疏表示策略中，其主要任务将 原始问题形式变换为对应近邻算子的特定模板，例如软阈值算子，硬阈值算子等， 然后利用近邻算法求解原始最优化问题。 （4）同论算法的基本框架是，通过连续调整同论参数[30]，迭代寻找最终 期望解。在基于同论算法稀疏表示中，同论算法用 K 稀疏特性求解 1l 范数最小 化问题。 二，具有不同范数约束的稀疏表示问题 该部分对稀疏表示做了概括，并按照采用范数约束的不同，将其分成不同的 类。稀疏表示的基本框架是，利用一些样本或原子的线性组合来表示一个新的样 本，计算表示的解，例如这些样本或原子的系数，然后根据表示解重构期望的结 果。表示能够形成稀疏表示，然而这一过程是受加在表示解上优化器中不同范数 主宰的[33]-[36]。因此就优化器中所使用的范数类型，可以将稀疏表示方法粗略 地分为五类：1）具有 0l 范数最小化稀疏表示[37][38]；2）具有 pl 范数的最小化稀 疏表示[39]-[41]；3）具有 1l 范数最小化稀疏表示[42]-[45]；4）具有 2,1l 范数最小化 稀疏表示[46]-[50]；5）具有 2l 范数最小化稀疏表示。本文提供了系数表述综合性 的全局概览[9],[22],[51]。 2.1 具有 0l 范数最小化稀疏表示 令 1 , x x 2 , R x n d 为 n 个已知的样本， 矩阵 X R d n   d  为基础字典或 n  测量矩阵，并且是过完备字典。矩阵 X 中每一列都是一个样本，而且测试样本 y R ，也是一个列向量。因此，如果用已知的样本去线性表示这个测试样本， d 结果如下 其中  ia i y  x   1 1 2 x 2    x  n n （2.1） 1,2,   是 ix 的系数， 公式（2.1）可以写成如下方便的形式 n ,  y X （2.2） 方程（2.2）是欠定线性方程。根据线性代数知识，如果没有任何先验的知 识或者任何对表示系数施加的约束，方程（2.2）就是一个病态的方程，并且 3
    永远没有唯一解存在。也就是说不可能利用方程（2.2）用测量矩阵 X 唯一的表 示测量样本 y 。 为了解决这个难题，可以对表示系数施加一个适当的约束条件 或约束方程。稀疏表示方法要求获得的表示系数应该是稀疏的。今后稀疏被定义 为：当用测量矩阵的线性组合去表示测量样本时，许多表示系数应当是零或者非 常接近于零，而只有全体中少数的稀疏非常的大。 最为稀疏的表示系数可以通过求解带有 0l 范数最小约束的线性系统（2.2）得 到，因此问题（2.2）转换为以下最优化问题：    arg min  0 . .s t y X   （2.3） 其中 0 指的是向量中非零元素的个数，同时也被看作稀疏的度量。如果测 量矩阵 X 中仅有 k 个原子被用于表示测量样本，问题（2.3）就等价于下面的最 优化问题： y X   . . s t  0  （2.4） k 问题（2.4）叫做 k －稀疏近似问题。由于实数据经常包含噪声，在大多说 情况下表示系数噪声是不可避免的，因此原始模型（2.2）通过修改能够包含噪 声的影响 y X s  （2.5） 其中 s R 代表表示噪声，并且被约束在 d 2s  之中。随着噪声的出现， 问题（2.3）和问题（2.4）能够近似表示为下面的最优化问题    arg min  0 . .s t y X  或者    （2.6） 2 2    arg min y X   2 2 . . s t    （2.7） 0 根据拉格朗日乘数定理，存在一个合适的实数 将（2.6）或（2.7）等价的 表示为下面一个不带约束条件的问题：     L   ,  arg min y X     2 2 （2.8） 0 2.2 具有 1l 范数最小化稀疏表示 1l 范数起源于套锁问题［42］［43］，并被广泛运用于解决机器学习，模式识 别和统计学方面的问题。尽管基于 0l 范数最小化的稀疏表示方法，能够获得基本 的稀疏解，但问题的求解仍然是 NP 难问题，而且很难得到近似解。最近的几篇 文献[20][56]－[58]证明，基于 1l 范数最小化约束的表示解也满足稀疏的条件，并 4
    且具有充分稀疏性的基于 1l 范数最小化约束的表示解，有十足的概率等同于基于 0l 范数最小化约束的表示解。基于 1l 范数的最优化问题有解析解，而且能够在多 项式时间内得到解，因此另一个基于 1l 范数最小化约束的稀疏表示方法已经被提 出，丰富了稀疏表示理论。和基于 0l 范数的稀疏表示方法相似，基于 1l 范数最小 化约束的稀疏表示方法主要用于解决一下问题       arg min  1 . .s t y X   （2.9） arg min  1 . .s t y X     （2.10） 2 2 或者    arg min y X   2 2 . . s t    （2.11） 1     L   ,  arg min y X     2 2 （2.12） 1 2.3 具有 pl 范数的最小化稀疏表示 通常稀疏表示方法为了解决一个具有 pl 范数最小化问题的线性表示系统。除 了 0l 范数最小化和 1l 范数最小化，有些研究人员尝试用  pl 0 p  范数解决稀疏  1 表示问题。也就是说，用 pl 范数最小化的稀疏表达是为了解决一下问题：    arg min  p p  或者 . . s t y X     （2.13） 2 2     L   ,  arg min  y X     2 2 p p （2.14） 尽管基于 pl 范数最小化稀疏表达方法不是获得稀疏解的主流方法，但他它极 大的促进了稀疏表达理论的发展。 2.4 具有 2,1l 和 2l 范数最小化稀疏表示 基于 2l 范数最小化方法获得稀疏表示，并不是严格稀疏的，他只能获得有限 稀疏的表示解，例如有该方法获得表示解具有以下特性：解是可区别，可分辨的， 5
    但就是不够稀疏［31］。基于 2l 范数最小化方法的稀疏表示的目标函数，是为了 求解以下问题 或者    arg min  2 2     L   ,  arg min  . .s t y X     （2.15） 2 2 y X     2 2 2 2 （2.16） 另一方面， 2,1l 范数也被叫做旋转不变 1l 范数，该范数对于异化值具有鲁棒性 [62]。基于 2,1l 范数最小化方法的稀疏表示的目标函数，是为了求解以下问题： arg min A Y XA   A 2,1 2,1 （2.17） 其中   Y y y 1 2 , ,  指的是有样本组成的矩阵，   A y  N , a a 1 2  , N a  是矩阵 X 的 对应稀疏矩阵， 是小的正常数。 三,贪婪策略逼近算法(the greedy strategy approximation） 贪婪算法可以追溯到 1950s。贪婪策略[7][24]的核心思想是，根据原子和测 试样本之间的关系，决定对应的位置，然后利用最小平方评估幅值。在求解问题 中，贪婪算法每一次迭代都能获得局部最优解，并且最终总是能够获得全局最优 解或近似解[7][24]。具有 1l 范数约束的稀疏表示问题是 NP 难问题，贪婪策略能 够通过一种特殊的方式获得近视的稀疏解。事实上，贪婪算法不能直接求解最优 化问题，它只能寻找出具有 1l 范数约束的稀疏表示问题的近似解。 3.1 匹配追踪算法 匹配追踪（MP）算法是基于贪婪策略解决 1l 范数约束稀疏表示问题中，最早 和最具有代表性的一种算法。匹配追踪算法主要思想是，根据某种相似性测度， 从字典中迭代选择最优原子，来获得系数解的近似解。 假设初始表示残差为 0R y ，   , D d d 1 , 2   d N d N R  ，其中字典 D 中每一 个样本都是 2l 范数归一化向量，例如 id  。为了逼近 y ，匹配追踪算法首先从 1 字典中选择一个匹配度最好的原子，而且这个原子应该满足下面的条件： , R d 0 l 0  sup （3.1） i , R d 0 6
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料