{
  "id": "1506.07029",
  "version": "v1",
  "published": "2015-06-23T14:29:07.000Z",
  "updated": "2015-06-23T14:29:07.000Z",
  "title": "Alternating Direction Method of Multipliers for Nonconvex Background/Foreground Extraction",
  "authors": [
    "Lei Yang",
    "Ting Kei Pong",
    "Xiaojun Chen"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "In this paper, we propose a new optimization model for extracting background and foreground from a surveillance video. Our model can be nuclear-norm-free, and can incorporate different possibly nonconvex sparsity inducing regularization functions for extracting the foreground, such as the $\\ell_p$ quasi-norm for $0<p<1$. To solve the resulting possibly nonconvex optimization problem, we adapt the alternating direction method of multipliers (ADMM) with a general dual step-size to solving a reformulation that contains three blocks of variables, and analyze its convergence. We show that for any dual step-size less than the golden ratio, there exists a (computable) threshold for the penalty parameter above which the cluster point of the sequence generated by our ADMM gives a stationary point of the nonconvex optimization problem, if the sequence is bounded. We achieve this via a potential function specifically constructed for our ADMM. Moreover, we establish the global convergence of the whole sequence generated if, in addition, this special potential function is a Kurdyka-{\\L}ojasiewicz function. Furthermore, we present a simple strategy for initializing the algorithm to guarantee boundedness of the sequence generated. Finally, we perform numerical experiments comparing our model solved by our ADMM against the $\\ell_1$-based model on real data. The numerical results show that our model outperforms the $\\ell_1$-based model in terms of the quality of the extracted foreground.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-06-23T14:29:07.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "alternating direction method",
      "nonconvex background/foreground extraction",
      "possibly nonconvex optimization problem",
      "nonconvex sparsity inducing regularization",
      "sparsity inducing regularization functions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150607029Y"
    }
  }
}