{
  "id": "1601.02513",
  "version": "v1",
  "published": "2016-01-11T16:23:30.000Z",
  "updated": "2016-01-11T16:23:30.000Z",
  "title": "How to learn a graph from smooth signals",
  "authors": [
    "Vassilis Kalofolias"
  ],
  "comment": "8 pages + supplementary material. Accepted in AISTATS 2016, Cadiz, Spain",
  "categories": [
    "stat.ML",
    "cs.LG",
    "physics.data-an"
  ],
  "abstract": "We propose a framework that learns the graph structure underlying a set of smooth signals. Given $X\\in\\mathbb{R}^{m\\times n}$ whose rows reside on the vertices of an unknown graph, we learn the edge weights $w\\in\\mathbb{R}_+^{m(m-1)/2}$ under the smoothness assumption that $\\text{tr}{X^\\top LX}$ is small. We show that the problem is a weighted $\\ell$-1 minimization that leads to naturally sparse solutions. We point out how known graph learning or construction techniques fall within our framework and propose a new model that performs better than the state of the art in many settings. We present efficient, scalable primal-dual based algorithms for both our model and the previous state of the art, and evaluate their performance on artificial and real data.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-01-11T16:23:30.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "smooth signals",
      "construction techniques fall",
      "graph structure",
      "real data",
      "rows reside"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160102513K"
    }
  }
}