Volume 26, pp. 178-189, 2007.

Probability against condition number and sampling of multivariate trigonometric random polynomials

Albrecht Böttcher and Daniel Potts

Abstract

The difficult factor in the condition number $\| A\| \, \| A^{-1}\|$ of a large linear system $Ap=y$ is the spectral norm of $A^{-1}$. To eliminate this factor, we here replace worst case analysis by a probabilistic argument. To be more precise, we randomly take $p$ from a ball with the uniform distribution and show that then, with a certain probability close to one, the relative errors $\| \Delta p\|$ and $\| \Delta y\|$ satisfy $\| \Delta p\| \le C \| \Delta y\|$ with a constant $C$ that involves only the Frobenius and spectral norms of $A$. The success of this argument is demonstrated for Toeplitz systems and for the problem of sampling multivariate trigonometric polynomials on nonuniform knots. The limitations of the argument are also shown.

Full Text (PDF) [265 KB]

Key words

condition number, probability argument, linear system, Toeplitz matrix, nonuniform sampling, multivariate trigonometric polynomial

AMS subject classifications

65F35, 15A12, 47B35, 60H25, 94A20

< Back