{
  "id": "0805.3167",
  "version": "v2",
  "published": "2008-05-20T21:03:15.000Z",
  "updated": "2009-08-10T22:40:19.000Z",
  "title": "Smooth analysis of the condition number and the least singular value",
  "authors": [
    "Terence Tao",
    "Van Vu"
  ],
  "comment": "20 pages, no figures, to appear, Mathematics of Computation",
  "categories": [
    "math.PR"
  ],
  "abstract": "Let $\\a$ be a complex random variable with mean zero and bounded variance. Let $N_{n}$ be the random matrix of size $n$ whose entries are iid copies of $\\a$ and $M$ be a fixed matrix of the same size. The goal of this paper is to give a general estimate for the condition number and least singular value of the matrix $M + N_{n}$, generalizing an earlier result of Spielman and Teng for the case when $\\a$ is gaussian. Our investigation reveals an interesting fact that the ``core'' matrix $M$ does play a role on tail bounds for the least singular value of $M+N_{n} $. This does not occur in Spielman-Teng studies when $\\a$ is gaussian. Consequently, our general estimate involves the norm $\\|M\\|$. In the special case when $\\|M\\|$ is relatively small, this estimate is nearly optimal and extends or refines existing results.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2009-08-10T22:40:19.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11B25"
    ],
    "keywords": [
      "singular value",
      "condition number",
      "smooth analysis",
      "general estimate",
      "refines existing results"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "doi": "10.1007/978-3-642-03685-9_53",
      "journal": "Lecture Notes in Computer Science",
      "year": 2009,
      "volume": 5687,
      "pages": 714
    },
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009LNCS.5687..714T"
    }
  }
}