Abstract. We propose stochastic splitting algorithms for solving large-scale composite inclusion problems involving monotone and linear operators. They activate at each iteration blocks of randomly selected resolvents of monotone operators and, unlike existing methods, achieve almost sure convergence of the iterates to a solution without any regularity assumptions or knowledge of the norms of the linear operators. Applications to image recovery and machine learning are provided.

Neural networks have become ubiquitous tools for solving signal and image processing problems, and they often outperform standard approaches. Nevertheless, training the layers of a neural network is a challenging task in many applications. The prevalent training procedure consists of minimizing highly non-convex objectives based on data sets of huge dimension. In this context, current methodologies are not guaranteed to produce global solutions. We present an alternative approach which foregoes the optimization framework and adopts a variational inequality formalism. The associated algorithm guarantees convergence of the iterates to a true solution of the variational inequality and it possesses an efficient block-iterative structure. A numerical application is presented.

Under consideration are multicomponent minimization problems involving a separable nonsmooth convex function penalizing the components individually, and nonsmooth convex coupling terms penalizing linear mixtures of the components. We investigate the application of block-activated proximal algorithms for solving such problems, i.e., algorithms which, at each iteration, need to use only a block of the underlying functions, as opposed to all of them as in standard methods. For smooth coupling functions, several block-activated algorithms exist and they are well understood. By contrast, in the fully nonsmooth case, few block-activated methods are available and little effort has been devoted to assessing them. Our goal is to shed more light on the implementation, the features, and the behavior of these algorithms, compare their merits, and provide machine learning and image recovery experiments illustrating their performance.

We show that many nonlinear observation models in signal recovery can be represented using firmly nonexpansive operators. To address problems with inaccurate measurements, we propose solving a variational inequality relaxation which is guaranteed to possess solutions under mild conditions and which coincides with the original problem if it happens to be consistent. We then present an efficient algorithm for its solution, as well as numerical applications in signal and image recovery, including an experimental operator-theoretic method of promoting sparsity.

Building up on classical linear formulations, we posit that a broad class of problems in signal synthesis and in signal recovery are reducible to the basic task of finding a point in a closed convex subset of a Hilbert space that satisfies a number of nonlinear equations involving firmly nonexpansive operators. We investigate this formalism in the case when, due to inaccurate modeling or perturbations, the nonlinear equations are inconsistent. A relaxed formulation of the original problem is proposed in the form of a variational inequality. The properties of the relaxed problem are investigated, and a provenly convergent block-iterative algorithm, whereby only blocks of the underlying firmly nonexpansive operators are activated at a given iteration, is devised to solve it. Numerical experiments illustrate robust recoveries in several signal and image processing applications.

Structured convex optimization problems typically involve a mix of smooth and nonsmooth functions. The common practice is to activate the smooth functions via their gradient and the nonsmooth ones via their proximity operator. We show that although intuitively natural, this approach is not necessarily the most efficient numerically and that, in particular, activating all the functions proximally may be advantageous. To make this viewpoint viable computationally, we derive a number of new examples of proximity operators of smooth convex functions arising in applications. A novel variational model to relax inconsistent convex feasibility problems is also investigated within the proposed framework. Several numerical applications to image recovery are presented to compare the behavior of fully proximal versus mixed proximal/gradient implementations of several splitting algorithms.

A wide array of image recovery problems can be abstracted into the problem of minimizing a sum of composite convex functions in a Hilbert space. To solve such problems, primal-dual proximal approaches have been developed which provide efficient solutions to large-scale optimization problems. The objective of this paper is to show that a number of existing algorithms can be derived from a general form of the forward-backward algorithm applied in a suitable product space. Our approach also allows us to develop useful extensions of existing algorithms by introducing a variable metric. An illustration to image restoration is provided.

We consider a variational formulation of blind image recovery problems. A novel iterative proximal algorithm is proposed to solve the associated nonconvex minimization problem. Under suitable assumptions, this algorithm is shown to have better convergence properties than standard alternating minimization techniques. The objective function includes a smooth convex data fidelity term and nonsmooth convex regularization terms modeling prior information on the data and on the unknown linear degradation operator. A novelty of our approach is to bring into play recent nonsmooth analysis results. The pertinence of the proposed method is illustrated in an image restoration example.

