We use the PAC-Bayesian theory for the setting of learning-to-optimize. To the best of our knowledge, we present the first framework to learn optimization algorithms with provable generalization guarantees (PAC-Bayesian bounds) and explicit trade-off between convergence guarantees and convergence speed, which contrasts with the typical worst-case analysis. Our learned optimization algorithms provably outperform related ones derived from a worst-case analysis. The results rely on PAC-Bayesian bounds for general, possibly unbounded loss-functions based on exponential families. Further, we provide a concrete algorithmic realization of the framework and new methodologies for learning-to-optimize. Finally, we conduct four practically relevant experiments to support our theory. With this, we showcase that the provided learning framework yields optimization algorithms that provably outperform the state-of-the-art by orders of magnitude.

Abstract. We introduce two quasi-Newton forward-backward splitting algorithms to solve a class of monotone inclusion problems. The bottleneck is the evaluation of the resolvent operator. Changing the metric makes its computation even harder, and this is even true for a simple operator whose resolvent is known for the standard metric. To fully exploit the advantage of adapting the metric, we develop a new efficient resolvent calculus for a low-rank perturbed standard metric, which accounts exactly for quasi-Newton metrics. Moreover, we prove the convergence of our algorithms, including linear convergence rates in case one of the two considered operators is strongly monotone. As a by-product of our general monotone inclusion framework, we introduce two variants of the quasi-Newton primal-dual hybrid gradient method (PDHG) for solving saddle point problems. The favorable performance of these two quasi-Newton PDHG methods is demonstrated on several numerical experiments in image processing.

The lack of robustness in neural network classifiers, especially when facing adversarial attacks, is a significant limitation for critical applications. While some researchers have suggested a connection between neuron coverage during training and vulnerability to adversarial perturbations, concrete experimental evidence supporting this claim is lacking. This paper empirically investigates the impact of maximizing neuron coverage during training and assess the effectiveness of adversarial attacks on under-covered neurons. Additionally, we explore the potential of leveraging coverage for designing more efficient attacks. Our experiments reveal no clear correlation between neuron coverage, adversarial robustness, or attack effectiveness.

Abstract. In this paper, we revisit the notion of perimeter on graphs, introduced in El Chakik, Elmoataz, and Desquesnes [ Signal Process., 105 (2014), pp. 449–463], and we extend it to so-called inner and outer perimeters. We will also extend the notion of total variation on graphs. Thanks to the co-area formula, we show that discrete total variations can be expressed through these perimeters. Then, we propose a novel class of curvature operators on graphs that unifies both local and nonlocal mean curvature on an Euclidean domain. This leads us to translate and adapt the notion of the mean curvature flow on graphs as well as the level set mean curvature, which can be seen as approximate schemes. Finally, we exemplify the usefulness of these methods in image processing, 3D point cloud processing, and high dimensional data classification.

Abstract. In this paper, we consider the problem of phase retrieval, which consists of recovering an [Formula: see text]‐dimensional real vector from the magnitude of its [Formula: see text] linear measurements. We propose a mirror descent (or Bregman gradient descent) algorithm based on a wisely chosen Bregman divergence, hence allowing us to remove the classical global Lipschitz continuity requirement on the gradient of the nonconvex phase retrieval objective to be minimized. We apply the mirror descent for two random measurements: the i.i.d. standard Gaussian and those obtained by multiple structured illuminations through coded diffraction patterns. For the Gaussian case, we show that when the number of measurements [Formula: see text] is large enough, then with high probability, for almost all initializers, the algorithm recovers the original vector up to a global sign change. For both measurements, the mirror descent exhibits a local linear convergence behavior with a dimension-independent convergence rate. Finally, our theoretical results are illustrated with various numerical experiments, including an application to the reconstruction of images in precision optics.

Abstract Lipschitz continuity of the gradient mapping of a continuously differentiable function plays a crucial role in designing various optimization algorithms. However, many functions arising in practical applications such as low rank matrix factorization or deep neural network problems do not have a Lipschitz continuous gradient. This led to the development of a generalized notion known as the L-smad property, which is based on generalized proximity measures called Bregman distances. However, the L-smad property cannot handle nonsmooth functions, for example, simple nonsmooth functions like $$\vert x^4-1 \vert $$ | x 4 - 1 | and also many practical composite problems are out of scope. We fix this issue by proposing the MAP property, which generalizes the L-smad property and is also valid for a large class of structured nonconvex nonsmooth composite problems. Based on the proposed MAP property, we propose a globally convergent algorithm called Model BPG, that unifies several existing algorithms. The convergence analysis is based on a new Lyapunov function. We also numerically illustrate the superior performance of Model BPG on standard phase retrieval problems and Poisson linear inverse problems, when compared to a state of the art optimization method that is valid for generic nonconvex nonsmooth optimization problems.

Discretized Langevin diffusions are efficient Monte Carlo methods for sampling from high dimensional target densities that are log-Lipschitz-smooth and (strongly) log-concave. In particular, the Euclidean Langevin Monte Carlo sampling algorithm has received much attention lately, leading to a detailed understanding of its non-asymptotic convergence properties and of the role that smoothness and log-concavity play in the convergence rate. Distributions that do not possess these regularity properties can be addressed by considering a Riemannian Langevin diffusion with a metric capturing the local geometry of the log-density. However, the Monte Carlo algorithms derived from discretizations of such Riemannian Langevin diffusions are notoriously difficult to analyze. In this paper, we consider Langevin diffusions on a Hessian-type manifold and study a discretization that is closely related to the mirror-descent scheme. We establish for the first time a non-asymptotic upper-bound on the sampling error of the resulting Hessian Riemannian Langevin Monte Carlo algorithm. This bound is measured according to a Wasserstein distance induced by a Riemannian metric ground cost capturing the squared Hessian structure and closely related to a self-concordance-like condition. The upper-bound implies, for instance, that the iterates contract toward a Wasserstein ball around the target density whose radius is made explicit. Our theory recovers existing Euclidean results and can cope with a wide variety of Hessian metrics related to highly non-flat geometries.

