Risk estimators for choosing regularization parameters in ill-posed problems - properties and limitations

Figure 1.  (a) The convolution kernel $k_l(t)$ for different values of $l$.(b) True solution $x^*$, clean data $A_l x^*$ and noisy data $A_lx^* +\varepsilon$ for $m = n = 64$, $l = 0.06$, $\sigma = 0.1$

Figure 2.  Decay of the singular values $\gamma_i$ of $A_l$ for different choices of $m = n$ and $l$. As expected, increasing the width $l$ of the convolution kernel leads to a faster decay. For a fixed $l$, increasing $m$ corresponds to using a finer discretization and $\gamma_i$ converges to the corresponding singular value of $A_{\infty, l}$, as can be seen for the largest $\gamma_i$, e.g., for $l = 0.02$

Figure 3.  Empirical probabilities of (a) $\hat \alpha$ and (b) the corresponding $\ell_2$-error for different parameter choice rules using $m = n = 64$, $l = 0.06$, $\sigma = 0.1$ and $N_\varepsilon = 10^6$ samples of $\varepsilon$

Figure 4.  Joint empirical probabilities of $\log_{10}\|x^* - x_{\hat \alpha}\|_2$ using $m = n = 64$, $l = 0.06$, $\sigma = 0.1$ and $N_\varepsilon = 10^6$ samples of $\varepsilon$ (the histograms in Figure 3(b) are the marginal distributions thereof). As in Figure 3(b), the logarithms of the probabilities are displayed (here in form of a color-coding) to facilitate the identification of smaller modes and tails. The red line at $x = y$ divides the areas where one method performs better than the other: In (a), all samples falling into the area on the right of the red line correspond to a noise realization where the discrepancy principle leads to a smaller error than PSURE. The percentage of samples for which that is true is 13% for PSURE and 44% for SURE

Figure 5.  True risk functions (black dotted line), their estimates for six different realizations $y^k$, $k = 1\ldots 6$ (solid lines), and their corresponding minima/roots (dots on the lines) in the setting described in Figure 1 using $\ell_2$-regularization: (a) $\text{DP}(\alpha, Ax^*)$ and $\text{DP}(\alpha, y^k)$. (b) $\text{MSPE}(\alpha)$ and $\text{PSURE}(\alpha, y^k)$. (c) $\text{MSEE}(\alpha)$ and $\text{SURE}(\alpha, y^k)$

Figure 6.  Illustration of Theorems 3.3 and 3.8 for $\ell_2$-regularization: The left hand side of (22)/(23) was estimated by the sample mean and plotted vs. $m$. For (23), the normalization with $\text{cond}(A)$ was omitted in (b) and included in (c). The black dotted lines were added to compare the order of convergence

Figure 7.  Empirical probabilities of $\alpha$ for $\ell_2$-regularization and different parameter choice rules for $l = 0.06$ and varying $m$

Figure 8.  Empirical probabilities of $\log_{10}\left(\tfrac{1}{m} \| x^* - x_{\alpha} \|_2^2\right)$ for $\ell_2$-regularization and different parameter choice rules for $l = 0.06$ and varying $m$

Figure 9.  Empirical probabilities of $\alpha$ for $\ell_2$-regularization and different parameter choice rules for $m = 64$ and varying $l$

Figure 10.  Empirical probabilities of $\log_{10}\left(\tfrac{1}{m} \| x^* - x_{\alpha} \|_2^2\right)$ for $\ell_2$-regularization and different parameter choice rules for $m = 64$ and varying $l$

Figure 11.  Illustration of the difference between evaluating the SURE risk on a coarse, linear grid for $\alpha$ as opposed to a fine, logarithmic one: In (a), a linear grid is constructed around ${{\hat{\alpha }}_{\text{DP}}}$ as $\alpha = \Delta_\alpha, 2 \Delta_\alpha, \ldots, 50\Delta_\alpha$ with $\Delta_\alpha = 2 {{\hat{\alpha }}_{\text{DP}}}/50$. While the plot suggests a clear minimum, (b) reveals that it is only a sub-optimal local minimum and that the linear grid did not cover the essential parts of $\text{SURE}(\alpha, y)$. (c) and (d) show the same plots for a different noise realization. Here, a linear grid will not even find a clear minimum. Both risk estimators are the same as those plotted in Figure 5(c) with the same colors

Figure 12.  Risk functions (black dotted line), $k = 1, \ldots, 6$ estimates thereof (solid lines) and their corresponding minima/roots (dots on the lines) in the setting described in Figure 1 using $\ell_1$-regularization: (a) $\text{DP}(\alpha, Ax^*)$ and $\text{DP}(\alpha, y^k)$. (b) $\text{MSPE}(\alpha)$ (empirical mean over $N_\varepsilon = 10^4$) and $\text{PSURE}(\alpha, y^k)$. (c) $\text{MSEE}(\alpha)$ (empirical mean over $N_\varepsilon = 10^4$) and $\text{SURE}(\alpha, y^k)$

Figure 13.  Empirical probabilities of (a) $\alpha$ and (b) the corresponding $\ell_1$-error for different parameter choice rules using $\ell_1$-regularization, $m = n = 64$, $l = 0.06$, $\sigma = 0.1$ and $N = 10^4$ samples of $\varepsilon$

Figure 14.  Illustration that Theorems 3.3 and 3.8 might also hold for $\ell_1$-regularization: The left hand side of (22)/(23) is estimated by the sample mean and plotted vs. $m$. The black dotted lines were added to compare the order of convergence

Figure 15.  Illustration of the difficulties of evaluating the SURE risk in the case of $\ell_1$-regularization: In (a), a coarse linear grid is constructed around ${{\hat{\alpha }}_{\text{DP}}}$ as $\alpha = \Delta_\alpha, 2 \Delta_\alpha, \ldots, 20\Delta_\alpha$ with $\Delta_\alpha = {{\hat{\alpha }}_{\text{DP}}}/10$. Similar to Figure 11(a) the plot suggests a clear minimum. However, using a fine, logarithmic grid, (b) reveals that it is only a sub-optimal local minimum before a very erratic part of $\text{SURE}(\alpha, y)$ starts. (c) shows how a coarse $\alpha$-grid can lead to an arbitrary projection of $\text{SURE}(\alpha, y)$ that is likely to miss important features. Both risk estimators are the same as those plotted in Figure 12(c)with the same colors. In (d), the difference between computing $\text{SURE}(\alpha, y)$ with the consistent and highly accurate version of ADMM (Impl A) and with a standard ADMM version using only 20 iterations (Impl B) is illustrated