We propose a variational method for decomposing an image into a geometry and a texture component. Our model involves the sum of two functions promoting separately properties of each component, and of a coupling function modeling the interaction between the components. None of these functions is required to be differentiable, which significantly broadens the range of decompositions achievable through variational approaches. The convergence of the proposed proximal algorithm is guaranteed under suitable assumptions. Numerical examples are provided that show an application of the algorithm to image decomposition and restoration in the presence of Poisson noise.

A broad range of signal recovery problems can be abstracted into the problem of minimizing the sum of several convex functions in a Hilbert space. We propose a proximal decomposition algorithm which, under mild conditions, provides a solution to such a problem. A significant improvement over the methods currently in use in the area of signal recovery is that it is not limited to two nondifferentiable functions. An application to image restoration is demonstrated.

Under consideration is the large body of signal recovery problems that can be formulated as the problem of minimizing the sum of two (not necessarily smooth) proper lower semicontinuous convex functions in a real Hilbert space. This generic problem is analyzed and a decomposition method is proposed to solve it. The convergence of the method, which is based on an extension of the Douglas-Rachford algorithm for monotone operators splitting, is established under general conditions. Various signal recovery applications are discussed and numerical results are provided

Improvements in electromagnetic sources, detectors, optical components, and computational imaging have made it possible to achieve three-dimensional atomic-scale resolution using tomographic phase-contrast imaging techniques. These greater capabilities have placed a premium on improving the efficiency and stability of phase retrieval algorithms for recovering the missing phase information in diffraction observations. In some cases, so called direct methods suffice, but, for large macromolecules and nonperiodic structures, one must rely on numerical techniques for reconstructing the missing phase. This is the principal motivation of our work. We report on recent progress in algorithms for iterative phase retrieval. The theory of convex optimisation is used to develop and to gain insight into counterparts for the nonconvex problem of phase retrieval. We propose a relaxation of averaged alternating reflectors and determine the fundamental mathematical properties of the related operator in the convex case. Numerical studies support our theoretical observations and demonstrate the effectiveness of the newer generation of algorithms compared to the current state of the art.

Convex set theoretic estimation methods have been shown to be effective in numerous signal recovery problems due to their ability to incorporate a wide range of deterministic and probabilistic information in the form of constraints on the solution. To date, probabilistic information has been used exclusively to constrain statistics of the estimation residual to be consistent with known properties of the noise. In this paper, we propose a new technique to construct constraint sets from probabilistic information based on Stein's identity. In this framework, probabilistic attributes of the signal to be recovered are estimated from the data. The proposed approach is applicable to signal formation models involving additive Gaussian noise and it leads to geometrically simple sets that can easily be handled via projection methods. An application to image denoising is demonstrated.

First-order finite-difference information has been exploited in a variety of image and signal restoration settings. These approaches typically require - implicitly or explicitly - that certain attributes of the finite-difference images be known a priori. We propose a new statistical framework in which such attributes are estimated a posteriori from the observed data under the assumption that the noise is additive and Gaussian. Our analysis can be directly applied to the construction of property sets in set theoretic estimation methods. The proposed framework is illustrated through an application to image denoising.

Regularization techniques have been in use in signal recovery for over four decades. In this paper, we propose a new synthetic approach to the study of regularization methods in image denoising problems based on Moreau's proximity operators. We exploit the remarkable properties enjoyed by these operators to establish in a systematic fashion a variety of properties of regularized denoising problems and to propose new numerical schemes to solve them.

Total variation has proven to be a valuable concept in connection with the recovery of images featuring piecewise smooth components. So far, however, it has been used exclusively as an objective to be minimized under constraints. In this paper, we propose an alternative formulation in which total variation is used as a constraint in a general convex programming framework. This approach places no limitation on the incorporation of additional constraints in the restoration process and the resulting optimization problem can be solved efficiently via block-iterative methods. Image denoising and deconvolution applications are demonstrated.