Low-complexity non-smooth convex regularizers are routinely used to impose some structure (such as sparsity or low-rank) on the coefficients for linear predictors in supervised learning. Model consistency consists then in selecting the correct structure (for instance support or rank) by regularized empirical risk minimization. It is known that model consistency holds under appropriate non-degeneracy conditions. However such conditions typically fail for highly correlated designs and it is observed that regularization methods tend to select larger models. In this work, we provide the theoretical underpinning of this behavior using the notion of mirror-stratifiable regularizers. This class of regularizers encompasses the most well-known in the literature, including the L1 or trace norms. It brings into play a pair of primal-dual models, which in turn allows one to locate the structure of the solution using a specific dual certificate. We also show how this analysis is applicable to optimal solutions of the learning problem, and also to the iterates computed by a certain class of stochastic proximal-gradient algorithms.

In this paper, we study a nonlocal variational problem which consists of minimizing in $L^2$ the sum of a quadratic data fidelity and a regularization term corresponding to the $L^p$-norm of the nonlocal gradient. In particular, we study convergence of the numerical solution to a discrete version of this nonlocal variational problem to the unique solution of the continuum one. To do so, we derive an error bound and highlight the role of the initial data and the kernel governing the nonlocal interactions. When applied to variational problems on graphs, this error bound allows us to show the consistency of the discretized variational problem as the number of vertices goes to infinity. More precisely, for networks in convergent graph sequences (simple and weighted deterministic dense graphs as well as random inhomogeneous graphs), we prove convergence and provide rates of convergence of solutions for the discrete models to the solution of the continuum problem as the number of vertices grows.

This paper studies least-square regression penalized with partly smooth convex regularizers. This class of penalty functions is very large and versatile, and allows to promote solutions conforming to some notion of low complexity. Indeed, such penalties/regularizers force the corresponding solutions to belong to a low-dimensional manifold (the so-called model), which remains stable when the argument of the penalty function undergoes small perturbations. Such a good sensitivity property is crucial to make the underlying low-complexity (manifold) model robust to small noise. In a deterministic setting, we show that a generalized “irrepresentable condition” implies stable model selection under small noise perturbations in the observations and the design matrix, when the regularization parameter is tuned proportionally to the noise level. As an algorithmic implication, we also prove that this condition is almost necessary for stable model recovery. We then turn to the random setting, where the design matrix and the noise are random, and the number of observations grows large. We show that under our generalized “irrepresentable condition,” and a proper scaling of the regularization parameter, the regularized estimator is model consistent. In plain words, with a probability tending to one as the number of measurements tends to infinity, the regularized estimator belongs to the correct low-dimensional model manifold. This paper unifies and generalizes a large body of literature, where model consistency was known to hold, for instance for the Lasso, group Lasso, total variation (fused Lasso), and nuclear/trace norm regularizers. As an algorithmic implication, we show that under the deterministic model selection conditions, the forward-backward proximal splitting algorithm used to solve the penalized least-square regression problem is guaranteed to identify the model manifold after a finite number of iterations. Finally, we detail how our results extend from the quadratic loss to an arbitrary smooth and strictly convex loss function. We illustrate the usefulness of our results on the problem of low-rank matrix recovery from random measurements using nuclear norm minimization.

In this paper, we study the support recovery guarantees of underdetermined sparse regression using the $\ell_1$-norm as a regularizer and a non-smooth loss function for data fidelity. More precisely, we focus in detail on the cases of $\ell_1$ and $\ell_\infty$ losses, and contrast them with the usual $\ell_2$ loss.While these losses are routinely used to account for either sparse ($\ell_1$ loss) or uniform ($\ell_\infty$ loss) noise models, a theoretical analysis of their performance is still lacking. In this article, we extend the existing theory from the smooth $\ell_2$ case to these non-smooth cases. We derive a sharp condition which ensures that the support of the vector to recover is stable to small additive noise in the observations, as long as the loss constraint size is tuned proportionally to the noise level. A distinctive feature of our theory is that it also explains what happens when the support is unstable. While the support is not stable anymore, we identify an "extended support" and show that this extended support is stable to small additive noise. To exemplify the usefulness of our theory, we give a detailed numerical analysis of the support stability/instability of compressed sensing recovery with these different losses. This highlights different parameter regimes, ranging from total support stability to progressively increasing support instability.

In this paper, we propose a multi-step inertial Forward--Backward splitting algorithm for minimizing the sum of two non-necessarily convex functions, one of which is proper lower semi-continuous while the other is differentiable with a Lipschitz continuous gradient. We first prove global convergence of the scheme with the help of the Kurdyka–Łojasiewicz property. Then, when the non-smooth part is also partly smooth relative to a smooth submanifold, we establish finite identification of the latter and provide sharp local linear convergence analysis. The proposed method is illustrated on a few problems arising from statistics and machine learning.

In this work, we first provide iteration-complexity bounds (pointwise and ergodic) for the inexact Krasnosel'skî-Mann iteration built from nonexpansive operators. Moreover, under an appropriate regularity assumption on the fixed point operator, local linear convergence rate is also established. These results are then applied to analyze the convergence rate of various proximal splitting methods in the literature, which includes the Forward-Backward, generalized Forward-Backward, Douglas-Rachford, ADMM and some primal-dual splitting methods. For these algorithms, we develop easily verifiable termination criteria for finding an approximate solution, which is a generalization of the termination criterion for the classical gradient descent method. We illustrate the usefulness of our results on a large class of problems in signal and image processing.

