{
  "id": "1710.06763",
  "version": "v1",
  "published": "2017-10-18T14:59:58.000Z",
  "updated": "2017-10-18T14:59:58.000Z",
  "title": "A complete characterization of optimal dictionaries for least squares representation",
  "authors": [
    "Mohammed Rayyan Sheriff",
    "Debasish Chatterjee"
  ],
  "comment": "36 pages",
  "categories": [
    "math.OC",
    "cs.LG",
    "stat.ML"
  ],
  "abstract": "Dictionaries are collections of vectors used for representations of elements in Euclidean spaces. While recent research on optimal dictionaries is focussed on providing sparse (i.e., $\\ell_0$-optimal,) representations, here we consider the problem of finding optimal dictionaries such that representations of samples of a random vector are optimal in an $\\ell_2$-sense. For us, optimality of representation is equivalent to minimization of the average $\\ell_2$-norm of the coefficients used to represent the random vector, with the lengths of the dictionary vectors being specified a priori. With the help of recent results on rank-$1$ decompositions of symmetric positive semidefinite matrices and the theory of majorization, we provide a complete characterization of $\\ell_2$-optimal dictionaries. Our results are accompanied by polynomial time algorithms that construct $\\ell_2$-optimal dictionaries from given data.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-10-18T14:59:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68T05",
      "65K10",
      "42-02"
    ],
    "keywords": [
      "complete characterization",
      "squares representation",
      "random vector",
      "symmetric positive semidefinite matrices",
      "polynomial time algorithms"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 36,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}