Global Optimality Guarantees for Nonconvex Unsupervised Video
  Segmentation
  In this paper, we consider the problem of unsupervised video object
segmentation via background subtraction. Specifically, we pose the nonsemantic
extraction of a video's moving objects as a nonconvex optimization problem via
a sum of sparse and low-rank matrices. The resulting formulation, a nonnegative
variant of robust principal component analysis, is more computationally
tractable than its commonly employed convex relaxation, although not generally
solvable to global optimality. In spite of this limitation, we derive intuitive
and interpretable conditions on the video data under which the uniqueness and
global optimality of the object segmentation are guaranteed using local search
methods. We illustrate these novel optimality criteria through example
segmentations using real video data.