Total variation has proven to be a valuable concept in connection with the recovery of images featuring piecewise smooth components. So far, however, it has been used exclusively as an objective to be minimized under a single constraint. In this paper, we propose an alternative framework in which total variation is used as a constraint in a general quadratic programming context. The advantage of this approach is that it allows for a wider range of constraints to be easily incorporated in the recovery process.

The state of the art for solving the phase retrieval problem in two dimensions relies heavily on the algorithms proposed by Gerchbercy, Saxton, and Fienup. Despite the widespread use of these algorithms, current mathematical theory cannot explain their remarkable success. It is already known that the Gerchberg-Saxton algorithm is a nonconvex version of method of alternating projections. In this paper, we show that two other prominent phase retrieval methods also have well known counterparts in the world of convex optimization algorithms: Fienup's basic input-output algorithm corresponds to Dykstra's algorithm, and Fienup's hybrid input-output algorithm can be viewed as an instance of the Douglas-Rachford algorithm. This work provides a theoretical framework to better understand and, potentially, improve existing phase recovery algorithms.

The formulation of a wide variety of image recovery problems leads to the minimization of a convex objective over a convex set representing the constraints derived from a priori knowledge and consistency with the observed signals. In previous years, nondifferentiable objectives have become popular due in part to their ability to capture certain features such as sharp edges. They also arise naturally in minimax inconsistent set theoretic recovery problems. At the same time, the issue of developing reliable numerical algorithms to solve such convex programs in the context of image recovery applications has received little attention. We address this issue and propose an adaptive level set method for nondifferentiable constrained image recovery. The asymptotic properties of the method are analyzed and its implementation is discussed. Numerical experiments illustrate applications to total variation and minimax set theoretic image restoration and denoising problems.

In image recovery, convex projection methods have been in use for almost two decades. However, while it is well known that projections can seldom be computed exactly, the effect of inexact projections on the behavior of such methods has not yet been investigated. We propose such an analysis and establish conditions on the projection errors under which the theoretical convergence properties of various algorithms remain valid. Our analysis covers sequential, parallel, and block-iterative (subgradient) projection methods for consistent and inconsistent set theoretic image recovery problems. It is shown in particular that parallel projection methods are more robust to errors than sequential methods such as the popular POCS (projection on to convex sets) algorithm.

The parallel projection method (PPM) uses successive averages of projections onto constraint sets to construct a signal that least violates these constraints in an average squared-distance sense. In this paper, we study the robustness of PPM to errors in the computation of the projections. It is shown that the convergence properties of PPM remain valid under a simple summability condition on the relaxed averages of the errors.

A block-iterative parallel decomposition method is proposed to solve general quadratic signal recovery problems under convex constraints. Unlike existing schemes, the proposed method proceeds by local linearizations of blocks of constraints and it is therefore not sensitive to their analytical complexity. Implementation-related issues are discussed and an application to signal deconvolution is demonstrated.

An new adaptive level-set subgradient projection algorithm is proposed to solve non-differentiable signal recovery problems with multiple convex constraints. The algorithm is described, its convergence is established, and its implementation is discussed. Applications to constrained total variation signal restoration and denoising are demonstrated.

We propose a block-iterative parallel decomposition method to solve quadratic signal recovery problems under convex constraints. The idea, of the method is to disintegrate the original multi-constraint problem into a sequence of simple quadratic minimizations over the intersection of two half-spaces constructed by linearizing blocks of constraints. The implementation of the algorithm is quite flexible thanks to its block-parallel structure. In addition a wide range of complex constraints can be incorporated since the method does not require exact constraint enforcement at each step but merely approximate enforcement via linearization. An application to deconvolution is demonstrated.

A standard wavelet multiresolution analysis can be defined via a sequence of projectors onto a monotone sequence of closed vector subspaces possessing certain properties. We propose a nonlinear extension of this framework in which the vector subspaces are replaced by convex subsets. These sets are chosen so as to provide a recursive, monotone approximation scheme that allows for various image features to be investigated. Several classes of convex multiresolution analyzes are discussed and numerical applications to image analysis are demonstrated.

A standard wavelet multiresolution analysis can be defined via a sequence of projectors onto a monotone sequence of closed vector subspaces possessing certain properties. We propose a nonlinear extension of this framework in which the vector subspaces are replaced by convex subsets. These sets are chosen so as to provide a recursive, monotone approximation scheme that allows for various signal and image features to be investigated. Several classes of convex multiresolution analyses are discussed and numerical applications to signal and image-processing problems are demonstrated.

