论文部分内容阅读
稀疏优化算法目的是求解优化问题的稀疏解。在数据日趋高维化的时代,稀疏性可以帮助人们更好地提炼出最有意义的特征信息,同时削弱噪声等无用信息的干扰。这一思想在信号处理,机器学习等领域都有广泛的应用。?0范数是既直观又理想的稀疏罚函数,但是因为其离散、非凸的性质,对?0的求解通常是一个NP（Non-deterministic Polynomial,NP）-困难问题。为了解决这一难题,学者致力于寻找其它函数代替?0范数。?1范数是对?0范数最好的凸近似,并且成功得到了广泛的应用。然而随着研究的深入,?1范数逐渐不能满足人们对于稀疏性更高的要求,取而代之的是更加复杂的非凸稀疏函数。通常非凸优化问题的求解过程容易困于局部极小点,为了解决这一问题,本文针对分片线性的非凸稀疏函数进行了深入研究。得益于分片线性的特性,本文提出了相应的快速求解算法,具有较好的精度和鲁棒性,并将其成功应用于压缩感知问题和核学习回归问题中。论文的主要研究成果如下:·本文将分片线性非凸稀疏函数与分位数损失函数结合,应用于核学习回归问题。针对非凸函数求解过程中容易困于局部解的问题,本文使用绕山法跳出局部解。原绕山法针对分片线性问题进行全局搜索,故存在效率较低且只能处理较小规模数据的问题。对此,本文提出了随机局部搜索策略,提高其运行效率,使其适用于更大规模的数据集。基于仿真数据和真实数据的实验表明,本文的算法具有一定的全局搜索能力,可以多次跳出浅层局部解,对于本文提出的优化问题的求解精度超过了目前主流的非凸优化算法。·本文将分片线性非凸稀疏函数与线性损失函数结合,应用于混合一比特压缩感知问题。混合一比特压缩感知问题在提出时使用了Hinge损失函数与?1稀疏函数。其中Hinge损失函数给求解带来了难度,?1函数也不能很好满足稀疏性的要求。针对上述问题,本文使用分片线性非凸稀疏函数与线性损失函数结合,并利用ADMM算法迭代求解。本文在仿真数据和真实数据的实验表明,使用线性罚函数代替Hinge损失函数可以在不损失精度的情况下将求解速度提升约10倍。而非凸稀疏函数的引入,可以使解更加稀疏,提升信号恢复的精度。·本文研究了稀疏优化问题的三个应用。首先针对混合一比特压缩感知在过曝光CT重建问题上提出的模型进行了误差界的理论分析。同时将提出的线性混合一比特压缩感知模型应用于带饱和测量值的心电图信号恢复问题上,相较于当前的主流算法取得了优越的效果。最后本文还简单介绍了稀疏优化问题在监控视频前后景分离问题和视频突变点检测问题上的应用。