  This paper proposes an epigraphical relaxation (ERx) technique for
non-proximable mixed norm minimization. Mixed norm regularization methods play
a central role in signal reconstruction and processing, where their
optimization relies on the fact that the proximity operators of the mixed norms
can be computed efficiently. To bring out the power of regularization,
sophisticated layered modeling of mixed norms that can capture inherent signal
structure is a key ingredient, but the proximity operator of such a mixed norm
is often unavailable (non-proximable). Our ERx decouples a layered
non-proximable mixed norm into a norm and multiple epigraphical constraints.
This enables us to handle a wide range of non-proximable mixed norms in
optimization, as long as both the proximal operator of the outermost norm and
the projection onto each epigraphical constraint are efficiently computable.
Moreover, under mild conditions, we prove that ERx does not change the
minimizer of the original problem despite relaxing equality constraints into
inequality ones. We also develop new regularizers based on ERx: one is
decorrelated structure-tensor total variation for color image restoration, and
the other is amplitude-spectrum nuclear norm for low-rank amplitude recovery.
We examine the power of these regularizers through experiments, which
illustrates the utility of ERx.
