中国工程论文网
代写工程论文
当前位置:工程论文网 > 系统工程论文 > 稀疏恢复问题的非凸松弛方法

稀疏恢复问题的非凸松弛方法

时间:2016-08-26 15:18来源:www.e-lunwen.com 作者:lgg 点击:
本文是系统工程论文,论文针对低 Tucker 秩张量恢复问题, 建立了一个非凸的 Lp松弛模型, 通过引入一系列辅助变量, 将其等价转化为一个具有可分结构的非凸极小化问题。
第一章 绪论
 
1.1 稀疏优化简介
稀疏优化问题是从众多实际问题中提炼出来的一类科学问题, 它在单像素相机、核磁共振成像、信号处理、图像处理、多元统计分析、机器学习、无线传感、计算机视觉、模式识别、传感器定位、系统辨识等很多领域中有重要的应用[1]. 在很多实际应用问题中, 比如在信号及图像处理中, 需要由得到的线性观测数据来恢复原信号, 在如今的大数据时代, 人们面临的问题越来越复杂、问题的规模越来越大. 在大规模的复杂问题中, 人们需要有效地处理高维数据.高阶张量1可以很好的刻画高维数据, 因而, 高阶张量的相关方法在实际中得到了越来越多的应用. 作为低秩矩阵恢复研究的一个推广, 如何从得到的观测数据中恢复一个低秩张量在近几年来引起了大量学者的关注和研究. 
......
 
1.2 稀稀疏优化研究现状
目前, 求解 l0极小化问题 (1-2) 的方法主要可以分为三大类, 包括优化类算法 (或松弛方法), 贪婪算法和阈值类算法.近几年, 通过 l1范数极小化及其相关问题来研究稀疏信号恢复问题成为一个研究热点, 已经得到了很多的研究成果.研究内容之一是考察 l1范数极小化问题的最优解 (1-9) 在什么条件下是原 l0范数极小化问题 (1-2) 的最优解, 即精确恢复理论. 目前已建立的条件主要包括互相干性 (Mutual Coherence, 简记为 MC)[7], 限制等距性质 (RestrictedIsometry Property, 简记为 RIP) 条件 [8–11], 零空间性质 (Null Space Property, 简记为NSP)[12,13], 域空间性质 (Range Space Property, 简记为 RSP) [14], s-good性质 [15]等.另一个研究内容主要是如何快速求解 l1范数极小化问题 (1-9), 即算法设计. 目前有效的算法主要包括内点法 (Interior-point methods), 同伦法 (Homo-topy methods)[16,17], 梯度投影 (Gradient Projection, 简记为 GP) 法 [18,19], 软阈迭代(Iterative Soft Thresholding, 简记为 IST) 算法 [20–22], 最近, Chen 等人证明了非凸非光滑约束 lp极小化问题 (1-13) 及无约束 l2-lp极小化问题 (1-15) 是 NP-难的[35,36]. 目前针对这类问题的求解主要包括光滑逼近算法和阈值迭代算法. 迭代重新加权类算法是光滑逼近算法中最重要的一类算法, 主要包括迭代重新加权 l1极小化 (Iteratively Reweighted L1minimization,简记为 IRL1) 算法[37–41]和迭代重新加权极小二乘 (Iteratively Reweighted LeastSquare, 简记为 IRLS) 算法 [42–44], 因为它的本质为求解 lp相关极小化问题的光滑化模型, 故可以看做求解 lp相关极小化问题的光滑逼近算法. 这类算法对于约束极小化问题 (1-13) 和无约束正则化问题 (1-15) 的求解都有对应的研究. 这两个问题的求解难度主要体现在对非光滑函数项  x pp的处理上. 特别地, 求解lp极小化问题已有算法的比较也被研究[45].
...........
 
第二章 预备知识
 
