×

Risk estimators for choosing regularization parameters in ill-posed problems – properties and limitations. (English) Zbl 06945044

Summary: This paper discusses the properties of certain risk estimators that recently regained popularity for choosing regularization parameters in ill-posed problems, in particular for sparsity regularization. They apply Stein’s unbiased risk estimator (SURE) to estimate the risk in either the space of the unknown variables or in the data space. We will call the latter PSURE in order to distinguish the two different risk functions. It seems intuitive that SURE is more appropriate for ill-posed problems, since the properties in the data space do not tell much about the quality of the reconstruction. We provide theoretical studies of both approaches for linear Tikhonov regularization in a finite dimensional setting and estimate the quality of the risk estimators, which also leads to asymptotic convergence results as the dimension of the problem tends to infinity. Unlike previous works which studied single realizations of image processing problems with a very low degree of ill-posedness, we are interested in the statistical behaviour of the risk estimators for increasing ill-posedness. Interestingly, our theoretical results indicate that the quality of the SURE risk can deteriorate asymptotically for ill-posed problems, which is confirmed by an extensive numerical study. The latter shows that in many cases the SURE estimator leads to extremely small regularization parameters, which obviously cannot stabilize the reconstruction. Similar but less severe issues with respect to robustness also appear for the PSURE estimator, which in comparison to the rather conservative discrepancy principle leads to the conclusion that regularization parameter choice based on unbiased risk estimation is not a reliable procedure for ill-posed problems. A similar numerical study for sparsity regularization demonstrates that the same issue appears in non-linear variational regularization approaches.

MSC:

65F22 Ill-posedness and regularization problems in numerical linear algebra
62F12 Asymptotic properties of parametric estimators
49N45 Inverse problems in optimal control

References:

