非凸惩罚的稀疏建模理论与算法研究

摘要

稀疏学习是一个横跨机器学习、统计估计、信号处理等多个领域的关键技术，其在模型选择、稀疏编码、压缩感知等重要问题中发挥着关键的作用。目前，稀疏学习以基于凸优化模型的方法为主且已建立完备的体系，但是具有更好理论性质和实践效果的非凸稀疏学习方法仍然存在诸多问题有待研究。本文为非凸MCP(Minimax Concave Penalty)惩罚线性回归模型设计了一种凹共轭算法。在所有非凸稀疏诱导函数中，MCP函数因具有较好的理论性质和实践效果而被常用于稀疏学习问题。如何高效地求解基于MCP的非凸优化问题对于实际效果是至关重要的。本文利用凹共轭这一概念，将非凸MCP函数写成凹共轭最小化问题的形式，从而设计了一种交替迭代算法。该算法可以求解每个变量都有独立惩罚参数的MCP惩罚回归模型，且能在算法运行过程中自动调整惩罚参数。这种机制能提升变量选择和预测精度。另外，本文还设计了一种DC规划算法。特别地，当所有变量具有相同的惩罚参数时，交替迭代算法蜕化为DC规划算法。
　　本文研究了一种恢复协稀疏信号的非凸优化方法。经典的压缩感知信号恢复方法通常基于稀疏合成模型，其假设信号在某个基或字典上具有稀疏表达。本文则考虑一种新兴的信号模型—协稀疏分析模型，其假设信号在某个线性变换下是稀疏的。鉴于当前的协稀疏信号恢复方法以凸优化方法为主，本文研究了一种非凸协稀疏信号恢复方法—(l)p(0＜p＜1)分析最小化。本文提出了一种新的分析工具-Ap-RIP，并用其分析了(l)p分析最小化模型的恢复误差。另外，本文首次证明了非凸(l)p分析最小化方法相对于凸l1分析最小化方法的优势:(1)非凸方法具有更低的样本复杂度;(2)非凸方法能在更宽的协稀疏度变化范围里进行信号恢复。本文还设计了求解(l)p分析最小化方法的迭代重加权算法，且该算法产生的序列收敛到一个局部临界点。本文为一种通用非凸结构稀疏学习模型设计了快速算法。标准的稀疏认为模型变量之间是相互独立的，而结构稀疏考虑变量之间的潜在结构。结构稀疏学习方法利用变量的结构信息可进一步提高学习性能。当前的结构稀疏学习方法以贪婪算法和凸优化方法为主。本文则考虑一类通用非凸结构稀疏学习模型，并为其设计快速求解算法。具体地，本文设计了一种交替邻域分裂算法，其每次迭代由一个梯度下降步骤和一个邻域映射步骤构成。相比之前的非凸结构稀疏优化算法，本文提出的算法具有较低的迭代计算复杂度，这使得其对于大规模问题具有更好的扩展性。另外，本文还设计了交替邻域分裂算法的加速算法，该加速算法极大地提高了运行时间效率。理论上，本文证明了交替邻域分裂算法产生的序列以至少次线性的速度收敛到一个局部临界点。

目录

声明

摘要

第1章 绪论

§1．1 选题背景和意义

§1．1．1 模型选择

§1．1．2 稀疏编码

§1．1．3 压缩感知

§1．2 稀疏学习研究回顾和现状分析

§1．2．1 贪婪算法

§1．2．2 凸优化方法

§1．2．3 非凸优化方法

§1．2．4 结构稀疏学习

§1．3 本文研究思路

§1．4 本文组织结构

第2章 非凸MCP惩罚回归的凹共轭算法

§2．1 非凸MCP惩罚回归

§2．1．1 相关工作

§2．2 基于凹共轭的交替迭代算法

§2．2．1 收敛性分析

§2．2．2 讨论

§2．3 DC规划算法

§2．4 实验分析

§2．5 本章小结

§2．6 引理证明

第3章 非凸协稀疏信号恢复方法—(e)p分析最小化

§3．1 协稀疏信号恢复

§3．1．1 相关工作

§3．2 恢复误差分析

§3．3 非凸(e)p分析最小化方法的优势

§3．3．1 样本复杂度

§3．3．2 协稀疏度的范围

§3．4 求解(e)p分析最小化的迭代重加权算法

§3．5 实验分析

§3．5．1 协稀疏信号恢复

§3．5．2 图像复原

§3．6 本章小结

§3．7 定理证明

第4章 非凸结构稀疏学习模型的快速算法

§4．1 结构稀疏学习模型

§4．1．1 相关工作

§4．2 预备知识

§4．3 交替向前向后分裂算法

§4．4 收敛性分析

§4．5 实验分析

§4．5．1 重叠组Lasso

§4．5．2 图融合Logistic回归

§4．6 本章小结

§4．7 定理证明

第5章 总结与展望

附录

参考文献

致谢

攻读博士学位期间主要的研究成果