{
  "id": "1303.3595",
  "version": "v2",
  "published": "2013-03-14T20:36:40.000Z",
  "updated": "2013-04-01T20:28:22.000Z",
  "title": "Sparse approximation and recovery by greedy algorithms",
  "authors": [
    "Eugene Livshitz",
    "Vladimir Temlyakov"
  ],
  "categories": [
    "math.NA"
  ],
  "abstract": "We study sparse approximation by greedy algorithms. Our contribution is two-fold. First, we prove exact recovery with high probability of random $K$-sparse signals within $\\lceil K(1+\\e)\\rceil$ iterations of the Orthogonal Matching Pursuit (OMP). This result shows that in a probabilistic sense the OMP is almost optimal for exact recovery. Second, we prove the Lebesgue-type inequalities for the Weak Chebyshev Greedy Algorithm, a generalization of the Weak Orthogonal Matching Pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space setting. However, even in the case of a Hilbert space our results add some new elements to known results on the Lebesque-type inequalities for the RIP dictionaries. Our technique is a development of the recent technique created by Zhang.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-04-01T20:28:22.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "41A65",
      "41A25",
      "41A46",
      "46B20"
    ],
    "keywords": [
      "exact recovery",
      "weak chebyshev greedy algorithm",
      "hilbert space",
      "weak orthogonal matching pursuit",
      "study sparse approximation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1303.3595L"
    }
  }
}