{
  "id": "0707.4203",
  "version": "v4",
  "published": "2007-07-28T02:38:43.000Z",
  "updated": "2008-03-15T18:15:13.000Z",
  "title": "Uniform Uncertainty Principle and signal recovery via Regularized Orthogonal Matching Pursuit",
  "authors": [
    "Deanna Needell",
    "Roman Vershynin"
  ],
  "comment": "This is the final version of the paper, including referee suggestions",
  "categories": [
    "math.NA"
  ],
  "abstract": "This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements -- L_1-minimization methods and iterative methods (Matching Pursuits). We find a simple regularized version of the Orthogonal Matching Pursuit (ROMP) which has advantages of both approaches: the speed and transparency of OMP and the strong uniform guarantees of the L_1-minimization. Our algorithm ROMP reconstructs a sparse signal in a number of iterations linear in the sparsity (in practice even logarithmic), and the reconstruction is exact provided the linear measurements satisfy the Uniform Uncertainty Principle.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2008-03-15T18:15:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68W20",
      "65T50",
      "41A46"
    ],
    "keywords": [
      "uniform uncertainty principle",
      "regularized orthogonal matching pursuit",
      "linear measurements",
      "major algorithmic approaches",
      "sparse signal recovery"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0707.4203N"
    }
  }
}