免费论文：大规模约束系统的复杂性分析和压缩感知重构算法研究

本文主要研究大规模约束系统的复杂性理论以及以压缩感知为代表的实际应用等研究热点、难点问题。综合使用统计物理、概率统计以及动力系统方法，对约束系统的解空间结构复杂性，搜索类求解算法的动力学复杂性，一类实际约束系统—压缩感知问题的重构算法设计和分析方面进行了深入研究。 在解空间结构复杂性方面，本文对一类由线性和非线性布尔方程组成的大规模代数系统MAS的解空间结构变化进行了研究。通过调节非线性方程的比例p，此MAS模型实现从XORSAT模型(p=0)到MAS-nonlinear模型(p=1)的平稳过渡。本文对解空间出现的一系列相变现象进行系统、完整的分析，并且展示相变过程如何随参数p演化。首先，应用概率方法和统计物理中的能量1RSB腔方法，计算出MAS的满足性阈值，并且得到参数的一个取值区域使得该区域内MAS的满足性完全取决于其MAS-nonlinear子问题。进一步，应用熵的1RSB腔方法确定出三个重要的非满足性相变点，并且展示了解空间随着参数p的增加所经历的不同相变过程。 在搜索类算法的动力学复杂性方面，针对算法失效与原问题存在指数个亚稳态之间的密切关系，本文对一类可解模型的亚稳态演化问题进行了研究。通过引入植入思想，把能量随温度演化这一动力学问题转化为Nishimori线上对应模型的热力学性质这一静力学问题，从而得到了能量演化过程的严格理论结果。 在实际约束系统方面，本文对压缩感知问题进行了研究。压缩感知是一种全新信号获取方式。它以压缩的方式获取信号，再利用计算手段和方法实现信号重构。由于该方法大大降低了原有的测量数从而节省了时间和空间。然而，当前使用的重构方法的重构极限远远高于理论重构极限，即真实的信号密度。针对这一问题，我们设计出一种全新的重构方法使得测量数极为接近理论重构极限时依然能实现信号精确重构。该方法由三部分组成：信号重构的概率准则，具有参数学习能力的信息传递算法以及受晶体成核理论启发的特殊测量矩阵。本文用统计物理方法对新重构方法进行了理论分析。该方法极好的重构效果在数值实验中得到了验证。

来源：半壳优胜育转载请保留出处和链接！

本文链接：http://www.87cpy.com/262940.html