Algorithms for solving variational regularization of ill-posed inverse problems usually involve operators that depend on a collection of continuous parameters. When the operators enjoy some (local) regularity, these parameters can be selected using the so-called Stein Unbiased Risk Estimator (SURE). While this selection is usually performed by an exhaustive search, we address in this work the problem of using the SURE to efficiently optimize for a collection of continuous parameters of the model. When considering nonsmooth regularizers, such as the popular $\ell_1$-norm corresponding to soft-thresholding mapping, the SURE is a discontinuous function of the parameters preventing the use of gradient descent optimization techniques. Instead, we focus on an approximation of the SURE based on finite differences as proposed by Ramani and Unser for the Monte-Carlo SURE approach. Under mild assumptions on the estimation mapping, we show that this approximation is a weakly differentiable function of the parameters and its weak gradient, coined the Stein Unbiased GrAdient estimator of the Risk (SUGAR), provides an asymptotically (with respect to the data dimension) unbiased estimate of the gradient of the risk. Moreover, in the particular case of soft-thresholding, it is proved to also be a consistent estimator. This gradient estimate can then be used as a basis for performing a quasi-Newton optimization. The computation of the SUGAR relies on the closed-form (weak) differentiation of the nonsmooth function. We provide its expression for a large class of iterative methods including proximal splitting methods and apply our strategy to regularizations involving nonsmooth convex structured penalties. Illustrations of various image restoration and matrix completion problems are given.

This paper introduces a generalized forward-backward splitting algorithm for finding a zero of a sum of maximal monotone operators $B + \sum_{i=1}^n A_i$, where $B$ is cocoercive. It involves the computation of $B$ in an explicit (forward) step and the parallel computation of the resolvents of the $A_i$'s in a subsequent implicit (backward) step. We prove the algorithm's convergence in infinite dimension and its robustness to summable errors on the computed operators in the explicit and implicit steps. In particular, this allows efficient minimization of the sum of convex functions $f + \sum_{i=1}^n g_i$, where $f$ has a Lipschitz-continuous gradient and each $g_i$ is simple in the sense that its proximity operator is easy to compute. The resulting method makes use of the regularity of $f$ in the forward step, and the proximity operators of the $g_i$'s are applied in parallel in the backward step. While the forward-backward algorithm cannot deal with more than $n = 1$ nonsmooth function, we generalize it to the case of arbitrary $n$. Examples on inverse problems in imaging demonstrate the advantage of the proposed methods in comparison to other splitting algorithms.

This paper addresses the problem of stably recovering sparse or compressible signals from compressed sensing measurements that have undergone optimal nonuniform scalar quantization, i.e., minimizing the common$\ell _{2}$-norm distortion. Generally, this quantized compressed sensing (QCS) problem is solved by minimizing the$\ell _{1}$-norm constrained by the$\ell _{2}$-norm distortion. In such cases, remeasurement and quantization of the reconstructed signal do not necessarily match the initial observations, showing that the whole QCS model is not consistent. Our approach considers instead that quantization distortion more closely resembles heteroscedastic uniform noise, with variance depending on the observed quantization bin. Generalizing our previous work on uniform quantization, we show that for nonuniform quantizers described by the “compander” formalism, quantization distortion may be better characterized as having bounded weighted$\ell _{p}$-norm ($p \geqslant 2$), for a particular weighting. We develop a new reconstruction approach, termed Generalized Basis Pursuit DeNoise (GBPDN), which minimizes the$\ell _{1}$-norm of the signal to reconstruct constrained by this weighted$\ell _{p}$-norm fidelity. We prove that, for standard Gaussian sensing matrices and$K$sparse or compressible signals in$ \BBR ^{N}$with at least$\Omega ((K \log N/K)^{p/2})$measurements, i.e., under strongly oversampled QCS scenario, GBPDN is$\ell _{2}-\ell _{1}$instance optimal and stable recovers all such sparse or compressible signals. The reconstruction error decreases as$O(2^{-B}/\sqrt {p+1})$given a budget of$B$bits per measurement. This yields a reduction by a factor$\sqrt {p+1}$of the reconstruction error compared to the one produced by$\ell _{2}$-norm constrained decoders. We also propose an primal-dual proximal splitting scheme to solve the GBPDN program which is efficient for large-scale problems. Interestingly, extensive simulations testing the GBPDN effectiveness confirm the trend predicted by the theory, that the reconstruction error can indeed be reduced by increasing$p$, but this is achieved at a much less stringent oversampling regime than the one expected by the theoretical bounds. Besides the QCS scenario, we also show that GBPDN applies straightforwardly to the related case of CS measurements corrupted by heteroscedastic generalized Gaussian noise with provable reconstruction error reduction.

This paper investigates the theoretical guarantees of$\ell^{1}$-analysis regularization when solving linear inverse problems. Most of previous works in the literature have mainly focused on the sparse synthesis prior where the sparsity is measured as the$\ell^{1}$norm of the coefficients that synthesize the signal from a given dictionary. In contrast, the more general analysis regularization minimizes the$\ell^{1}$norm of the correlations between the signal and the atoms in the dictionary, where these correlations define the analysis support. The corresponding variational problem encompasses several well-known regularizations such as the discrete total variation and the fused Lasso. Our main contributions consist in deriving sufficient conditions that guarantee exact or partial analysis support recovery of the true signal in presence of noise. More precisely, we give a sufficient condition to ensure that a signal is the unique solution of the$\ell^{1}$-analysis regularization in the noiseless case. The same condition also guarantees exact analysis support recovery and$\ell^{2}$-robustness of the$\ell^{1}$-analysis minimizer vis-à-vis an enough small noise in the measurements. This condition turns to be sharp for the robustness of the sign pattern. To show partial support recovery and$\ell^{2}$-robustness to an arbitrary bounded noise, we introduce a stronger sufficient condition. When specialized to the$\ell^{1}$-synthesis regularization, our results recover some corresponding recovery and robustness guarantees previously known in the literature. From this perspective, our work is a generalization of these results. We finally illustrate these theoretical findings on several examples to study the robustness of the 1-D total variation, shift-invariant Haar dictionary, and fused Lasso regularizations.

In this paper, we propose a rigorous derivation of the expression of the projected Generalized Stein Unbiased Risk Estimator (GSURE) for the estimation of the (projected) risk associated to regularized ill-posed linear inverse problems using sparsity-promoting ℓ1penalty. The projected GSURE is an unbiased estimator of the recovery risk on the vector projected on the orthogonal of the degradation operator kernel. Our framework can handle many well-known regularizations including sparse synthesis- (e.g. wavelet) and analysis-type priors (e.g. total variation). A distinctive novelty of this work is that, unlike previously proposed ℓ1risk estimators, we have a closed-form expression that can be implemented efficiently once the solution of the inverse problem is computed. To support our claims, numerical examples on ill-posed inverse problems with analysis and synthesis regularizations are reported where our GSURE estimates are used to tune the regularization parameter.

