@inproceedings{c7b413816db94153bb260eb302a79720,
title = "Fast estimates of Hankel matrix condition numbers and numeric sparse interpolation",
abstract = "We investigate our early termination criterion for sparse polynomial interpolation when substantial noise is present in the values of the polynomial. Our criterion in the exact case uses Monte Carlo randomization which introduces a second source of error. We harness the Gohberg-Semencul formula for the inverse of a Hankel matrix to compute estimates for the structured condition numbers of all arising Hankel matrices in quadratic arithmetic time overall, and explain how false ill-conditionedness can arise from our randomizations. Finally, we demonstrate by experiments that our condition number estimates lead to a viable termination criterion for polynomials with about 20 non-zero terms and of degree about 100, even in the presence of noise of relative magnitude 10 -5.",
keywords = "Early termination, Gohberg-Semencul formula, Hankel system, Sparse polynomial interpolation, Vandermonde system",
author = "Kaltofen, \{Erich L.\} and Lee, \{Wen Shin\} and Zhengfeng Yang",
year = "2011",
doi = "10.1145/2331684.2331704",
language = "英语",
isbn = "9781450305150",
series = "SNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation",
pages = "130--136",
booktitle = "SNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation",
note = "SNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation ; Conference date: 07-06-2011 Through 09-06-2011",
}