  Rank and cardinality penalties are hard to handle in optimization frameworks
due to non-convexity and discontinuity. Strong approximations have been a
subject of intense study and numerous formulations have been proposed. Most of
these can be described as separable, meaning that they apply a penalty to each
element (or singular value) based on size, without considering the joint
distribution. In this paper we present a class of non-separable penalties and
give a recipe for computing strong relaxations suitable for optimization. In
our analysis of this formulation we first give conditions that ensure that the
globally optimal solution of the relaxation is the same as that of the original
(unrelaxed) objective. We then show how a stationary point can be guaranteed to
be unique under the RIP assumption (despite non-convexity of the framework).