In this paper, we propose a novel and rigorous framework for region-based active contours that combines the Wasserstein distance between statistical distributions in arbitrary dimension and shape derivative tools. To speed-up the computation and be able to handle high-dimensional features and large-scale data, we introduce an approximation of the differential of the Wasserstein distance between histograms. The framework is flexible enough to allow either minimization of the Wasserstein distance to prior distributions, or maximization of the distance between the distributions of the regions to be segmented (i.e. region competition). Numerical results reported demonstrate the advantages of the proposed optimal transport distance with respect to point-wise metrics.

We describe efficient implementations of the proximity calculation for a useful class of functions; the implementations exploit the piece-wise linear nature of the dual problem. The second part of the paper applies the previous result to acceleration of convex minimization problems, and leads to an elegant quasi-Newton method. The optimization method compares favorably against state-of-the-art alternatives. The algorithm has extensive applications including signal processing, sparse regression and recovery, and machine learning and classification.

The matter density is an important knowledge for today cosmology as many phenomena are linked to matter fluctuations. However, this density is not directly available, but estimated through lensing maps or galaxy surveys. In this article, we focus on galaxy surveys which are incomplete and noisy observations of the galaxy density. Incomplete, as part of the sky is unobserved or unreliable. Noisy as they are count maps degraded by Poisson noise. Using a data augmentation method, we propose a two-step method for recovering the density map, one step for inferring missing data and one for estimating the density. The results show that the missing areas are efficiently inferred and the statistical properties of the maps are preserved.

In this paper, we propose two algorithms for solving linear inverse problems when the observations are corrupted by Poisson noise. A proper data fidelity term (log-likelihood) is introduced to reflect the Poisson statistics of the noise. On the other hand, as a prior, the images to restore are assumed to be positive and sparsely represented in a dictionary of waveforms. Piecing together the data fidelity and the prior terms, the solution to the inverse problem is cast as the minimization of a non-smooth convex functional. We establish the well-posedness of the optimization problem, characterize the corresponding minimizers, and solve it by means of primal and primal-dual proximal splitting algorithms originating from the field of non-smooth convex optimization theory. Experimental results on deconvolution and comparison to prior methods are also reported.

Following the Compressed Sensing (CS) paradigm, this paper studies the problem of recovering sparse or compressible signals from (scalar) non-uniformly quantized measurements. We show that a simple adaptation of the Basis Pursuit De-Quantizer introduced earlier, that is, a sign sensitive weighting of their ℓp-norm fidelity constraint, yields good SNR improvements in the signal reconstruction. As a good indication of this improvement origin, we prove theoretically that a similar decoder, using a particular side-position-to-level oracle, displays a reduction of the reconstruction error when both the number of measurements and the moment p of the constraint increase. This follows the oversampling principle underlined in our previous study for uniformly quantized CS, with an additional gain provided by the non-uniform quantization. We conclude this paper by showing the efficiency of the approach on 1-D and 2-D signal examples.

We propose a new framework to extract the activity-related component in the BOLD functional magnetic resonance imaging (fMRI) signal. As opposed to traditional fMRI signal analysis techniques, we do not impose any prior knowledge of the event timing. Instead, our basic assumption is that the activation pattern is a sequence of short and sparsely distributed stimuli, as is the case in slow event-related fMRI. We introduce new wavelet bases, termed “activelets”, which sparsify the activity-related BOLD signal. These wavelets mimic the behavior of the differential operator underlying the hemodynamic system. To recover the sparse representation, we deploy a sparse-solution search algorithm. The feasibility of the method is evaluated using both synthetic and experimental fMRI data. The importance of the activelet basis and the non-linear sparse recovery algorithm is demonstrated by comparison against classical B-spline wavelets and linear regularization, respectively.

This article proposes a new algorithm to compute the projection on the set of images whose total variation is bounded by a constant. The projection is computed through a dual formulation that is solved by first order non-smooth optimization methods. This yields an iterative algorithm that applies iterative soft thresholding to the dual vector field, and for which we establish convergence rate on the primal iterates. This projection algorithm can then be used as a building block in a variety of applications such as solving inverse problems under a total variation constraint, or for texture synthesis. Numerical results are reported to illustrate the usefulness and potential applicability of our TV projection algorithm on various examples including denoising, texture synthesis, inpainting, deconvolution and tomography problems. We also show that our projection algorithm competes favorably with state-of-the-art TV projection methods in terms of convergence speed.

In this paper, we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. We present a new class of convex optimization programs, or decoders, coined Basis Pursuit DeQuantizer of moment p (BPDQp), that model the quantization distortion more faithfully than the commonly used Basis Pursuit DeNoise (BPDN) program. Our decoders proceed by minimizing the sparsity of the signal to be reconstructed subject to a data-fidelity constraint expressed in the ℓp-norm of the residual error for 2 ≤ p ≤ ∞. We show theoretically that, (i) the reconstruction error of these new decoders is bounded if the sensing matrix satisfies an extended Restricted Isometry Property involving the Iρ norm, and (ii), for Gaussian random matrices and uniformly quantized measurements, BPDQpperformance exceeds that of BPDN by dividing the reconstruction error due to quantization by √(p + 1). This last effect happens with high probability when the number of measurements exceeds a value growing with p, i.e., in an oversampled situation compared to what is commonly required by BPDN = BPDQ2. To demonstrate the theoretical power of BPDQp, we report numerical simulations on signal and image reconstruction problems.

