Abstract
In convex optimization, duality theory can sometimes lead to simpler solution methods than those resulting from direct primal analysis. In this paper, this principle is applied to a class of composite variational problems arising in particular in signal recovery. These problems are not easily amenable to solution by current methods but they feature Fenchel–Moreau–Rockafellar dual problems that can be solved by forward-backward splitting. The proposed algorithm produces simultaneously a sequence converging weakly to a dual solution, and a sequence converging strongly to the primal solution. Our framework is shown to capture and extend several existing duality-based signal recovery methods and to be applicable to a variety of new problems beyond their scope.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Amar, M., Bellettini, G.: A notion of total variation depending on a metric with discontinuous coefficients. Ann. Inst. Henri Poincaré, Anal. Non Linéaire 11, 91–133 (1994)
Andrews, H.C., Hunt, B.R.: Digital Image Restoration. Prentice-Hall, Englewood Cliffs (1977)
Aubert, G., Kornprobst, P.: Mathematical Problems in Image Processing, 2nd edn. Springer, New York (2006)
Aubin, J.-P. Frankowska, H.: Set-Valued Analysis. Birkhäuser, Boston (1990)
Bauschke, H.H., Combettes, P.L.: A Dykstra-like algorithm for two monotone operators. Pacific J. Optim. 4, 383–391 (2008)
Bauschke, H.H., Combettes, P.L.: The Baillon–Haddad theorem revisited. J. Convex Anal. 17 (2010)
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2, 183–202 (2009)
Bect, J., Blanc-Féraud, L., Aubert, G., Chambolle, A.: A ℓ1 unified variational framework for image restoration. In: Pajdla, T., Matas, J. (eds.) Proc. Eighth Europ. Conf. Comput. Vision, Prague. Lecture Notes in Computer Science, vol. 3024, pp. 1–13. Springer, New York (2004)
Ben-Tal, A., Borwein, J.M., Teboulle, M.: A dual approach to multidimensional L p spectral estimation problems. SIAM J. Control Optim. 26, 985–996 (1988)
Bertero, M., De Mol, C., Pike, E.R.: Linear inverse problems with discrete data I—general formulation and singular system analysis. Inverse Probl. 1, 301–330 (1985)
Bioucas-Dias, J.M., Figueiredo, M.A.: A new TwIST: Two-step iterative shrinkage/thresholding algorithms for image restoration. IEEE Trans. Image Process 16, 2992–3004 (2007)
Borwein, J.M., Lewis, A.S., Noll, D.: Maximum entropy reconstruction using derivative information. I: Fisher information and convex duality. Math. Oper. Res. 21, 442–468 (1996)
Borwein, J.M., Luke, D.R.: Duality and convex programming. In: Scherzer, O. (ed.) Handbook of Imaging. Springer, New York (to appear)
Bredies, K. Lorenz, D.A.: Linear convergence of iterative soft-thresholding. J. Fourier Anal. Appl. 14, 813–837 (2008)
Briceño-Arias, L.M., Combettes, P.L.: Convex variational formulation with smooth coupling for multicomponent signal decomposition and recovery. Numer. Math. Theory Methods Appl. 2, 485–508 (2009)
Byrne, C.L.: Signal Processing—A Mathematical Approach. A. K. Peters, Wellesley (2005)
Cai, J.-F. Chan, R.H., Shen, L., Shen, Z.: Convergence analysis of tight framelet approach for missing data recovery. Adv. Comput. Math. 31, 87–113 (2009)
Cai, J.-F., Chan, R.H., Shen, Z.: A framelet-based image inpainting algorithm. Appl. Comput. Harmon. Anal. 24, 131–149 (2008)
Censor, Y., Elfving, T.: A multiprojection algorithm using Bregman projections in a product space. Numer. Algorithms 8, 221–239 (1994)
Censor, Y., Zenios, S.A.: Parallel Optimization: Theory, Algorithms and Applications. Oxford University Press, New York (1997)
Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20, 89–97 (2004)
Chambolle, A.: Total variation minimization and a class of binary MRF model. Lect. Notes Comput. Sci. 3757, 136–152 (2005)
Chan, T.F., Golub, G.H., Mulet, P.: A nonlinear primal-dual method for total variation-based image restoration. SIAM J. Sci. Comput. 20, 1964–1977 (1999)
Chaux, C., Combettes, P.L., Pesquet, J.-C., Wajs, V.R.: A variational formulation for frame-based inverse problems. Inverse Probl. 23, 1495–1518 (2007)
Chaux, C., Pesquet, J.-C., Pustelnik, N.: Nested iterative algorithms for convex contrained image recovery problems,. SIAM J. Imag. Sci. 2, 730–762 (2009)
Combettes, P.L.: Signal recovery by best feasible approximation. IEEE Trans. Image Process. 2, 269–271 (1993)
Combettes, P.L.: Inconsistent signal feasibility problems: Least-squares solutions in a product space. IEEE Trans. Signal Process. 42, 2955–2966 (1994)
Combettes, P.L.: The convex feasibility problem in image recovery. In: Hawkes, P. (ed.) Advances in Imaging and Electron Physics, vol. 95, pp. 155–270. Academic, New York (1996)
Combettes, P.L., Dũng, Đ., Vũ, B.C.: Dualization of signal recovery problems. Preprint, 2 July 2009. http://arxiv.org/abs/0907.0436
Combettes, P.L., Pesquet, J.-C.: Proximal thresholding algorithm for minimization over orthonormal bases. SIAM J. Optim. 18, 1351–1376 (2007)
Combettes, P.L., Pesquet, J.-C.: A Douglas–Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE Selected J. Topics Signal Process. 1, 564–574 (2007)
Combettes, P.L., Trussell, H.J.: The use of noise properties in set theoretic estimation. IEEE Trans. Signal Process. 39, 1630–1641 (1991)
Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4, 1168–1200 (2005)
Daubechies, I.: Ten Lectures on Wavelets. SIAM, Philadelphia (1992)
Daubechies, I., Defrise, M., De Mol, C.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57, 1413–1457 (2004)
Daubechies, I., Teschke, G., Vese, L.: Iteratively solving linear inverse problems under general convex constraints. Inverse Probl. Imaging 1, 29–46 (2007)
Destuynder, P., Jaoua, M., Sellami, H.: A dual algorithm for denoising and preserving edges in image processing. J. Inverse Ill-Posed Probl. Ser. 15, 149–165 (2007)
Donoho, D., Johnstone, I.: Ideal spatial adaptation via wavelet shrinkage. Biometrika 81, 425–455 (1994)
Durand, S., Nikolova, M.: Denoising of frame coefficients using ℓ1 data-fidelity term and edge-preserving regularization. Multiscale Model. Simul. 6, 547–576 (2007)
Ekeland, I., Temam, R.: Analyse Convexe et Problèmes Variationnels, Dunod, Paris, 1974; Convex Analysis and Variational Problems. SIAM, Philadelphia (1999)
Fadili, J., Peyré, G.: Total variation projection with first order schemes. Preprint (2009). http://hal.archives-ouvertes.fr/hal-00380491
Fenchel, W.: Convex Cones, Sets and Functions. Lecture Notes (mimeograph). Princeton University (1953)
Fornasier, M.: Domain decomposition methods for linear inverse problems with sparsity constraints. Inverse Probl. 23, 2505–2526 (2007)
Gerchberg, R.W.: Super-resolution through error energy reduction. Opt. Acta 21, 709–720 (1974)
Hintermüller, M., Stadler, G.: An infeasible primal-dual algorithm for total bounded variation-based inf-convolution-type image restoration. SIAM J. Sci. Comput. 28, 1–23 (2006)
Huang, Y., Ng, M.K., Wen, Y.-W.: A fast total variation minimization method for image restoration. Multiscale Model. Simul. 7, 774–795 (2008)
Iusem, A.N., Teboulle, M.: A regularized dual-based iterative method for a class of image reconstruction problems. Inverse Probl. 9, 679–696 (1993)
Kärkkäinen, T., Majava, K., Mäkelä, M.M.: Comparison of formulations and solution methods for image restoration problems. Inverse Probl. 17, 1977–1995 (2001)
Leahy, R.M., Goutis, C.E.: An optimal technique for constraint-based image restoration and reconstruction. IEEE Trans. Acoust. Speech Signal Process. 34, 1629–1642 (1986)
Levi, L.: Fitting a bandlimited signal to given points. IEEE Trans. Inf. Theory 11, 372–376 (1965)
Mallat, S.G.: A Wavelet Tour of Signal Processing, 2nd edn. Academic, New York (1999)
Medoff, B.P.: Image reconstruction from limited data: theory and applications in computerized tomography. In: Stark, H. (ed.) Image Recovery: Theory and Application, pp. 321–368. Academic, San Diego (1987)
Mercier, B.: Inéquations Variationnelles de la Mécanique (Publications Mathématiques d’Orsay, no. 80.01). Orsay, France, Université de Paris-XI (1980)
Moreau, J.-J.: Fonctions convexes duales et points proximaux dans un espace hilbertien. C.R. Acad Sci. Paris Sér. A Math. 255, 2897–2899 (1962)
Moreau, J.-J.: Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. Fr. 93, 273-299 (1965)
Moreau, J.-J.: Fonctionnelles Convexes. Séminaire sur les Équations aux Dérivées Partielles II. Collège de France, Paris (1966–1967)
Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)
Nesterov, Yu.: Smooth minimization of non-smooth functions. Math. Program. 103, 127–152 (2005)
Noll, D.: Reconstruction with noisy data: An approach via eigenvalue optimization. SIAM J. Optim. 8, 82–104 (1998)
Papoulis, A.: A new algorithm in spectral analysis and band-limited extrapolation. IEEE Trans. Circuits Syst. 22, 735–742 (1975)
Polak, E.: Computational Methods in Optimization: A Unified Approach. Academic, New York (1971)
Potter, L.C., Arun, K.S.: A dual approach to linear inverse problems with convex constraints. SIAM J. Control Optim. 31, 1080–1092 (1993)
Rockafellar, R.T.: Duality and stability in extremum problems involving convex functions. Pac. Math. J. 21, 167–187 (1967)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Rockafellar, R.T.: Conjugate Duality and Optimization. SIAM, Philadelphia (1974)
Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992)
Stark, H. (Ed.): Image Recovery: Theory and Application. Academic, San Diego (1987)
Steinhardt, A.O., Goodrich, R.K., Roberts, R.A.: Spectral estimation via minimum energy correlation extension. IEEE Trans. Acoust. Speech Signal Process. 33, 1509–1515 (1985)
Tropp, J.A.: Just relax: Convex programming methods for identifying sparse signals in noise. IEEE Trans. Inf. Theory 52, 1030–1051 (2006)
Trussell, H.J., Civanlar, M.R.: The feasible solution in signal restoration. IEEE Trans. Acoust. Speech Signal Process. 32, 201–212 (1984)
Twomey, S.: The application of numerical filtering to the solution of integral equations encountered in indirect sensing measurements. J. Franklin Inst. 279, 95–109 (1965)
van den Berg, E., Friedlander, M.P.: Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31, 890–912 (2008)
Weaver, J.B., Xu, Y., Healy, D.M., Jr., Cromwell, L.D.: Filtering noise from images with wavelet transforms. Magn. Reson. Med. 21, 288–295 (1991)
Weiss, P., Aubert, G., Blanc-Féraud, L.: Efficient schemes for total variation minimization under constraints in image processing. SIAM J. Sci. Comput. 31, 2047–2080 (2009)
Youla, D.C.: Generalized image restoration by the method of alternating orthogonal projections. IEEE Trans. Circuits Syst. 25, 694–702 (1978)
Youla, D.C., Velasco, V.: Extensions of a result on the synthesis of signals in the presence of inconsistent constraints. IEEE Trans. Circuits Syst. 33, 465–468 (1986)
Youla, D.C., Webb, H.: Image restoration by the method of convex projections: Part 1—theory. IEEE Trans. Med. Imag. 1, 81–94 (1982)
Zălinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, River Edge (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of P. L. Combettes was supported the Agence Nationale de la Recherche under grant ANR-08-BLAN-0294-02. The work of Đ. Dũng and B. C. Vũ was supported by the Vietnam National Foundation for Science and Technology Development.
Rights and permissions
About this article
Cite this article
Combettes, P.L., Dũng, Đ. & Vũ, B.C. Dualization of Signal Recovery Problems. Set-Valued Anal 18, 373–404 (2010). https://doi.org/10.1007/s11228-010-0147-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11228-010-0147-7
Keywords
- Convex optimization
- Denoising
- Dictionary
- Dykstra-like algorithm
- Duality
- Forward-backward splitting
- Image reconstruction
- Image restoration
- Inverse problem
- Signal recovery
- Primal-dual algorithm
- Proximity operator
- Total variation