Epigraphical Relaxation for Minimizing Layered Mixed Norms

Seisuke Kyochi, Shunsuke Ono, Ivan Selesnick

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number9346035
Pages (from-to)2923-2938
Number of pages16
JournalIEEE Transactions on Signal Processing
StatePublished - 2021


  • Convex optimization
  • epigraph
  • epigraphical projection
  • image recovery
  • structure tensor total variation

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Epigraphical Relaxation for Minimizing Layered Mixed Norms'. Together they form a unique fingerprint.

Cite this