A Douglas–Rachford Splitting Approach to Nonsmooth Convex Variational Signal Recovery
IEEE Journal of Selected Topics in Signal ProcessingPublished 1 December 2007
Patrick L. Combettes, Jean‐Christophe Pesquet
Citations494
SJR quartileQ1
SJR score4.12
SNIP3.79
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A decomposition method based on the Douglas-Rachford algorithm for monotone operator-splitting for signal recovery problems and applications to non-Gaussian image denoising in a tight frame are demonstrated.
Abstract
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) 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 the Douglas-Rachford algorithm for monotone operator-splitting, is obtained under general conditions. Applications to non-Gaussian image denoising in a tight frame are also demonstrated.
Keywords
Computer ScienceEngineering
Computers in PhysicsTen Lectures on Wavelets
15,386 Citations1992Ingrid Daubechies, Christopher Heil
This paper presents a meta-analyses of the wavelet transforms of Coxeter’s inequality and its applications to multiresolutional analysis and orthonormal bases.
Springer series in computational mathematicsMatrix Iterative Analysis
5,787 Citations2000Richard S. Varga
Communications on Pure and Applied MathematicsAn iterative thresholding algorithm for linear inverse problems with a sparsity constraint
4,957 Citations2004Ingrid Daubechies, Michel Defrise +1 more
It is proved that replacing the usual quadratic regularizing penalties by weighted 𝓁p‐penalized penalties on the coefficients of such expansions, with 1 ≤ p ≤ 2, still regularizes the problem.
IEEE Transactions on Image ProcessingThe contourlet transform: an efficient directional multiresolution image representation
3,930 Citations2005N. Minh, Martin Vetterli
Mathematical ProgrammingOn the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators
2,877 Citations1992Jonathan Eckstein, Dimitri P. Bertsekas
This paper shows, by means of an operator called asplitting operator, that the Douglas—Rachford splitting method for finding a zero of the sum of two monotone operators is a special case of the proximal point algorithm, which allows the unification and generalization of a variety of convex programming algorithms.
Multiscale Modeling and SimulationSignal Recovery by Proximal Forward-Backward Splitting
2,599 Citations2005Patrick L. Combettes, Valérie R. Wajs
It is shown that various inverse problems in signal recovery can be formulated as the generic problem of minimizing the sum of two convex functions with certain regularity properties, which makes it possible to derive existence, uniqueness, characterization, and stability results in a unified and standardized fashion for a large class of apparently disparate problems.
SIAM Journal on Numerical AnalysisSplitting Algorithms for the Sum of Two Nonlinear Operators
1,975 Citations1979Pierre‐Louis Lions, Bertrand Mercier
This work studies two splitting algorithms for (stationary and evolution) problems involving the sum of two monotone operators with real-time requirements.
SIAM ReviewOn Projection Algorithms for Solving Convex Feasibility Problems
1,711 Citations1996Heinz H. Bauschke, Jonathan M. Borwein
A very broad and flexible framework is investigated which allows a systematic discussion of questions on behaviour in general Hilbert spaces and on the quality of convergence in convex feasibility problems.
IEEE Signal Processing MagazineDigital image restoration
1,669 Citations1997M.R. Banham, Aggelos K. Katsaggelos
The article introduces digital image restoration to the reader who is just beginning in this field, and provides a review and analysis for the readers who may already be well-versed in image restoration.
Transactions of the American Mathematical SocietyOn the numerical solution of heat conduction problems in two and three space variables
1,657 Citations1956Jim Douglas, H.H. Rachford
WORLD SCIENTIFIC eBooksConvex Analysis in General Vector Spaces
1,483 Citations2002Constantin Zălinescu
Bulletin de la Société mathématique de FranceProximité et dualité dans un espace hilbertien
1,386 Citations1965Jean Jacques Moreau
IEEE Transactions on Medical ImagingImage Restoration by the Method of Convex Projections: Part 1ߞTheory
1,021 Citations1982Dante C. Youla, H. Webb
This paper exploits the properties of projection operators Pi onto a closed convex set in Hilbert space to develop several iterative algorithms for image restoration from partial data which permit any number of nonlinear constraints of a certain type to be subsumed automatically.
Nonlinear Functional Analysis and its Applications
813 Citations1985Eberhard Zeidler
Physics in Medicine and BiologyA unified approach for inversion problems in intensity-modulated radiation therapy
804 Citations2006Yair Censor, Thomas Bortfeld +2 more
A unified model for handling dose constraints and radiation source constraints in a single mathematical framework based on the split feasibility problem is proposed and computational results demonstrate the validity of the model and the power of the proposed algorithmic scheme.
Proceedings of the IEEEThe foundations of set theoretic estimation
635 Citations1993Patrick L. Combettes
Best Approximation in Inner Product Spaces
590 Citations2001Frank Deutsch
Memoirs of the American Mathematical SocietyFrames, bases and group representations
537 Citations2000Deguang Han, David R. Larson
HAL (Le Centre pour la Communication Scientifique Directe)Fonctions convexes duales et points proximaux dans un espace hilbertien
517 Citations1962Jean Jacques Moreau
Advances in imaging and electron physicsThe Convex Feasibility Problem in Image Recovery
482 Citations1996Patrick L. Combettes
OptimizationSolving monotone inclusions via compositions of nonexpansive averaged operators
481 Citations2004Patrick L. Combettes
IEEE Transactions on Signal ProcessingTime-invariant orthonormal wavelet representations
407 Citations1996Jean‐Christophe Pesquet, Hamid Krim +1 more
This work addresses the time-invariance problem for orthonormal wavelet transforms and proposes an extension to wavelet packet decompositions to achieve time invariance and preserve the orthonormality.
IEEE Transactions on Circuits and SystemsGeneralized Image Restoration by the Method of Alternating Orthogonal Projections
391 Citations1978Dante C. Youla
This work adopts a view that suggests that many problems of image restoration are probably geometric in character and admits the following initial linear formulation: the original f is a vector known a priori to belong to a linear subspace {\cal P}_b of a parent Hilbert space {\cal H}( , but all that is available to the observer is its image P_{a} f, the projection of f onto a known linear sub Space P_a (also in \cal H ).
The Annals of StatisticsRecovering edges in ill-posed inverse problems: optimality of curvelet frames
327 Citations2002Emmanuel J. Candès, David L. Donoho
It is proved that the curvelet shrinkage can be tuned so that the estimator will attain, within logarithmic factors, the MSE $O(\varepsilon^{4/5})$ as noise level $\varePSilon\to 0$.
IEEE Transactions on Information TheoryWhy Simple Shrinkage Is Still Relevant for Redundant Representations?
284 Citations2006Michael Elad
This work develops a simple iterative procedure for the BPDN minimization that amounts to stepwise shrinkage, and demonstrates how the simple shrinkage emerges as the first iteration of this novel algorithm.
Medical Entomology and ZoologyVector Space Projections : A Numerical Approach to Signal and Image Processing, Neural Nets, and Optics
272 Citations1998Henry Stark, Yongi Yang +1 more
This self-contained volume provides a tutorial on projection methods and how to apply them in science and engineering, and details effective problem-solving strategies, and explores key applications in communication and signal processing, neural networks and pattern recognition, and optics and image processing.
IEEE Transactions on Image ProcessingSuper-resolution reconstruction of hyperspectral images
265 Citations2005Toygar Akgün, Y. Altunbasak +1 more
A novel super-resolution method for hyperspectral images that fuses information from multiple observations and spectral bands to improve spatial resolution and reconstruct the spectrum of the observed scene as a combination of a small number of spectral basis functions.
Optima and Equilibria: An Introduction to Nonlinear Analysis
235 Citations1993Jean Aubin
Inverse ProblemsA variational formulation for frame-based inverse problems
235 Citations2007Caroline Chaux, Patrick L. Combettes +2 more
A splitting algorithm is presented to solve this problem and its convergence is established in infinite-dimensional spaces under mild conditions on the penalization functions, which need not be differentiable.
Journal of Approximation TheoryFinding best approximation pairs relative to two closed convex sets in Hilbert spaces
210 Citations2004Heinz H. Bauschke, Patrick L. Combettes +1 more
This work investigates systematically the asymptotic behavior of AAR in the general case when the sets do not necessarily intersect and shows that the method produces best approximation pairs provided they exist.
IEEE Transactions on Signal ProcessingInconsistent signal feasibility problems: least-squares solutions in a product space
197 Citations1994Patrick L. Combettes
Presents parallel projection methods to find least-squares solutions to inconsistent convex set theoretic signal synthesis problems and convergence properties of the proposed methods are analyzed and signal synthesis applications are demonstrated.
IEEE Transactions on Image ProcessingImage Restoration Subject to a Total Variation Constraint
194 Citations2004Patrick L. Combettes, Jean‐Christophe Pesquet
An alternative formulation in which total variation is used as a constraint in a general convex programming framework is proposed, which 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.
IEEE Transactions on Image ProcessingConvex set theoretic image recovery by extrapolated iterations of parallel subgradient projections
193 Citations1997Patrick L. Combettes
SIAM Journal on OptimizationProximal Thresholding Algorithm for Minimization over Orthonormal Bases
186 Citations2007Patrick L. Combettes, Jean‐Christophe Pesquet
This work proposes a versatile convex variational formulation for optimization over orthonormal bases that covers a wide range of problems, and establishes the strong convergence of a proximal thresholding algorithm to solve it.
IEEE Transactions on Image ProcessingBayesian wavelet-based image deconvolution: a GEM algorithm exploiting a class of heavy-tailed priors
173 Citations2006José M. Bioucas‐Dias
A new generalized expectation maximization (GEM) algorithm, where the missing variables are the scale factors of the GSM densities, and the maximization step of the underlying expectation maximizations algorithm is replaced with a linear stationary second-order iterative method.
Numerical Functional Analysis and OptimizationIteration methods for convexly constrained ill-posed problems in hilbert space
160 Citations1992Bertolt Eicke
Applied Mathematics & OptimizationHilbertian convex feasibility problem: Convergence of projection methods
150 Citations1997Patrick L. Combettes
Magnetic Resonance in MedicinePOCSENSE: POCS‐based reconstruction for sensitivity encoded magnetic resonance imaging
149 Citations2004Alexey Samsonov, Eugene Kholmovski +2 more
POCSENSE is conceptually simple and numerically efficient and can reconstruct images from data sampled on arbitrary k‐space trajectories and was demonstrated using a wide range of simulated and real MRI data.
IEEE Transactions on Signal ProcessingAn efficient robust adaptive filtering algorithm based on parallel subgradient projection techniques
136 Citations2002Isao Yamada, Konstantinos Slavakis +1 more
A novel robust adaptive filtering scheme based on the interactive use of statistical noise information and the ideas developed originally for efficient algorithmic solutions to the convex feasibility problems is presented.
IEEE Transactions on Image ProcessingImage analysis using a dual-tree M-band wavelet transform
134 Citations2006Caroline Chaux, Laurent Duval +1 more
A two-dimensional generalization to the M-band case of the dual-tree decomposition structure based on a Hilbert pair of wavelets, which minimizes potential estimation errors and significant improvements in terms of both overall noise reduction and direction preservation are observed.
Numerical AlgorithmsExtrapolation algorithm for affine-convex feasibility problems
84 Citations2005Heinz H. Bauschke, Patrick L. Combettes +1 more
A general parallel block-iterative algorithmic framework in which the affine subspaces are exploited to introduce extrapolated over-relaxations is proposed, which encompasses a wide range of projection, subgradient projection, proximal, and fixed point methods encountered in various branches of applied mathematics.
International Statistical ReviewA Comparative Simulation Study of Wavelet Shrinkage Estimators for Poisson Counts
78 Citations2004Panagiotis Besbeas, Italia De Feis +1 more
Statistica NeerlandicaWavelet thresholding for some classes of non–Gaussian noise
73 Citations2002Anestis Antoniadis, D. Leporini +1 more
This paper proposes a framework in which the notion of sparseness can be naturally expressed by a Bayesian model for the wavelet coefficients of the underlying signal and establishes close connections between wavelet thresholding techniques and Maximum A Posteriori estimation for two classes of noise distributions including heavy–tailed noises.
IEEE Transactions on Image ProcessingAn adaptive level set method for nondifferentiable constrained image recovery
68 Citations2002Patrick L. Combettes, Ji‐An Luo
This work proposes an adaptive level set method for nondifferentiable constrained image recovery and analyzes the asymptotic properties of the method.
IEEE Transactions on Circuits and SystemsExtensions of a result on the synthesis of signals in the presence of inconsistent constraints
54 Citations1986Dante C. Youla, Víctor Lanz Gutiérrez De Velasco
Considerations of symmetry have led to a formulation which identifies "minimizers" as "nodes" on closed "greedy" paths and an important and potentially useful property of such paths is proven in Theorem 4.
Choice Reviews OnlineTime-frequency representations
50 Citations1998
This chapter discusses Zak transform, a Fourier transform of periodic functions of W-H systems, and its applications to biorthogonals, and some examples of groups.
IEEE Transactions on Signal ProcessingPairwise Optimal Weight Realization—Acceleration Technique for Set-Theoretic Adaptive Parallel Subgradient Projection Algorithm
44 Citations2006Masahiro Yukawa, Isao Yamada
A novel weighting technique named pairwise optimal weight realization (POWER) for further acceleration of the adaptive PSP algorithm and yields significantly faster convergence than not only adaptive PSP with uniform weights, affine projection algorithm, and fast Newton transversal filters but also the regularized recursive least squares algorithm.
Journal of Computational and Graphical StatisticsAutomatic Smoothing With Wavelets for a Wide Class of Distributions
42 Citations2004Sylvain Sardy, Anestis Antoniadis +1 more
This work considers a unifying l1-penalized likelihood approach to regularize the maximum likelihood estimation by adding an l1 penalty of the wavelet coefficients to give an explicit formula for the universal smoothing parameter to denoise Poisson measurements.
Inverse ProblemsOn some Bayesian choices of regularization parameter in image restoration
25 Citations1993Adam Thompson, Jim Kay
This paper examines the hyperparametric method of selecting the regularization parameter described in Gull and shows how Gull's results may be generalised to situations where the log-prior may be approximated by a positive semi-definite quadratic form.
IEEE Transactions on Image ProcessingFast image recovery using dynamic load balancing in parallel architectures, by means of incomplete projections
7 Citations2001Francisco J. González‐Castaño, Ubaldo M. García‐Palomares +2 more
This paper formulates an incomplete projection algorithm that is applied to the image recovery problem and results compare favorably with those obtained by the extrapolated method of parallel subgradient projections.
Pattern Recognition LettersA hybrid parallel projection approach to object-based image restoration
4 Citations2006Xin Fan, Hua Huang +2 more
This paper proposes a hybrid approach to object-based image restoration that incorporates common characteristics of images from a class of objects into image restoration as deterministic sets built on principal component analysis (PCA) models.