Rank related properties for Basis Pursuit and total variation regularization

This paper focuses on optimization problems containing an l1l1 kind of regularity criterion and a smooth data fidelity term. A general theorem is applied in this context; it gives an estimate of the distribution law of the “rank” of the solution to optimization problems, when the initial datum follows a uniform (in a convex compact set) distribution law. It says that, asymptotically, solutions with a large rank are more and more likely.The main goal of this paper is to understand the meaning of this notion of rank for some energies which are commonly used in image processing. We study in detail the energy whose level sets are defined as the convex hull of a finite subset of RNRN (c.f. Basis Pursuit) and the total variation. For these energies, the notion of rank relates, respectively, to sparse representation and staircasing.In all cases but the 2D total variation, we are able to adapt the general theorem mentioned above to the energies under consideration.