{
  "id": "1301.6268",
  "version": "v3",
  "published": "2013-01-26T16:27:33.000Z",
  "updated": "2014-08-29T19:51:48.000Z",
  "title": "Singular values of Gaussian matrices and permanent estimators",
  "authors": [
    "Mark Rudelson",
    "Ofer Zeitouni"
  ],
  "comment": "small revision, no major changes. Changed terminology to \"broadly connected\". Corrected error in probability estimate in statement of theorems 1.4 and 1.5",
  "categories": [
    "math.PR",
    "cs.DS"
  ],
  "abstract": "We present estimates on the small singular values of a class of matrices with independent Gaussian entries and inhomogeneous variance profile, satisfying a broad-connectedness condition. Using these estimates and concentration of measure for the spectrum of Gaussian matrices with independent entries, we prove that for a large class of graphs satisfying an appropriate expansion property, the Barvinok--Godsil-Gutman estimator for the permanent achieves sub-exponential errors with high probability.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-12-28T05:52:45.000Z",
      "comment": "small revision, no major changes. Changed terminology to \"broadly connected\"",
      "journal": null,
      "doi": null
    },
    {
      "version": "v3",
      "updated": "2014-08-29T19:51:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "gaussian matrices",
      "permanent estimators",
      "permanent achieves sub-exponential errors",
      "appropriate expansion property",
      "small singular values"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1301.6268R"
    }
  }
}