稀疏插值中多项式方程组的高效率数值解法

The sparse interpolation problem is interesting and important but not been extensively studied, and has important applications in signal processing. Due to the strongly nonlinearity and ill-conditioning, it is greatly challenging for the research of theoretical analysis and algorithms of the sparse interpolation problem, and has received increasing attention to more and more foreign and domestic scholars. Solving the sparse interpolation problem can be ascribed to a problem of solving polynomial system with a particular structure. Finding properties of solutions of a polynomial system is an essential research subject in algebra, algebraic geometry, and proposing algorithms is an essential and important research subject in computational mathematics and computer mathematics. On the base of our previous work, we will give some properties of solutions of the polynomial system arising from sparse interpolation problems, and propose efficient algorithms for solving them. We concentrate on four issues, 1. Estimating the numbers of isolated solutions and equivalence classes of polynomial system arising from sparse interpolation; 2. Propose an efficient coefficient parameter homotopy method in which the number of paths to be traced is equal to that of equivalence classes, and the smoothness and accessibility hold for the homotopy; 3. The Prony method which is only suited to the equally spaced sampling is extended to the case of unequally spaced sampling; 4. Analyze reasons for the ill-condition and numerical instability, and propose stable algorithms and develop software package.

稀疏插值问题是一类有趣、重要但相对来说研究还不够成熟的数学问题，在信号处理等方面中有重要应用．强非线性和病态性使其理论和计算方法研究具有很大的挑战性，近年来受到越来越多的国内外学者的关注．稀疏插值问题可以归结为一类具有特殊结构的多项式方程组的求解问题．多项式方程组解的研究是代数学、代数几何学的核心课题，而有关算法研究是计算数学与计算机数学的重要而困难的研究课题．本项目将在前期工作基础上，研究非等距稀疏插值中多项式方程组的解的性质和高效率的解法．主要研究如下内容：1、估计非等距稀疏插值问题中的多项式方程组孤立解的个数及解的等价类的个数；2、构造求解这类多项式组的高效率同伦方法，使所需跟踪路径条数与等价类个数相等，并证明同伦的光滑性和可达性；3、将只适用于等距稀疏插值的Prony方法推广到非等距情形；4、分析病态性和算法数值不稳定性的主要因素，设计数值稳定的计算方法并研制相应软件包．

本项目在非等距稀疏插值问题、以及凸二次优化和稀疏优化问题的高效率解法方面进行了深入研究．在稀疏插值问题方面：1）对若干采样情形，我们给出稀疏插值问题中的多项式方程组的孤立解的个数及其等价类的个数，并对部分情形给出理论证明；2）基于系数参数同伦，构造了解稀疏插值问题的多项式同伦方法．该算法的第一阶段只需很小的计算量，第二阶段所需跟踪的同伦路径的条数与解的等价类的个数相等，远远小于孤立解的个数；3）我们给出解非等距稀疏插值问题的增强Prony方法．此外，我们给出了若干更高效的同伦方法来求解凸二次规划和稀疏优化问题．本项目已资助3篇接受发表论文，3篇待发表论文．