2.1两类方法
MM 算法可以看做是著名 EM 算法 [137]的一个推广. 它的一般原理由学者 Ortega 和 Rheinboldt 在 1970 年研究线性搜索方法时首次阐明[138]. Leeuw 和Heiser 在 1977 年提出了一个求解多维标度问题的 MM 算法 [139], 但它并未像EM 算法一样在统计领域中引起特别大的关注. 虽然到二十世纪末期针对 MM算法一般原理研究已有一些工作[140–143], 但直到 2000 年缩写的 MM 算法才被Hunter 和 Lange 第一次提出 [144]. 统计中很多问题的研究都说明了 MM 算法的实用性, 比如用于分位数回归 (quantile regression), 存活率分析 (survival analysis),变量选择 (variable selection) 及 DNA 序列分析 (DNA sequence analysis) 等[145–149].MM 算法不是指某个单独的算法, 而是指一类算法. 当它被用于求解极小化问题时, MM 中的两个 M 分别表示“majorize”和“minimize”, 即为通常所说的Majorization 极小化方法. 对应地, 当 MM 算法用于求解极大化问题时, 它指的是 Minorization 极大化方法. 下面给出 Majorizing 与 Minorizing 函数的定义.定义 2.3 ( Majorizing 与 Minorizing 函数)[150] 令 x, y 分别为任意赋范空间中的点, f 为一个实值函数, Q(x, y) 表示与固定值 y 相关的关于 x 的实值函数. 称函数 Q(x, y) 是 f(x) 在点 y 处的一个 Majorizing 函数, 或者 Q(x, y) 在点 y 处 Majorizes函数 f(x).
..........
 
2.2 交替方向法
近年来, 很多领域中涌现出了大量的大规模问题亟待求解, 包括机器学习, 相比具有更快的收敛性, ADMM 的研究又引起了大量的关注. 早在1989 年, Bertsekas 等人已经证明了 ADMM 在适当的条件下收敛 [157], 最近 He 等人在相同的条件下证明 ADMM 具有 O(1t) 次线性收敛率 [158,159], Goldfarb 等人在更严格的条件下证明了加速的 ADMM 具有 O(1t2) 次线性收敛率 [160,161]最近, 关于具有多个变量及多块可分结构问题的 ADMM 研究主要包括下面两个方向: 考虑 ADMM 的其它变形形式, 或者在增加条件的前提下考虑ADMM 的收敛性 [163–169]. 另外, 针对 N = 2 但目标函数关于变量不可分的情形,Hong 等人说明在某些误差界条件满足的前提下, ADMM 可以收敛到原对偶最优解集[170,171].最近, 在实际应用中, ADMM 还被用于目标函数非凸情形的问题中, 并得到了很好的效果, 比如非负矩阵分解, 相位检索等[172–174]. 最近, Hong 等人针对某类非凸问题, 包括非凸的一致性 (consensus) 问题和分享 (sharing) 问题, 讨论了非凸 ADMM 的收敛性, 证明当非凸的目标函数 fi满足某些正则性条件, 并且在 β 充分大时, 由 ADMM 所产生的序列收敛到原问题的稳定点[175].
........
 
第三章 求解 lp极小化问题的熵型光滑化算法 ........27
3.1 引言 ........27
3.2 光滑逼近及光滑化模型 ........27
3.3 光滑化算法 ....30
3.4 数值实验 ....34
3.4.1 不同 p 值的数值表现 ........36
3.4.2 下界的应用 ....36
3.4.3 与其他算法比较 ........38
3.5 本章小结 ....39
第四章 求解 l2-Mp 极小化问题的重新加权核范数极小化算法 ....41
4.1 引言 ........41
4.2 算法设计 ....42
4.2.1 非凸逼近函数的次微分 ........42
4.2.2 算法设计 ........43
4.3 收敛性分析 ....45
4.4 数值实验 ....48
4.5 本章小结 ....55
第五章 求解低 Tucker 秩张量恢复问题的非凸交替方向法 ........57
5.1 引言 ........57
5.2 算法设计 ....58
5.2.1 传统的交替方向法求解 ........58
5.2.2 非精确的交替方向法求解 ....61
5.3 数值实验 ....63
5.3.1 参数选取 ........64
5.3.2 与其他算法的比较 ....66
5.3.3 图像恢复 ........69
5.4 本章小结 ....70
 
