Universal Architectures for the Learning of Polyhedral Norms and Convex Regularizers

Michael Unser and Stanislas Ducotterd · 2025

Read Universal Architectures for the Learning of Polyhedral Norms and Convex Regularizers by Michael Unser and Stanislas Ducotterd (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-19190.txt.

Introduction

Michael Unser and Stanislas Ducotterd learn convex regularizers for image reconstruction in a 2025 paper. Rebuilding an image from few facts needs guidance from prior structure, and convex penalties give it with proofs attached. Learned penalties could beat ones made by hand.

A rule that the rebuild keep pace when image amplitude is scaled cuts fair penalties down to powers of a seminorm. Polyhedral norms can match any of those powers as closely as one likes, and two paired forms come from the geometry. One form learns a dictionary with a sparsity penalty, and the other trains an operator with a bound on its size. Both forms are proven to match all such penalties, and a tight frame makes training work in practice. In denoising and medical scan tests, the frame beat classic sparse methods on quality. Its proofs on settling and on holding up matched the older theory.

Catalog record

CREATORMichael Unser and Stanislas Ducotterd
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-19190

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Universal Architectures for the Learning of Polyhedral Norms and Convex Regularizers Thanks: The research leading to these results has received funding from the European Research Council under Grant ERC-2020-AdG FunLearn-101020573. Michael Unser and Stanislas Ducotterd Abstract This paper addresses the task of learning convex regularizers to guide the reconstruction of images from limited data. By imposing that the reconstruction be amplitude-equivariant, we narrow down the class of admissible functionals to those that can be expressed as a power of a seminorm. We then show that such functionals can be approximated to arbitrary precision with the help of polyhedral norms. In particular, we identify two dual parameterizations of such systems: (i) a synthesis (or atomic) form with an ℓ 1 \ell_{1} -penalty that involves some learnable dictionary; and (ii) an analysis form with an ℓ ∞ \ell_{\infty} -penalty that involves a trainable regularization operator. After having provided geometric insights and proved that the two forms are universal, we propose an implementation that relies on a specific architecture (tight frame with a weighted ℓ 1 \ell_{1} penalty) that is easy to train. We illustrate its use for denoising and the reconstruction of biomedical images. We find that the proposed framework outperforms the sparsity-based methods of compressed sensing, while it offers essentially the same convergence and robustness guarantees. keywords convex optimization, regularization, learning, image reconstruction, sparsity, dictionaries MSC 47A52, 65K10, 46N10, 65J20 1 Introduction The context of this work is computational imaging where the goal is to reconstruct an image from indirect and possibly incomplete measurements. We focus on scenarios where the measurements are linear functionals of the object under investigation, such as line integrals in computer tomography [ 62 ] or samples of its Fourier transform in magnetic resonance imaging [ 47 ] . These quantities are corrupted by noise according to the relation {\bf{y}}={\bf{H}}{\bf{s}}+{\bf{n}}_{\rm noise}\in\mathbb{R}^{M} , where {\bf{s}}\in\mathbb{R}^{d} is the unknown signal to be recovered and {\bf{H}}\in\mathbb{R}^{M\times d} is the system matrix that results from the discretization of the physics. Given a candidate signal \tilde{{\bf{s}}} , the forward model is simulated as {\bf{H}}\tilde{{\bf{s}}} which, for consistency, ought to match {\bf{y}} within the noise level. Computational imaging is currently dominated by two paradigms [ 52 , 66 ] . The first one is the variational approach, where the reconstruction task is formulated as a cost minimization problem, as in ( 1 ). Variational techniques have driven the development of image reconstruction algorithms over the past three decades. They are supported by an extensive theory and benefit from the powerful computational tools of convex optimization [ 28 , 10 ] and compressed sensing [ 29 , 20 , 32 ] . Solutions are typically computed iteratively through the minimization of a cost, either by steepest descent or by proximal-gradient techniques [ 31 , 24 , 30 , 7 ] . Under standard hypotheses (convexity and coercivity of the cost functional), this framework provides guarantees for convergence [ 28 ] , stability [ 26 ] , and signal recovery from limited measurements [ 27 , 17 ] . The second paradigm, at the forefront of research, is the data-driven approach, often referred to as artificial intelligence (AI), where the traditional reconstruction pipeline is replaced or complemented by deep neural networks (DNN) [ 43 , 51 , 78 , 48 ] . Formally, the resulting reconstruction algorithm is a nonlinear map {\bf{f}}_{{\boldsymbol{\theta}}}:\mathbb{R}^{M}\to\mathbb{R}^{d} with parameters {\boldsymbol{\theta}} (the weights of the neural net). These are pre-trained for best performance in a regression task such that {\bf{f}}_{{\boldsymbol{\theta}}}({\bf{y}}_{k})\approx{\bf{s}}_{k} on a representative set of data ({\bf{s}}_{k},{\bf{y}}_{k})_{k=1}^{K} , where K (the number of training images) is assumed to be sufficiently large. DNN-based methods generally achieve superior image reconstructions [ 79 ] but suffer from a lack of robustness [ 3 ] and theoretical understanding. More importantly, they have been found to remove or hallucinate structures [ 61 , 57 ] , which is unacceptable in medical imaging. Hybrid approaches aim to combine the strengths of both paradigms [ 59 ] and can be broadly classified in two categories. (i) Trainable regularizers : The guiding principle here is to select a parametric regularization functional {\bf{s}}\mapsto g_{{\boldsymbol{\theta}}}({\bf{s}}) and to then optimize its parameters {\boldsymbol{\theta}} (training) for best performance within the variational setting [ 41 , 1 ] . An early example is the field of expert (FoE) model [ 68 ] , where g({\bf{s}})=\sum_{k}\phi_{k}({\bf{w}}_{k}^{\mathsf{T}}{\bf{s}})=\langle{\bf{1}},{\boldsymbol{\Phi}}({\bf{W}}{\bf{s}})\rangle is a sum of ridges. These ridges result from the application of a convex function \phi_{k}:\mathbb{R}\to\mathbb{R}^{+} (potential) to some filtered versions of the signal, with the filtering templates {\bf{w}}_{k} (collectively encoded in {\bf{W}} ) being learned. Enhanced versions of this model allow for trainable potentials under convexity constraints [ 21 , 63 , 35 ] . A notable alternative involves using an input-convex neural network [ 2 ] to model the regularizer, as suggested in [ 58 ] . (ii) Deep unrolling : The methods in this category typically originate from an existing variational reconstruction algorithm that is reconfigured it into a trainable architecture (unrolling) [ 56 ] . This is exemplified in the plug-and-play (PnP) framework [ 77 , 44 ] , where deep-learning-based denoisers replace traditional proximal operators [ 19 , 70 , 74 ] . For these methods to remain variational, the learned denoiser must satisfy both firm non-expansiveness (for convergence [ 42 , Proposition 15] ) and monotonicity [ 6 , 36 ] , the latter being challenging to enforce. This raises a fundamental question: To what extent can one improve variational methods by learning the regularizer, while maintaining their theoretical guarantees? While the FoE model substantially improves upon “handcrafted” regularizers such as total variation (TV) [ 34 ] , its expressiveness may still be insufficient to capture the full range of convex regularizations. We contend that further improvements are possible within the variational framework under adequate constraints to avoid hallucinations. To address these issues, we introduce a general parametric framework for image reconstruction under the constraints of amplitude equivariance (AE) and convexity. This parameterization involves polyhedral norms and results in a formulation that is reminiscent of compressed-sensing techniques with a trainable dictionary [ 69 , 29 ] . Our present contribution is two fold: 1. The identification of two dual forms of polyhedral regularization with proof of their universality, in the sense that they are able to encode any AE convex regularizer to an \epsilon -level of precision. 2. The transcription of the theory into practical reconstruction architectures, including a constrained version that lends itself well to training. The paper is organized as follows. In Section 2 , we formalize the variational reconstruction problem and invoke higher-level principles (amplitude-equivariance and coercivity) to narrow down the class of admissible regularization functionals to some power of a norm, as dictated by Theorem 3 . In Section 3 , we prove that we can achieve universality with the help of polyhedral norms (Theorem 7 ), the latter admitting two dual parameterizations in terms of some linear operator, as stated in Theorem 6 . The theoretical foundation for our results is presented in Section 4 with a complete characterization of the geometry of polyhedral Banach spaces (Theorem 10 ) in connection with atomic norms [ 20 ] . In Section 5 , we use our results to specify

Read the complete text