{
  "id": "0902.4394",
  "version": "v1",
  "published": "2009-02-25T15:41:38.000Z",
  "updated": "2009-02-25T15:41:38.000Z",
  "title": "Circulant and Toeplitz matrices in compressed sensing",
  "authors": [
    "Holger Rauhut"
  ],
  "comment": "6 pages, submitted to Proc. SPARS'09 (Saint-Malo)",
  "categories": [
    "cs.IT",
    "math.IT"
  ],
  "abstract": "Compressed sensing seeks to recover a sparse vector from a small number of linear and non-adaptive measurements. While most work so far focuses on Gaussian or Bernoulli random measurements we investigate the use of partial random circulant and Toeplitz matrices in connection with recovery by $\\ell_1$-minization. In contrast to recent work in this direction we allow the use of an arbitrary subset of rows of a circulant and Toeplitz matrix. Our recovery result predicts that the necessary number of measurements to ensure sparse reconstruction by $\\ell_1$-minimization with random partial circulant or Toeplitz matrices scales linearly in the sparsity up to a $\\log$-factor in the ambient dimension. This represents a significant improvement over previous recovery results for such matrices. As a main tool for the proofs we use a new version of the non-commutative Khintchine inequality.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-02-25T15:41:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "compressed sensing",
      "bernoulli random measurements",
      "partial random circulant",
      "ensure sparse reconstruction",
      "recovery result predicts"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0902.4394R"
    }
  }
}