This paper gives essential insights into the use of sparsity and morphological diversity in image decomposition and source separation by reviewing our recent work in this field. The idea to morphologically decompose a signal into its building blocks is an important problem in signal processing and has far-reaching applications in science and technology. Starck , proposed a novel decomposition method-morphological component analysis (MCA)-based on sparse representation of signals. MCA assumes that each (monochannel) signal is the linear mixture of several layers, the so-called morphological components, that are morphologically distinct, e.g., sines and bumps. The success of this method relies on two tenets: sparsity and morphological diversity. That is, each morphological component is sparsely represented in a specific transform domain, and the latter is highly inefficient in representing the other content in the mixture. Once such transforms are identified, MCA is an iterative thresholding algorithm that is capable of decoupling the signal content. Sparsity and morphological diversity have also been used as a novel and effective source of diversity for blind source separation (BSS), hence extending the MCA to multichannel data. Building on these ingredients, we will provide an overview the generalized MCA introduced by the authors in and as a fast and efficient BSS method. We will illustrate the application of these algorithms on several real examples. We conclude our tour by briefly describing our software toolboxes made available for download on the Internet for sparse signal and image decomposition and separation.

This article proposes a new method for image separation into a linear combination of morphological components. Sparsity in fixed dictionaries is used to extract the cartoon and oscillating content of the image. Complicated texture patterns are extracted by learning adapted local dictionaries that sparsify patches in the image. These fixed and learned sparsity priors define a nonconvex energy, and the separation is obtained as a stationary point of this energy. This variational optimization is extended to solve more general inverse problems such as inpainting. A new adaptive morphological component analysis algorithm is derived to find a stationary point of the energy. Using adapted dictionaries learned from data allows one to circumvent some difficulties faced by fixed dictionaries. Numerical results demonstrate that this adaptivity is indeed crucial in capturing complex texture patterns.

Recently morphological diversity and sparsity have emerged as new and effective sources of diversity for blind source separation. Based on these new concepts, novel methods such as generalized morphological component analysis have been put forward. The latter takes advantage of the very sparse representation of structured data in large overcomplete dictionaries, to separate sources based on their morphology. Building on GMCA, the purpose of this contribution is to describe a new algorithm for hyperspectral data processing. Large-scale hyperspectral data refers to collected data that exhibit sparse spectral signatures in addition to sparse spatial morphologies, in specified dictionaries of spectral and spatial waveforms. Numerical experiments are reported which demonstrate the validity of the proposed extension for solving source separation problems involving hyperspectral data.

This paper addresses the problem of mapping images between different vision sensors. Such a mapping could be modeled as a sampling problem that has to encompass the change of geometry between the two sensors and the specific discretization of the real scene observed by the two different imaging systems. We formulate the problem in a general framework that can be cast as a minimization regularized problem with a linear operator, that applies to any image geometry. We then focus on the particular problem of the generation of planar images from omnidirectional images, in any viewing direction and for any size and resolution. In this regularized approach, the fidelity term is expressed in the original omnicam geometry and the regularization is based on Total Variation (TV) solved here with proximal methods. Experimental results demonstrate the superiority of this approach with respect to alternative schemes based on linear interpolation or TV in-painting.

In this paper, we propose a fast image deconvolution algorithm that combines adaptive block thresholding and Vaguelet-Wavelet Decomposition. The approach consists in first denoising the observed image using a wavelet-domain Stein block thresholding, and then inverting the convolution operator in the Fourier domain. Our main theoretical result investigates the minimax rates over Besov smoothness spaces, and shows that our block estimator can achieve the optimal minimax rate, or is at least nearly-minimax in the least favorable situation. The resulting algorithm is simple to implement and fast. Its computational complexity is dominated by that of the FFT in the Fourier-domain inversion step. We report a simulation study to support our theoretical findings. The practical performance of our block vaguelet-wavelet deconvolution compares very favorably to existing competitors on a large set of test images.

This paper proposes a new class of algorithms to compute the projection onto the set of images with a total variation bounded by a constant. The projection is computed on a dual formulation of the problem that is minimized using either a one-step gradient descent method or a multi-step Nesterov scheme. This yields iterative algorithms that compute soft thresholding of the dual vector fields. We show the convergence of the method with a convergence rate of O(1/k) for the one step method and O(1/k2) for the multi-step one, where k is the iteration number. The projection algorithm can be used as a building block in several applications, and we illusrtate it by solving linear inverse problems under total variation constraint. Numerical results show that our algorithm competes favorably with state-of-the-art TV projection methods to solve denoising, inpainting and deblurring problems.

This work focuses on several optimization problems involved in recovery of sparse solutions of linear inverse problems. Such problems appear in many fields including image and signal processing, and have attracted even more interest since the emergence of the compressed sensing (CS) theory. In this paper, we formalize many of these optimization problems within a unified framework of convex optimization theory, and invoke tools from convex analysis and maximal monotone operator splitting. We characterize all these optimization problems, and to solve them, we propose fast iterative convergent algorithms using forward-backward and/or Peaceman/Douglas-Rachford splitting iterations. With non-differentiable sparsity-promoting penalties, the proposed algorithms are essentially based on iterative shrinkage. This makes them very competitive for large-scale problems. We also report some experiments on image reconstruction in CS to demonstrate the applicability of the proposed framework.

In this paper, following the Compressed Sensing (CS) paradigm, we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. We present a new class of convex optimization programs, or decoders, coined Basis Pursuit DeQuantizer of moment p (BPDQp), that model the quantization distortion more faithfully than the commonly used Basis Pursuit DeNoise (BPDN) program. Our decoders proceed by minimizing the sparsity of the signal to be reconstructed while enforcing a data fidelity term of bounded ¿p-norm, for 2pdecoders outperforms that of BPDN, with reconstruction error due to quantization divided by. This reduction relies on a modified Restricted Isometry Property of the sensing matrix expressed in the ¿p-norm (RIPp); a property satisfied by Gaussian random matrices with high probability. We conclude with numerical experiments comparing BPDQpand BPDN for signal and image reconstruction problems.

Sparsity constraints are now very popular to regularize inverse problems. We review several approaches which have been proposed in the last ten years to solve inverse problems such as inpainting, deconvolution or blind source separation. We will focus especially on optimization methods based on iterative thresholding methods to derive the solution.

