Adversarial smoothed analysis
The purpose of this note is to extend the results on uniform smoothed analysis of condition numbers from Burgisser et al. (2008) [1] to the case where the perturbation follows a radially symmetric probability distribution. In particular, we will show that the bounds derived in [1] still hold in the case of distributions whose density has a singularity at the center of the perturbation, which we call adversarial. (C) 2010 Elsevier Inc. All rights reserved.
smoothed analysis condition numbers random matrices average case analysis