  We characterize proximity operators, that is to say functions that map a
vector to a solution of a penalized least squares optimization problem.
Proximity operators of convex penalties have been widely studied and fully
characterized by Moreau. They are also widely used in practice with nonconvex
penalties such as the {\ell} 0 pseudo-norm, yet the extension of Moreau's
characterization to this setting seemed to be a missing element of the
literature. We characterize proximity operators of (convex or nonconvex)
penalties as functions that are the subdifferential of some convex potential.
This is proved as a consequence of a more general characterization of so-called
Bregman proximity operators of possibly nonconvex penalties in terms of certain
convex potentials. As a side effect of our analysis, we obtain a test to verify
whether a given function is the proximity operator of some penalty, or not.
Many well-known shrinkage operators are indeed confirmed to be proximity
operators. However, we prove that windowed Group-LASSO and persistent empirical
Wiener shrinkage -- two forms of so-called social sparsity shrinkage-- are
generally not the proximity operator of any penalty; the exception is when they
are simply weighted versions of group-sparse shrinkage with non-overlapping
groups.
