American Institute of Mathematical Sciences

February  2008, 2(1): 133-149. doi: 10.3934/ipi.2008.2.133

Analytical bounds on the minimizers of (nonconvex) regularized least-squares

 1 CMLA, ENS Cachan, CNRS, PRES UniverSud, 61 Av. President Wilson, F-94230 Cachan

Received  April 2007 Published  January 2008

This is a theoretical study on the minimizers of cost-functions composed of an l 2 data-fidelity term and a possibly nonsmooth or nonconvex regularization term acting on the differences or the discrete gradients of the image or the signal to restore. More precisely, we derive general nonasymptotic analytical bounds characterizing the local and the global minimizers of these cost-functions. We first derive bounds that compare the restored data with the noisy data. For edge-preserving regularization, we exhibit a tight data-independent bound on the l norm of the residual (the estimate of the noise), even if its l 2 norm is being minimized. Then we focus on the smoothing incurred by the (local) minimizers in terms of the differences or the discrete gradient of the restored image (or signal).
Citation: Mila Nikolova. Analytical bounds on the minimizers of (nonconvex) regularized least-squares. Inverse Problems & Imaging, 2008, 2 (1) : 133-149. doi: 10.3934/ipi.2008.2.133
 [1] C. M. Elliott, B. Gawron, S. Maier-Paape, E. S. Van Vleck. Discrete dynamics for convex and non-convex smoothing functionals in PDE based image restoration. Communications on Pure & Applied Analysis, 2006, 5 (1) : 181-200. doi: 10.3934/cpaa.2006.5.181 [2] Nurullah Yilmaz, Ahmet Sahiner. On a new smoothing technique for non-smooth, non-convex optimization. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2020004 [3] Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems & Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171 [4] Bartomeu Coll, Joan Duran, Catalina Sbert. Half-linear regularization for nonconvex image restoration models. Inverse Problems & Imaging, 2015, 9 (2) : 337-370. doi: 10.3934/ipi.2015.9.337 [5] Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2020013 [6] Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237 [7] Amir Averbuch, Pekka Neittaanmäki, Valery Zheludev. Periodic spline-based frames for image restoration. Inverse Problems & Imaging, 2015, 9 (3) : 661-707. doi: 10.3934/ipi.2015.9.661 [8] Nicolas Lermé, François Malgouyres, Dominique Hamoir, Emmanuelle Thouin. Bayesian image restoration for mosaic active imaging. Inverse Problems & Imaging, 2014, 8 (3) : 733-760. doi: 10.3934/ipi.2014.8.733 [9] Jing Xu, Xue-Cheng Tai, Li-Lian Wang. A two-level domain decomposition method for image restoration. Inverse Problems & Imaging, 2010, 4 (3) : 523-545. doi: 10.3934/ipi.2010.4.523 [10] Xiaoman Liu, Jijun Liu. Image restoration from noisy incomplete frequency data by alternative iteration scheme. Inverse Problems & Imaging, 2020, 14 (4) : 583-606. doi: 10.3934/ipi.2020027 [11] Tong Li, Jeungeun Park. Stability of traveling waves of models for image processing with non-convex nonlinearity. Communications on Pure & Applied Analysis, 2018, 17 (3) : 959-985. doi: 10.3934/cpaa.2018047 [12] Salvatore A. Marano, Sunra Mosconi. Non-smooth critical point theory on closed convex sets. Communications on Pure & Applied Analysis, 2014, 13 (3) : 1187-1202. doi: 10.3934/cpaa.2014.13.1187 [13] Rafail Krichevskii and Vladimir Potapov. Compression and restoration of square integrable functions. Electronic Research Announcements, 1996, 2: 42-49. [14] Gabriel Peyré, Sébastien Bougleux, Laurent Cohen. Non-local regularization of inverse problems. Inverse Problems & Imaging, 2011, 5 (2) : 511-530. doi: 10.3934/ipi.2011.5.511 [15] Moulay Rchid Sidi Ammi, Ismail Jamiai. Finite difference and Legendre spectral method for a time-fractional diffusion-convection equation for image restoration. Discrete & Continuous Dynamical Systems - S, 2018, 11 (1) : 103-117. doi: 10.3934/dcdss.2018007 [16] Petteri Harjulehto, Peter Hästö, Juha Tiirola. Point-wise behavior of the Geman--McClure and the Hebert--Leahy image restoration models. Inverse Problems & Imaging, 2015, 9 (3) : 835-851. doi: 10.3934/ipi.2015.9.835 [17] Jia Li, Zuowei Shen, Rujie Yin, Xiaoqun Zhang. A reweighted $l^2$ method for image restoration with Poisson and mixed Poisson-Gaussian noise. Inverse Problems & Imaging, 2015, 9 (3) : 875-894. doi: 10.3934/ipi.2015.9.875 [18] Hongwei Lou, Junjie Wen, Yashan Xu. Time optimal control problems for some non-smooth systems. Mathematical Control & Related Fields, 2014, 4 (3) : 289-314. doi: 10.3934/mcrf.2014.4.289 [19] Deepak Singh, Bilal Ahmad Dar, Do Sang Kim. Sufficiency and duality in non-smooth interval valued programming problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 647-665. doi: 10.3934/jimo.2018063 [20] Paul Glendinning. Non-smooth pitchfork bifurcations. Discrete & Continuous Dynamical Systems - B, 2004, 4 (2) : 457-464. doi: 10.3934/dcdsb.2004.4.457

2018 Impact Factor: 1.469