Representing the image to be inpainted in an appropriate sparse representation dictionary, and combining elements from Bayesian statistics and modern harmonic analysis, we introduce an expectation maximization (EM) algorithm for image inpainting and interpolation. From a statistical point of view, the inpainting/interpolation can be viewed as an estimation problem with missing data. Toward this goal, we propose the idea of using the EM mechanism in a Bayesian framework, where a sparsity promoting prior penalty is imposed on the reconstructed coefficients. The EM framework gives a principled way to establish formally the idea that missing samples can be recovered/interpolated based on sparse representations. We first introduce an easy and efficient sparse-representation-based iterative algorithm for image inpainting. Additionally, we derive its theoretical convergence properties. Compared to its competitors, this algorithm allows a high degree of flexibility to recover different structural components in the image (piecewise smooth, curvilinear, texture, etc.). We also suggest some guidelines to automatically tune the regularization parameter.

We propose an image deconvolution algorithm when the data is contaminated by Poisson noise. The image to restore is assumed to be sparsely represented in a dictionary of waveforms such as the wavelet or curvelet transforms. Our key contributions are as follows. First, we handle the Poisson noise properly by using the Anscombe variance stabilizing transform leading to a nonlinear degradation equation with additive Gaussian noise. Second, the deconvolution problem is formulated as the minimization of a convex functional with a data-fidelity term reflecting the noise properties, and a nonsmooth sparsity-promoting penalty over the image representation coefficients (e.g., l(1) -norm). An additional term is also included in the functional to ensure positivity of the restored image. Third, a fast iterative forward-backward splitting algorithm is proposed to solve the minimization problem. We derive existence and uniqueness conditions of the solution, and establish convergence of the iterative algorithm. Finally, a GCV-based model selection procedure is proposed to objectively select the regularization parameter. Experimental results are carried out to show the striking benefits gained from taking into account the Poisson statistics of the noise. These results also suggest that using sparse-domain regularization may be tractable in many deconvolution applications with Poisson noise such as astronomy and microscopy.

We propose an image deconvolution algorithm when the data is contaminated by Poisson noise. The image to restore is assumed to be sparsely represented in a dictionary of waveforms such as the wavelet or curvelet transform. Our key innovations are: First, we handle the Poisson noise properly by using the Anscombe variance stabilizing transform leading to a non-linear degradation equation with additive Gaussian noise. Second, the deconvolution problem is formulated as the minimization of a convex functional with a data-fidelity term reflecting the noise properties, and a non-smooth sparsity-promoting penalties over the image representation coefficients (e.g. l1-norm). Third, a fast iterative backward-forward splitting algorithm is proposed to solve the minimization problem. We derive existence and uniqueness conditions of the solution, and establish convergence of the iterative algorithm. Experimental results are carried out to show the striking benefits gained from taking into account the Poisson statistics of the noise. These results also suggest that using sparse-domain regularization may be tractable in many deconvolution applications, e.g. astronomy or microscopy.

In this paper we propose a rigorous framework for texture image segmentation relying on region-based active contours (RBAC) and sparse texture representation. Such representations allow to efficiently describe a texture by transforming it in a dictionary of appropriate waveforms (atoms) where the texture representation coefficients are concentrated on a small set. For segmentation purposes. these atoms have to be multiscale and localized both in space and frequency, e.g. the wavelet transform. To discriminate different textures, we measure a ldquodistancerdquo between the non-parametric Parzen estimates of their respective sparse-representation coefficients probability density functions (pdfs). These distance measures are then used within RBAC, and we take benefit from shape derivative tools to derive the evolution speed expression of the RBAC. Our framework is applied to both supervised (with reference textures), and unsupervised texture segmentation. A series of experiments on synthetic textures illustrate the potential applicability of our method.

In order to denoise Poisson count data, we introduce a variance stabilizing transform (VST) applied on a filtered discrete Poisson process, yielding a near Gaussian process with asymptotic constant variance. This new transform, which can be deemed as an extension of the Anscombe transform to filtered data, is simple, fast, and efficient in (very) low-count situations. We combine this VST with the filter banks of wavelets, ridgelets and curvelets, leading to multiscale VSTs (MS-VSTs) and nonlinear decomposition schemes. By doing so, the noise-contaminated coefficients of these MS-VST-modified transforms are asymptotically normally distributed with known variances. A classical hypothesis-testing framework is adopted to detect the significant coefficients, and a sparsity-driven iterative scheme reconstructs properly the final estimate. A range of examples show the power of this MS-VST approach for recovering important structures of various morphologies in (very) low-count images. These results also demonstrate that the MS-VST approach is competitive relative to many existing denoising methods.

Overcomplete representations are attracting interest in image processing theory, particularly due to their potential to generate sparse representations of data based on their morphological diversity. We here consider a scenario of image denoising using an overcomplete dictionary of sparse linear transforms. Rather than using the basic approach where the denoised image is obtained by simple averaging of denoised estimates provided by each sparse transform, we here develop an elegant Bayesian framework to optimally combine the individual estimates. Our derivation of the optimally combined denoiser relies on a scale mixture of Gaussian (SMG) prior on the coefficients in each representation transform. Exploiting this prior, we design a Bayesian ℓ2-risk (mean field) nonlinear estimator and we derive a closed-form for its expression when the SMG specializes to the Bessel K form prior. Experimental results are carried out to show the striking profits gained from exploiting sparsity of data and their morphological diversity.

We address the problem of temporal tracking fine pointlike and filamentary structures exhibiting smooth motions in image sequences. By taking these specific restrictions into account, we put forward an original tracking method based on the search of integral lines in time-space structure tensor fields. The method is simple and very efficient regarding computation time and tracking precision, which allows a sub-pixel accuracy in both spatial and temporal domains. We suggest a numerical implementation of the algorithm which is based on a modified constrained Runge-Kutta scheme. Its performance and potential applicability are illustrated through two real cases : the tracking of internal linear features in composite materials observed with X-rays and the tracking of granular-shaped objects moving in a gas flow.