第五章 求解低 Tucker 秩秩张量恢复问题的非凸交替方向法
 
5.1 引言
在数值实验中, 置最大迭代数目 maxit = 500, 如果终止准则 (5-16) 在 500 步之后仍不满足, 算法自动终止迭代. 对任意的 i ∈ [N], 为了在第 k 步迭代中降低张量 Xk模式-i展开矩阵 Xk(i)奇异值分解的花费, 在数值实验中只考虑求解 Xk(i)的秩 Ri截断奇异值分解, 这里 Ri为预先给定的预估计秩, 其选取的方式与第四章中相同[93].另外, 由于本章中建立的非凸松弛模型与 p 值的选取有关, p 的不同取值将会对数值实验结果产生不同的影响. 在这一小节中, 将算法 5.3 与其他用于求解张量填充问题的算法进行比较, 分别 为: 用 于 求 解 低 多 重 线 性 秩1张 量 填 充 的 分 裂 增 广 Lagrange 方 法 (SALM for LowMultilinear-Rank Tensor Completion, 简 记 为 SALM-LRTC) [113], 硬 填 充 (TENSOR-HC) 方法[109], 用于“约束”型研究的交替方向法 (ADMM for the “Constraint” Approach, 简记为TENSOR-CON)[115], 用于低 n-秩张量恢复的交替方向法 (ADMM for Low-n-Rank TensorRecovery, 简记为 TENSOR-TR(E) [108]. 这里, 为了方便起见, 简记本章中给出的算法 5.3为 NC-ADMM.下面, 对随机生成的张量填充问题, 给出算法 NC-ADMM, SALM-LRTC, TENSOR-HC, TENSOR-CON 与 TENSOR-TR(E) 分别在有无噪音情形下的数值实验结果. 在实验中, 对所有的算法取初始点. 对于不同算法的具体参数选取, 参考文献[108,109,113,115].
...........
 
总结
 
本论文主要针对稀疏信号恢复、低秩矩阵恢复和低 Tucker 秩张量恢复问题, 对其非凸松弛进行光滑化逼近, 进而设计求解算法, 并证明算法的收敛性质, 研究成果如下:1. 文中讨论了熵函数的性质, 建立了非凸 lp拟范数极小化问题的一个光滑逼近模型, 并对所提光滑模型给出了一般的光滑化算法框架, 证明了所提算法的收敛性.此外, 文中给出了光滑化问题稳定点中非零元素的下界估计, 从而降低了计算中的误差影响, 进一步保证了所求得解的稀疏性.2. 文中针对无约束 L2-Mp 极小化问题, 设计了一个基于加权不动点迭代的重新加权核范数极小化算法. 具体地, 文中首先给出了问题中非凸正则项  X pp,ε的次微分公式, 以及加权核范数的邻近算子, 将其定义为加权的阈值压缩算子. 然后基于求解加权核范数极小化问题的加权不动点迭代设计了重新加权核范数极小化算法, 通过引入一个泛函, 证明了所提算法的收敛性.3. 文中建立了低 Tucker 秩张量恢复问题的一个非凸松弛模型, 通过引入一系列辅助变量, 将其等价转化为一个具有可分结构的非凸极小化问题. 针对所得的非凸极小化问题, 设计精确和非精确的非凸交替方向法进行求解, 并给出收敛性结果.4. 基于仿真数据和真实数据的数值实验, 均说明了本论文所提出的非凸松弛方法在求解稀疏信号恢复、低秩矩阵恢复和低 Tucker 秩张量恢复问题时相比已有算法的有效性.
.........
参考文献(略)
(责任编辑:gufeng)
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
栏目列表
点击提交代写需求
点击提交代写需求
点击提交代写需求
推荐内容