{
  "id": "0803.2392",
  "version": "v2",
  "published": "2008-03-17T05:59:48.000Z",
  "updated": "2008-04-17T23:24:21.000Z",
  "title": "CoSaMP: Iterative signal recovery from incomplete and inaccurate samples",
  "authors": [
    "D. Needell",
    "J. A. Tropp"
  ],
  "comment": "30 pages. Revised. Presented at Information Theory and Applications, 31 January 2008, San Diego",
  "journal": "Appl. Comput. Harmon. Anal., Vol. 26, pp. 301-321, 2008",
  "categories": [
    "math.NA",
    "cs.IT",
    "math.IT"
  ],
  "abstract": "Compressive sampling offers a new paradigm for acquiring signals that are compressible with respect to an orthonormal basis. The major algorithmic challenge in compressive sampling is to approximate a compressible signal from noisy samples. This paper describes a new iterative recovery algorithm called CoSaMP that delivers the same guarantees as the best optimization-based approaches. Moreover, this algorithm offers rigorous bounds on computational cost and storage. It is likely to be extremely efficient for practical problems because it requires only matrix-vector multiplies with the sampling matrix. For many cases of interest, the running time is just O(N*log^2(N)), where N is the length of the signal.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-04-17T23:24:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "41A46",
      "68Q25",
      "68W20",
      "90C27"
    ],
    "keywords": [
      "iterative signal recovery",
      "inaccurate samples",
      "incomplete",
      "algorithm offers rigorous bounds",
      "major algorithmic challenge"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0803.2392N"
    }
  }
}