[1] R. J. Adler and J. E. Taylor, Random Fields and Geometry, Springer Monographs in Mathematics, Springer, New York, 2007. · Zbl 1149.60003
[2] M. S. C. Almeida; M. A. T. Figueiredo, Parameter estimation for blind and non-blind deblurring using residual whiteness measures, IEEE Transactions on Image Processing, 22, 2751-2763 (2013) · Zbl 1373.94018 · doi:10.1109/TIP.2013.2257810
[3] F. Bauer; T. Hohage, A Lepskij-type stopping rule for regularized Newton methods, Inverse Problems, 21, 1975-1991 (2005) · Zbl 1091.65052 · doi:10.1088/0266-5611/21/6/011
[4] G. Blanchard and P. Mathé, Discrepancy principle for statistical inverse problems with application to conjugate gradient iteration Inverse Problems, 28 (2012), 115011, 23pp. · Zbl 1284.47051
[5] P. Blomgren; T. F. Chan, Modular solvers for image restoration problems using the discrepancy principle, Numerical Linear Algebra with Applications, 9, 347-358 (2002) · Zbl 1071.68557 · doi:10.1002/nla.278
[6] S. Boyd; N. Parikh; E. Chu; B. Peleato; J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3, 1-122 (2011) · Zbl 1229.90122 · doi:10.1561/2200000016
[7] B. Bringmann, D. Cremers, F. Krahmer and M. Möller, The homotopy method revisited: Computing solution paths of \(\begin{document}\ell_1\end{document} \)-regularized problems, Math. Comp., 87 (2018), 2343-2364, arXiv: 1605.00071. · Zbl 1391.49072
[8] M. Burger, A. Sawatzky and G. Steidl, First order algorithms in variational image processing, Splitting Methods in Communication, Imaging, Science, and Engineering, 345-407, Sci. Comput., Springer, Cham, 2016. · Zbl 1372.65053
[9] E. J. Candes; C. A. Sing-Long; J. D. Trzasko, Unbiased risk estimates for singular value thresholding and spectral estimators, IEEE Transactions on Signal Processing, 61, 4643-4657 (2013) · Zbl 1393.94187 · doi:10.1109/TSP.2013.2270464
[10] E. Chernousova; Y. Golubev, Spectral cut-off regularizations for ill-posed linear models, Math. Methods Statist., 23, 116-131 (2014) · Zbl 1308.62016 · doi:10.3103/S1066530714020033
[11] C. Deledalle; S. Vaiter; J. Fadili; G. Peyré, Stein Unbiased GrAdient estimator of the Risk (SUGAR) for Multiple Parameter Selection, SIAM Journal on Imaging Sciences, 7, 2448-2487 (2014) · Zbl 1361.94012 · doi:10.1137/140968045
[12] C. Deledalle, S. Vaiter, G. Peyré, J. Fadili and C. Dossal, Proximal splitting derivatives for risk estimation, Journal of Physics: Conference Series, 386 (2012), 012003.
[13] C. Deledalle, S. Vaiter, G. Peyré, J. Fadili and C. Dossal, Unbiased risk estimation for sparse analysis regularization, in 2012 19th IEEE International Conference on Image Processing, IEEE, 2012, 3053-3056.
[14] C. Dossal; M. Kachour; J. Fadili; G. Peyré; C. Chesneau, The degrees of freedom of the lasso for general design matrix, Statistica Sinica, 23, 809-828 (2013) · Zbl 1433.62193
[15] Y. C. Eldar, Generalized SURE for Exponential Families: Applications to Regularization, IEEE Transactions on Signal Processing, 57, 471-481 (2009) · Zbl 1391.62131 · doi:10.1109/TSP.2008.2008212
[16] H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, vol. 375, Springer Science & Business Media, 1996. · Zbl 0859.65054
[17] N. P. Galatsanos; A. K. Katsaggelos, Methods for choosing the regularization parameter and estimating the noise variance in image restoration and their relation, Trans. Img. Proc., 1, 322-336 (1992) · doi:10.1109/83.148606
[18] S. K. Ghoreishi; M. R. Meshkani, On SURE estimates in hierarchical models assuming heteroscedasticity for both levels of a two-level normal hierarchical model, Journal of Multivariate Analysis, 132, 129-137 (2014) · Zbl 1360.62397 · doi:10.1016/j.jmva.2014.08.001
[19] R. Giryes; M. Elad; Y. Eldar, The projected GSURE for automatic parameter tuning in iterative shrinkage methods, Applied and Computational Harmonic Analysis, 30, 407-422 (2011) · Zbl 1210.94015 · doi:10.1016/j.acha.2010.11.005
[20] J. Hadamard, Lectures on Cauchy’s Problem in Linear Partial Differential Equations, New Haven, 1953.
[21] H. Haghshenas Lari; A. Gholami, Curvelet-TV regularized Bregman iteration for seismic random noise attenuation, Journal of Applied Geophysics, 109, 233-241 (2014) · doi:10.1016/j.jappgeo.2014.08.005
[22] P. C. Hansen, Analysis of discrete ill-posed problems by means of the L-curve, SIAM Review, 34, 561-580 (1992) · Zbl 0770.65026 · doi:10.1137/1034115
[23] P. C. Hansen; D. P. OLeary, The Use of the L-Curve in the Regularization of Discrete Ill-Posed Problems, SIAM Journal on Scientific Computing, 14, 1487-1503 (1993) · Zbl 0789.65030 · doi:10.1137/0914086
[24] B. Jin, J. Zou et al., Iterative parameter choice by discrepancy principle, IMA Journal of Numerical Analysis, 32 (2012), 1714-1732. · Zbl 1261.65052
[25] A. Kneip, Ordered linear smoothers, Ann. Statist., 22, 835-866 (1994) · Zbl 0815.62022 · doi:10.1214/aos/1176325498
[26] O. V. Lepskii, On a Problem of Adaptive Estimation in Gaussian White Noise, Theory of Probability & Its Applications, 35, 454-466 (1991) · Zbl 0745.62083 · doi:10.1137/1135065
[27] H. Li and F. Werner, Empirical risk minimization as parameter choice rule for general linear regularization methods, 2017, arXiv: 1703.07809.
[28] K.-C. Li, From stein’s unbiased risk estimates to the method of generalized cross validation, The Annals of Statistics, 13, 1352-1377 (1985) · Zbl 0605.62047 · doi:10.1214/aos/1176349742
[29] K.-C. Li, Asymptotic optimality for \(\begin{document}C_p\end{document} , \begin{document}C_L\end{document} \), cross-validation and generalized cross-validation: Discrete index set, Ann. Statist., 15, 958-975 (1987) · Zbl 0653.62037 · doi:10.1214/aos/1176350486
[30] F. Luisier; T. Blu; M. Unser, Image denoising in mixed Poisson-Gaussian noise, IEEE Transactions on Image Processing, 20, 696-708 (2011) · Zbl 1372.94168 · doi:10.1109/TIP.2010.2073477
[31] J.-C. Pesquet; A. Benazza-Benyahia; C. Chaux, A SURE Approach for Digital Signal/Image Deconvolution Problems, IEEE Transactions on Signal Processing, 57, 4616-4632 (2009) · Zbl 1392.94041 · doi:10.1109/TSP.2009.2026077
[32] P. Qu; C. Wang; G. X. Shen, Discrepancy-based adaptive regularization for grappa reconstruction, Journal of Magnetic Resonance Imaging, 24, 248-255 (2006) · doi:10.1002/jmri.20620
[33] S. Ramani; T. Blu; M. Unser, Monte-Carlo sure: A black-box optimization of regularization parameters for general denoising algorithms, IEEE Transactions on Image Processing, 17, 1540-1554 (2008) · doi:10.1109/TIP.2008.2001404
[34] S. Ramani; Z. Liu; J. Rosen; J.-F. Nielsen; J. A. Fessler, Regularization parameter selection for nonlinear iterative image restoration and MRI reconstruction using GCV and SURE-based methods, IEEE Transactions on Image Processing, 21, 3659-3672 (2012) · Zbl 1373.94340 · doi:10.1109/TIP.2012.2195015
[35] J. A. Rice, Choice of smoothing parameter in deconvolution problems, Contemporary Mathematics, 59, 137-151 (1986) · Zbl 0623.62032 · doi:10.1090/conm/059/10
[36] C. M. Stein, Estimation of the mean of a multivariate normal distribution, The Annals of Statistics, 9, 1135-1151 (1981) · Zbl 0476.62035 · doi:10.1214/aos/1176345632
[37] A. M. Thompson; J. C. Brown; J. W. Kay; D. M. Titterington, A study of methods of choosing the smoothing parameter in image restoration by regularization, IEEE Trans. Pattern Anal. Mach. Intell., 13, 326-339 (1991) · doi:10.1109/34.88568
[38] G. M. Vainikko, The discrepancy principle for a class of regularization methods, USSR Computational Mathematics and Mathematical Physics, 22, 1-19 (1982) · Zbl 0528.65033 · doi:10.1016/0041-5553(82)90120-3
[39] S. Vaiter; C. Deledalle; G. Peyré, The degrees of freedom of partly smooth regularizers, Annals of the Institute of Statistical Mathematics, 69, 791-832 (2017) · Zbl 1382.62027 · doi:10.1007/s10463-016-0563-z
[40] S. Vaiter; C. Deledalle; G. Peyré; C. Dossal; J. Fadili, Local behavior of sparse analysis regularization: Applications to risk estimation, Applied and Computational Harmonic Analysis, 35, 433-451 (2013) · Zbl 1291.65189 · doi:10.1016/j.acha.2012.11.006
[41] S. A. vande Geer, Applications of Empirical Process Theory, vol. 6 of Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2000. · Zbl 0953.62049
[42] D. Van De Ville and M. Kocher, SURE-Based Non-Local Means, IEEE Signal Processing Letters, 16 (2009), 973-976, URL http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5165022.
[43] D. Van DeVille; M. Kocher, Nonlocal means with dimensionality reduction and SURE-based parameter selection, IEEE Transactions on Image Processing, 20, 2683-2690 (2011) · Zbl 1373.62298 · doi:10.1109/TIP.2011.2121083
[44] Y.-Q. Wang; J.-M. Morel, SURE Guided Gaussian Mixture Image Denoising, SIAM Journal on Imaging Sciences, 6, 999-1034 (2013) · Zbl 1279.68341 · doi:10.1137/120901131
[45] D. S. Weller; S. Ramani; J.-F. Nielsen; J. A. Fessler, Monte Carlo SURE-based parameter selection for parallel magnetic resonance imaging reconstruction, Magnetic Resonance in Medicine, 71, 1760-1770 (2014)
[46] X. Xie; S. C. Kou; L. D. Brown, SURE Estimates for a Heteroscedastic Hierarchical Model, Journal of the American Statistical Association, 107, 1465-1479 (2012) · Zbl 1284.62450 · doi:10.1080/01621459.2012.728154
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.