Fluorescence microscopy images are contaminated by photon and readout noises, and hence can be described by mixed-Poisson-Gaussian (MPG) processes. In this paper, a new variance stabilizing transform (VST) is designed to convert a filtered MPG process into a near Gaussian process with a constant variance. This VST is then combined with the isotropic undecimated wavelet transform leading to a multiscale VST (MS-VST). We demonstrate the usefulness of MS-VST for image denoising and spot detection in fluorescence microscopy. In the first case, we detect significant Gaussianized wavelet coefficients under the control of a false discovery rate. A sparsity-driven iterative scheme is proposed to properly reconstruct the final estimate. In the second case, we show that the MS-VST can also lead to a fluorescent-spot detector, where the false positive rate of the detection in pure noise can be controlled. Experiments show that the MS-VST approach outperforms the generalized Anscombe transform in denoising, and that the detection scheme allows efficient spot extraction from complex background.

Over the last few years, the development of multichannel sensors motivated interest in methods for the coherent processing of multivariate data. Some specific issues have already been addressed as testified by the wide literature on the so-caIled blind source separation (BSS) problem. In this context, as clearly emphasized by previous work, it is fundamental that the sources to be retrieved present some quantitatively measurable diversity. Recently, sparsity and morphological diversity have emergedas a novel and effective source of diversity for BSS. Here, we give some new and essential insights into the use of sparsity in source separation, and we outline the essential role of morphological diversity as being a source of diversity or contrast between the sources. This paper introduces a new BSS method coined generalized morphological component analysis (GMCA) that takes advantages of both morphological diversity and sparsity, using recent sparse overcomplete or redundant signal representations. GMCA is a fast and efficient BSS method. We present arguments and a discussion supporting the convergence of the GMCA algorithm. Numerical results in multivariate image and signal processing are given illustrating the good performance of GMCA and its robustness to noise.

In a recent paper, a method called morphological component analysis (MCA) has been proposed to separate the texture from the natural part in images. MCA relies on an iterative thresholding algorithm, using a threshold which decreases linearly towards zero along the iterations. This paper shows how the MCA convergence can be drastically improved using the mutual incoherence of the dictionaries associated to the different components. This modified MCA algorithm is then compared to basis pursuit, and experiments show that MCA and BP solutions are similar in terms of sparsity, as measured by the l1 norm, but MCA is much faster and gives us the possibility of handling large scale data sets.

This paper describes the undecimated wavelet transform and its reconstruction. In the first part, we show the relation between two well known undecimated wavelet transforms, the standard undecimated wavelet transform and the isotropic undecimated wavelet transform. Then we present new filter banks specially designed for undecimated wavelet decompositions which have some useful properties such as being robust to ringing artifacts which appear generally in wavelet-based denoising methods. A range of examples illustrates the results.

This paper introduces a complete pipeline of image processing methods in order to analyze and track the internal structures of a composite material. As a first step, input Xray images are denoised, enhanced, separated into different morphological components, and geometrically filtered in order to isolate the interesting fiber inside the composite material. This requires the design of specific algorithms preserving very thin image details while being able to remove undesired image regions that may be sometimes large. For this purpose, we use state-of the-art techniques based on recent achievements in diffusion PDE’s and modern harmonic analysis tools. Then, the shapes of the remaining fibered composite are individually analyzed by the use of a tensor-based tracking algorithm. We illustrate how this set of techniques allows the dynamic analysis of the composite structure when submitted to external mechanical loads.

In this paper, we focus on statistical region-based active contour models where image features (e.g. intensity) are random variables whose distribution belongs to some parametric family (e.g. exponential) rather than confining ourselves to the special Gaussian case. Using shape derivation tools, our effort focuses on constructing a general expression for the derivative of the energy (with respect to a domain) and derive the corresponding evolution speed. A general result is stated within the framework of multi-parameter exponential family. More particularly, when using maximum likelihood estimators, the evolution speed has a closed-form expression that depends simply on the probability density function, while complicating additive terms appear when using other estimators, e.g. moments method. Experimental results on both synthesized and real images demonstrate the applicability of our approach

We propose in this paper a multi-scale variance stabilizing transform (MSVST) for approximately Gaussianizing and stabilizing the variance of a sequence of independent Poisson random variables (RVs) filtered by a low-pass linear filter. This approach is shown to be fast, very well adapted to extremely low-count situations and easily applicable to any dimensional data. It is shown that the RV transformed using Anscombe VST can be reasonably considered as stabilized for an intensity lambda gsim 10, using Fisz VST for lambda gsim 1 and using our VST (after low-pass filtering) for lambda gsim 0.1. We then use the MSVST technique to stabilize the detail coefficients of the isotropic undecimated wavelet transform (IUWT) of multi-dimensional Poisson count data. We use a hypothesis testing framework in the wavelet domain to denoise the Gaussianized and stabilized coefficients, and then apply the inverse MSVST-IUWT to get the estimated intensity image underlying the Poisson data. Finally, potential applicability of our approach is illustrated on an astronomical example where isotropic structures must be recovered

In this paper, we propose to combine formally noise and shape priors in region-based active contours. On the one hand, we use the general framework of exponential family as a prior model for noise. On the other hand, translation and scale invariant Legendre moments are considered to incorporate the shape prior (e.g. fidelity to a reference shape). The combination of the two prior terms in the active contour functional yields the final evolution equation whose evolution speed is rigorously derived using shape derivative tools. Experimental results on both synthetic images and real life cardiac echography data clearly demonstrate the robustness to initialization and noise, flexibility and large potential applicability of our segmentation algorithm.

In this paper, a nonparametric Bayesian estimator in the wavelet domain using the Bessel K form (BKF) distribution will be presented. Our first contribution is to show how the BKF prior is suited to characterize images belonging to Besov spaces. Exploiting this prior, our second contribution is to design a Bayesian L/sub 1/-loss maximum a posteriori estimator nonlinear denoiser, for which we formally establish the mathematical properties. Finally, a comparative study is carried to show the effectiveness of our Bayesian denoiser compared to other denoising approaches.