We consider the problem of synthesizing feasible signals in the presence of inconsistent convex constraints, some of which are hard in the sense that they must absolutely be satisfied. This problem is formalized as that of minimizing an objective function measuring the degree of unfeasibility with respect to the soft constraints over the intersection of the sets associated with the hard constraints. We first investigate the process of aggregating soft constraints in order to define relevant objectives and then address the question of solving the resulting convex programs. Finally, we provide numerical results to illustrate the benefits of our analysis.

Solving a convex set theoretic image recovery problem amounts to finding a point in the intersection of closed and convex sets in a Hilbert space. The projection onto convex sets (POCS) algorithm, in which an initial estimate is sequentially projected onto the individual sets according to a periodic schedule, has been the most prevalent tool to solve such problems. Nonetheless, POCS has several shortcomings: it converges slowly, it is ill suited for implementation on parallel processors, and it requires the computation of exact projections at each iteration. We propose a general parallel projection method (EMOPSP) that overcomes these shortcomings. At each iteration of EMOPSP, a convex combination of subgradient projections onto some of the sets is formed and the update is obtained via relaxation. The relaxation parameter may vary over an iteration-dependent, extrapolated range that extends beyond the interval [0,2] used in conventional projection methods. EMOPSP not only generalizes existing projection-based schemes, but it also converges very efficiently thanks to its extrapolated relaxations. Theoretical convergence results are presented as well as numerical simulations.

A general formalism for iterative image coding is introduced. In this framework, each feature of the image to be coded is associated with a nonexpansive operator which leaves invariant all images possessing the feature in question. The decoding scheme consists of finding a common fixed point of these operators, which can be achieved via efficient parallel algorithms. The proposed formalism provides a flexible treatment of the image coding problem and contains as special cases transform coding, fractal coding, set theoretic coding, and vector quantization.

In set theoretic image recovery, the constraints which do not yield convex sets in the chosen Hilbert solution space cannot be enforced. In some cases, however, such constraints may yield convex sets in other Hilbert spaces. We introduce a generalized product space formalism, through which constraints that are convex in different Hilbert spaces can be combined. A nonconvex problem with several sets is reduced to a convex problem with two sets in the product space, where it is solved via an alternating projection method. Applications are discussed.

Statistical information has been used extensively to define feasible solutions in set theoretic signal processing. However, the reliability of the set theoretic estimates resulting from the combination of multiple statistical constraints has thus far not been investigated. We address this question in order to provide a basis for a better use of statistical information in set theoretic estimation problems.

We address the problem of linear mean-square estimation with arbitrary convex constraints for dependent processes. Two algorithms are proposed and their convergence is established. The first algorithm, which is deterministic, covers the case of known correlation structures; the second, which is stochastic and adaptive, covers the case of unknown correlation structures. Since existing algorithms can handle at most one simple constraint this contribution is relevant to signal processing problems in which arbitrary convex inequality constraints are present.

In image recovery a priori knowledge and the observed data give rise to constraints on the solutions. In general, the recovery problem can be posed as that of minimizing a pertinent cost function over the resulting feasibility set. In this paper we present a product space framework for solving such problems, which leads to simplified formulations and to efficient parallel algorithms. Feasibility problems, quadratic minimization problems, and convex minimization problems are discussed.

A new projection algorithm for convex set theoretic image recovery [reconstruction and restoration] is presented. This algorithm comprises all serial and parallel projection methods as particular cases and is straightforwardly implementable on concurrent processors. It proceeds by taking convex combinations of selected projections at each iteration and allows extrapolated relaxations far beyond the range [0,2] used in conventional algorithms. These extrapolated, iteration-dependent relaxations result in very fast convergence. Numerical results are provided which show that the proposed algorithm outperforms existing ones, in particular the popular cyclic method of projections onto convex sets [POCS].>

