Adversarial smoothed analysis

Martin Lotz; Felipe Cucker; Raphael Hauser

doi:10.1016/j.jco.2009.12.005

Adversarial smoothed analysis

Martin Lotz, Felipe Cucker, Raphael Hauser

School of Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract / Description of output

The purpose of this note is to extend the results on uniform smoothed analysis of condition numbers from Bürgisser 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.

Original language	English
Pages (from-to)	255-262
Number of pages	8
Journal	Journal of Complexity
Volume	26
DOIs	https://doi.org/10.1016/j.jco.2009.12.005
Publication status	Published - 2010

Keywords / Materials (for Non-textual outputs)

Condition numbers
Random matrices
Average case analysis
Smoothed analysis

Access to Document

10.1016/j.jco.2009.12.005

http://www.sciencedirect.com/science/article/pii/S0885064X10000294

Cite this

@article{fd6b8479db5a452f821ebe9426649ae1,

title = "Adversarial smoothed analysis",

abstract = "The purpose of this note is to extend the results on uniform smoothed analysis of condition numbers from B{\"u}rgisser 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.",

keywords = "Condition numbers, Random matrices, Average case analysis, Smoothed analysis",

author = "Martin Lotz and Felipe Cucker and Raphael Hauser",

year = "2010",

doi = "10.1016/j.jco.2009.12.005",

language = "English",

volume = "26",

pages = "255--262",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press",

}

TY - JOUR

T1 - Adversarial smoothed analysis

AU - Lotz, Martin

AU - Cucker, Felipe

AU - Hauser, Raphael

PY - 2010

Y1 - 2010

N2 - The purpose of this note is to extend the results on uniform smoothed analysis of condition numbers from Bürgisser 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.

AB - The purpose of this note is to extend the results on uniform smoothed analysis of condition numbers from Bürgisser 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.

KW - Condition numbers

KW - Random matrices

KW - Average case analysis

KW - Smoothed analysis

U2 - 10.1016/j.jco.2009.12.005

DO - 10.1016/j.jco.2009.12.005

M3 - Article

SN - 0885-064X

VL - 26

SP - 255

EP - 262

JO - Journal of Complexity

JF - Journal of Complexity

ER -

Adversarial smoothed analysis

Abstract / Description of output

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this