Abstract: Sparse interpolation is an effective method to reduce the time complexity of computer algebraic algorithms. It has been widely used in the fields of signal processing, compressed sensing, resultant computation, image processing and so on. In order to improve the efficiency of sparse multivariate polynomial interpolation algorithms, an improved sparse interpolation algorithm addressed by Javadi and Monagan is presented. Firstly, the restriction on [T], which is the bound on the number of terms and necessary condition in the original method, has been eliminated. In fact, the exact number of terms in [f] can be obtained by computing the determinant of special defined matrix. Secondly, the necessary condition that the degree bound [D] in [f] must be given in advance has been also eliminated. The exact degree of [f] is obtained by forming an auxiliary function, applying the high probabilistic method, and combining with early termination technique in Cauchy interpolation. Thus the problem of high computational complexity caused by the bad degree bound [D] in Javadi/Monagan algorithm is solved. Compared to Javadi/Monagan algorithm, the theory analysis and experiment results reveal that the performance has been highly improved by applying new algorithm, especially when the given degree bound is too high. Furthermore, the improved algorithm does not need [T] and [D] in advance, so it is more practical to use the interpolation recovery or approximation for real problems.

Key words: sparse interpolation, multivariate polynomial, Javadi/Monagan algorithm, bipartite graph, perfect matching

摘要： 稀疏插值是一种降低计算机代数算法时间复杂度的有效方法，在信号处理、压缩感知、结式计算、图像处理等领域都有广泛应用。为了提高稀疏多元多项式插值算法的效率，对Javadi/Monagan稀疏插值算法进行了改进。首先，消除了必须预先给定项数界[T]的限制，通过计算特定的矩阵行列式，得到插值多项式[f]的准确项数。然后，消除了必须预先给定次数界[D]的限制，通过构造辅助函数，利用概率法结合提前终止技术的Cauchy插值法，得到插值多项式[f]的准确次数，解决了Javadi和Monagan论文中提出的次数界[D]过高而导致的高计算复杂度的问题。理论分析和实验结果表明了改进算法的优势，特别是在给定的次数界[D]过高的情况下，相较于Javadi/Monagan算法，改进算法的性能有较大提高。更进一步，由于改进算法无须给定项数界[T]和次数界[D]，对于实际问题在利用插值恢复或近似时更具实用性。

关键词: 稀疏插值, 多元多项式, Javadi/Monagan算法, 二部图, 完美匹配