Solving a convex set theoretic image recovery problem amounts to finding a point in the intersection of closed and convex sets in a Hilbert space. Methods employing projections onto the individual sets to build a sequence converging to a point in their intersection have proven most useful to obtain set theoretic solutions. They are nonetheless sometimes difficult to implement because of the theoretical or numerical tedium associated with the computation of projections at each iteration. We propose a general parallel iterative method which processes chaotically approximate projections instead of exact ones. Weak and strong convergence results are presented and subgradient projection methods are discussed as a particular case. >

Explains set theoretic estimation, which is governed by the notion of feasibility and produces solutions whose sole property is to be consistent with all information arising from the observed data and a priori knowledge. Each piece of information is associated with a set in the solution space, and the intersection of these sets, the feasibility set, represents the acceptable solutions. The practical use of the set theoretic framework stems from the existence of efficient techniques for finding these solutions. Many scattered problems in systems science and signal processing have been approached in set theoretic terms over the past three decades. The author synthesizes a single, general framework from these various approaches, examines its fundamental philosophy, goals, and analytical techniques, and relates it to conventional methods.>

The objective of set theoretical signal recovery is to find a feasible signal in the form of a point in the intersection of S of sets modeling the information available about the problem. For problems in which the true signal is known to lie near a reference signal r, the solution should not be any feasible point but one which best approximates r, i.e., a projection of r onto S. Such a solution cannot be obtained by the feasibility algorithms currently in use, e.g., the method of projections onto convex sets (POCS) and its offsprings. Methods for projecting a point onto the intersection of closed and convex sets in a Hilbert space are introduced and applied to signal recovery by best feasible approximation of a reference signal. These algorithms are closely related to the above projection methods, to which they add little computational complexity.

In digital signal processing, the two main sources of uncertainty encountered in estimation problems are model uncertainty and noise. In many instances, probabilistic information is available to partially describe these sources of uncertainty. It is shown how such information can be exploited in a broad class of set theoretic estimation problems relevant to digital signal processing. A general framework is developed to construct sets in the solution space by constraining the estimation residual based on the known component of the model to be consistent with those known properties of a so-called uncertainty process consisting of the contribution of the unknown component of the model and the noise. Specific digital signal processing applications are discussed.>

Many scattered estimation problems in systems science and signal processing have been approached in set theoretic terms over the past three decades. A single formal framework is presented to synthesize these various approaches, and the fundamental philosophy, goals, and analytical techniques of set theoretic estimation are discussed.>

Two methods for the synthesis of set theoretic estimates are presented. The first is a generalization of the method of successive projections onto closed and convex subsets of Hilbert spaces to approximately compact subsets of metric spaces. The second is based on a stochastic search in the solution space. These methods allow greater flexibility with regard to the incorporation of prior knowledge, thereby extending the scope of set theoretic estimation. Applications to digital signal processing problems are discussed.>

A description is given of how information pertaining to an arbitrary absolute moment of the noise process can be used in a general set-theoretic estimation framework. It is shown that for each such piece of a priori information, a set can be constructed in the solution space by constraining the corresponding sample statistics of the estimation residual to lie within some acceptable distance from the expected value. The geometrical and topological properties of these sets are investigated. The benefits of the simultaneous use of several such sets with regard to the synthesis of better set-theoretic estimates are discussed. Applications to signal restoration/reconstruction, speech prediction, spectral estimation, and radar signal processing are discussed.>

The authors investigate the application of set-theoretic estimation methods to the design of linear-predictive-coding (LPC) digital filters. The constraints involved in the design are represented by sets in an abstract space. Any member of their intersection satisfies all the design specifications and is called feasible. Two sets are considered: the set of stable filters and the set of filters which minimize the mean-square prediction error in an environment where the statistics of the observed data are unknown. These two sets are described analytically and the problem of obtaining a feasible LPC filter is addressed. Experimental results are also presented.>

This paper presents a technique for restoring images which have been degraded by a stochastic point spread function (psf). In the past, the restoration of such images has been approached in terms of averages without considering the variations of the psf. It will be shown that the integration of the additional uncertainties caused by the stochastic psf can be used to obtain better estimates. These uncertainties can be included to the restoration scheme in a very flexible manner through the use of the Projection Onto Convex Sets (POCS) method. Finally, the benefits of the method will be illustrated through simulations.