基于顺序重要度采样策略的积和式近似算法

论文摘要

矩阵积和式是一种常用的矩阵不变量，在组合计数、统计检验、无线通讯、统计物理、分子化学等领域有重要的应用。积和式的定义与行列式相似，但是它的计算复杂性远远高于行列式。英国理论计算机科学家Valiant在1979年证明积和式计算是组合计数中的#P完全问题，即其难度不低于组合优化中的NP完全问题。迄今为止，对一般矩阵最为有效的积和式精确算法是Ryser基于容斥原理所建立，其计算复杂性为O(n2n-1)。该算法只对阶数不超过40的矩阵有效。近年来，由于应用问题对更大规模矩阵积和式计算的需求，人们的研究兴趣集中在发展有效的积和式近似算法。积和式近似算法主要分为以下三类：（1）马尔科夫链蒙特卡洛；（2）行列式转化；（3）随机Laplace展开。各类算法都有其自身的优势与适用的范围。具体的应用问题根据矩阵的特殊结构特征，针对特定背景设计适合的近似算法。本文研究统计学中置换检验问题与统计物理中dimer常数计算涉及的积和式计算。这些问题需要计算稀疏0-1结构矩阵的积和式。随机Laplace展开类的算法是适合于这类问题的实用积和式近似算法。本文将随机Laplace展开类的算法归入顺序重要度采样的理论框架下，利用顺序重要度采样和重抽样策略得到了基于随机Laplace展开的改进积和式近似算法。本文的主要贡献有：给出了一个新的矩阵积和式上界估计；将Fearnhead与Cliford提出的顺序重要度抽样理论的最优重抽样策略应用于稀疏矩阵积和式的近似算法设计；将算法应用于统计学置换检验与统计物理中的dimer覆盖模型，大量计算表明，基于新的上界以及最优重抽样策略的算法优于此前的随机Laplace展开类算法。

论文目录

• 摘要
• Abstract
• 第1章 引论
• 1.1 矩阵积和式
• 1.2 置换检验
• 1.3 Dimer覆盖
• 1.4 研究现状
• 1.5 本文的主要工作
• 第2章 顺序重要度采样与重抽样策略
• 2.1 顺序重要度采样
• 2.1.1 恰当赋权样本
• 2.1.2 构造序列
• 2.1.3 局部蒙特卡洛方法
• 2.1.4 优化方法
• 2.2 重抽样策略
• 2.2.1 重抽样方法
• 2.2.2 重抽样算法
• 2.3 在截断数据分析中的应用
• 第3章 基于顺序重要度抽样的积和式近似算法
• 3.1 RAS算法
• 3.2 随机路径算法
• 第4章 改进算法
• 4.1 基于界估计的改进算法
• 4.1.1 矩阵积和式的上界估计
• 4.1.2 基于改进上界的顺序重要采样算法
• 4.1.3 数值结果
• 4.2 基于重抽样策略的改进算法
• 4.2.1 Fearnhead与Cliford的最优重抽样策略
• 4.2.2 基于FC重抽样策略的顺序重要采样算法
• 4.2.3 数值结果
• 第5章 结论
• 参考文献
• 致谢
• 个人简历