We introduce an expectation-maximization (EM) algorithm for image inpainting based on a penalized likelihood formulated using linear sparse representations. Taking advantage of the sparsity of representations, a regularization through a prior penalty is imposed on the reconstructed coefficients. From a statistical point of view, the inpainting can be viewed as an estimation problem with missing data. The EM framework is a general iterative algorithm for ML estimation in such situations. The EM framework gives a principled way to establish formally the idea that missing samples can be recovered based on sparse representations. Furthermore, owing to its well known theoretical properties, the EM algorithm allows to investigate the convergence behavior of the inpainting algorithm.

A novel Bayesian nonparametric estimator in the Wavelet domain is presented. In this approach, a prior model is imposed on the wavelet coefficients designed to capture the sparseness of the wavelet expansion. Seeking probability models for the marginal densities of the wavelet coefficients, the new family of Bessel K forms (BKF) densities are shown to fit very well to the observed histograms. Exploiting this prior, we designed a Bayesian nonlinear denoiser and we derived a closed form for its expression. We then compared it to other priors that have been introduced in the literature, such as the generalized Gaussian density (GGD) or the alpha-stable models, where no analytical form is available for the corresponding Bayesian denoisers. Specifically, the BKF model turns out to be a good compromise between these two extreme cases (hyperbolic tails for the alpha-stable and exponential tails for the GGD). Moreover, we demonstrate a high degree of match between observed and estimated prior densities using the BKF model. Finally, a comparative study is carried out to show the effectiveness of our denoiser which clearly outperforms the classical shrinkage or thresholding wavelet-based techniques.

Many practical applications in the field of medical image processing require robust and valid 3D image segmentation results. In this paper, we present a semi-automatic iterative segmentation approach for 3D medical image by combining a 2D boundary tracking algorithm and a boundary mapping process. Upon each of the consecutive slice, the boundary tracking process is accomplished in an alternate procedure of the morphological dilatation and the multi-label front propagation. The multi-label front propagation method is developed based on the minimal path theory and fast sweeping evolution method to ensure the efficiency, and speed of the boundary tracking algorithm. This 3D image segmentation approach can easily extract the close and smooth boundary of the desired object from a 2D medical image series. This approach is efficient and reliable, and requires very limited user intervention. Some experimental results are also presented to demonstrate the efficiency of this approach.

Functional magnetic resonance imaging (fMRI) time series generally demonstrate serial dependence. This endogenous auto-correlation typically exhibits long-range dependence described by a 1/f-like power law. We present a novel wavelet-based methodology for characterising the noise structure in short-medium length (shortish) fMRI time series. Mono-fractality is assessed in terms of the Hurst exponent and the noise variance. We then investigate potential local stationarity of the Hurst exponent in MM data and present a uniformly most powerful test for its time constancy. A novel bootstrap approach is presented as an alternative to the normal assumption and its advantages are discussed. From several datasets investigated, we specifically show that the 1/f model is particularly suited to describe color in MM nose. We also demonstrate that even if most of the brain voxels are mono-fractal, there are many locations in the brain where time constancy of the Hurst exponent is violated, ie, the noise structure is poly-fractal.

We present a fuzzy Markovian method for brain tissue segmentation from magnetic resonance images. Generally, there are three principal brain tissues in a brain dataset: gray matter, white matter and cerebrospinal fluid. However, due to the limited resolution of the acquisition system, many voxels may be composed of multiple tissue types (partial volume effects). The proposed method aims to calculate the fuzzy membership of each voxel to indicate the partial volume degree using a fuzz, Markovian segmentation. Since our method is unsupervised, it first estimates the fuzzy Markovian random field model parameters using a stochastic gradient algorithm. The efficiency of the proposed method is quantified on a digital phantom using an absolute average error, and qualitatively tested on real MRI brain data.

This paper presents an unsupervised segmentation method applied to classify brain tissues in 3D for magnetic resonance (MR) images. An MR image volume may be composed of a mixture of several tissue types due to partial volume effects. The statistical model of the mixtures is proposed and studied by means of simulations. It is shown that it can be approximated by a Gaussian function under some conditions. The D'Agostino-Pearson normality test is used to calculate the risk /spl alpha/ of the approximation. In order to classify a brain into three brain tissues and deal with the problem of partial volume effects, the proposed algorithm classifies firstly the brain into pure classes and mix-classes, it then re-classifies the mix-classes into pure classes by adding the knowledge about the topology of the brain, based on the multifractal dimension. Both steps use Markov random field models. The algorithm is evaluated using both simulated images and real MR images.

We address the problem of automatically segmenting cell nuclei or cluster of cell nuclei in image medical microscopy. We present a system of automatic segmentation combining fuzzy clustering and multiple active contour models. An automatic initialization algorithm based on fuzzy clustering is used to robustly identify and classify all possible seed regions in the image. These seeds are propagated outward simultaneously to localize the final contours of all objects. We present examples of quantitative segmentation on biomedical images: segmentation of lobules in color images of histology and segmentation of nuclei in cytological images.

This paper presents a fully automatic three-dimensional classification of brain tissues for Magnetic Resonance (MR) images. An MR image volume may be composed of a mixture of several tissue types due to partial volume effects. Therefore, we consider that in a brain dataset there are not only the three main types of brain tissue: gray matter, white matter, and cerebro spinal fluid, called pure classes, but also mixtures, called mixclasses. A statistical model of the mixtures is proposed and studied by means of simulations. It is shown that it can be approximated by a Gaussian function under some conditions. The D'Agostino-Pearson normality test is used to assess the risk alpha of the approximation. In order to classify a brain into three types of brain tissue and deal with the problem of partial volume effects, the proposed algorithm uses two steps: 1) segmentation of the brain into pure and mixclasses using the mixture model; 2) reclassification of the mixclasses into the pure classes using knowledge about the obtained pure classes. Both steps use Markov random field (MRF) models. The multifractal dimension, describing the topology of the brain, is added to the MRFs to improve discrimination of the mixclasses. The algorithm is evaluated using both simulated images and real MR images with different T1-weighted acquisition sequences.