稀疏数据恢复的结构优化模型及其算法研究

摘要

稀疏数据可以被充分压缩，从而节约储存空间、减少传输量.数据恢复是指将遭到干扰或者破坏的数据还原成真实数据.稀疏数据恢复问题广泛存在，例如，稀疏信号压缩传感问题、低秩矩阵完整化问题、基于全变差正则化的图像恢复问题等.根据稀疏数据恢复问题模型的特殊结构（如目标函数的可分性、向量的稀疏性、矩阵的低秩性等），如何高效地从病态的线性反问题中唯一且稳健地恢复出特定的信息是许多研究者共同关注的重要课题.根据实际需要与问题特征构造的结构优化模型，以及与其相适应的算法被证实对求解稀疏数据恢复问题有较好的效果.
　　本论文以稀疏数据恢复问题的结构优化模型为研究对象,分别针对带有两个、三个与四个可分离块变量的结构凸优化问题提出了相对应的快速算法，并证明了所提出算法的全局收敛性，数值实验验证了所提出算法在稀疏信号压缩传感、低秩矩阵完整化、图像恢复等方面的有效性和实用性.本论文的主要工作如下:
　　首先，针对一类带有两个块变量的结构优化问题，提出了一种基于线搜索的部分邻近型交替方向法(LSPPAD).该算法充分利用了所研究问题的特殊结构，在每一轮迭代中交替地求解两个子问题:其中一个子问题采用邻近点方法求解，而另一个子问题的求解无须添加邻近点项.两个子问题均采用线搜索技术进行非精确求解.在适当条件下，证明了LSPPAD算法的全局收敛性.压缩传感和矩阵完整化问题的数值实验结果表明，该算法具有较好的实现性能.
　　其次，针对一类带有三个块变量的光滑Tikhonov正则化问题，提出了一种平行交替混合分裂方法(HSM）.该算法在每一轮迭代中，需要求解三个子问题并更新两个乘子.前两个子问题由平行分裂迭代格式求解.并立即更新与前两个块变量相关的Lagrange乘子;第三个子问题利用前两个子问题的最新结果，采用交替方向法的迭代格式来求解;最后更新与第二、第三个块变量相关的Lagrange乘子.该算法巧妙揉合了平行分裂方法和交替方向法.在适当条件下，证明了该算法的全局收敛性.离散不适定问题的数值实验表明所提出算法的有效性.该算法进一步被推广应用到TVIR图像恢复模型中，数值实验结果表明该方法具有可应用性.
　　最后，针对一类带有四个块变量的结构优化问题，提出了一种非精确分组交替方向法.该算法在每一轮迭代中，根据子问题计算工作量的大小，将四个子问题分为两组，每组包含工作量相当的两个子问题.算法在组内执行平行分裂方法，两组间执行交替方向法，并允许迭代子问题的非精确求解.在适当条件下，证明了所提出算法的全局收敛性.与已有的分组分裂方法相比较，由于所提出算法允许非精确求解子问题，从而更具有实用性.该算法可以直接推广到带N个块变量的分组交替方向算法.
　　全文结构如下:第一章对以压缩传感问题为基础、矩阵完整化问题为拓展、基于全变差的图像恢复问题为应用的三种典型稀疏数据恢复问题及其研究现状进行了简要的综述;第二章对本论文所需要的基本知识进行了简单概括;从第三章到第五章是本文的核心，分别就带有两个、三个和四个可分离块变量的结构凸优化问题，提出了与之相适应的算子分裂算法，包括基于线搜索的部分邻近型交替方向法、平行一交替混合分裂算法和非精确分组交替方向算法，并证明了所提出算法的全局收敛性，部分数值实验说明了算法的有效可行性.最后，结论部分对全文进行了总结，并对未来的研究进行了展望.

目录

声明

摘要

第1章 绪论

1．1 稀疏数据恢复问题及其应用

1．2 相关问题的研究现状及其进展

1．2．1 压缩传感

1．2．2 矩阵完整化

1．2．3 图像恢复

1．3 本论文的主要研究内容、研究意义及其创新点

1．4 本论文的章节安排

第2章 预备知识

2．1 约束凸优化问题的最优性条件

2．1．1 一般约束凸优化问题

2．1．2 线性约束凸优化问题

2．1．3 可分离结构凸优化问题

2．1．4 带有多个块变量的可分离结构凸优化问题

2．2 增广Lagrange方法

2．3 算子分裂算法

2．3．1 交替方向法

2．3．2 平行分裂算法

2．4 收缩算法的基本框架

2．5 几种常用算子及其基本性质

第3章 带两个块变量结构优化问题的邻近型部分交替方向法

3．1 引言

3．2 算法描述

3．3 收敛性分析

3．4 数值实验

3．5 本章小节

第4章 带三个块变量结构优化问题的混合分裂算法

4．1 引言

4．2 算法描述

4．3 收敛性分析

4．4 数值实验

4．5 算法推广应用到图像恢复问题

4．6 本章小结

第5章 带四个块变量结构优化问题的分组交替方向法

5．1 引言

5．2 若干记号

5．3 算法描述

5．4 收敛性分析

5．5 本章小结

结论

参考文献

致谢

附录A 攻读学位期间所发表的学术论文目录