  We consider the recovery of a continuous domain piecewise constant image from
its non-uniform Fourier samples using a convex matrix completion algorithm. We
assume the discontinuities/edges of the image are localized to the zero
levelset of a bandlimited function. This assumption induces linear dependencies
between the Fourier coefficients of the image, which results in a two-fold
block Toeplitz matrix constructed from the Fourier coefficients being low-rank.
The proposed algorithm reformulates the recovery of the unknown Fourier
coefficients as a structured low-rank matrix completion problem, where the
nuclear norm of the matrix is minimized subject to structure and data
constraints. We show that exact recovery is possible with high probability when
the edge set of the image satisfies an incoherency property. We also show that
the incoherency property is dependent on the geometry of the edge set curve,
implying higher sampling burden for smaller curves. This paper generalizes
recent work on the super-resolution recovery of isolated Diracs or signals with
finite rate of innovation to the recovery of piecewise constant images.
