$ \ell_1 $ regularization is widely used to preserve important features of the desired solution in ill-posed inverse problems. We employed the split Bregman (SB) algorithm, which reformulates the $ \ell_1 $-regularized problem as a sequence of unconstrained optimization problems involving generalized Tikhonov minimization. Selecting the regularization parameter at each SB iteration was crucial for obtaining accurate reconstructions. To address this challenge, we transformed each generalized Tikhonov problem into standard form and determined the regularization parameter using the singular value decomposition (SVD) of a transformed coefficient matrix, thereby improving both stability and efficiency. An enlarged Krylov subspace strategy based on Golub–Kahan bidiagonalization (EGKB) was employed to compute an approximate truncated SVD, with the EGKB implemented in single precision to further reduce computational cost. We extended the unbiased predictive risk estimator (UPRE) to the transformed problem and used it to estimate stabilizing regularization parameters throughout the SB iterations. A theoretical analysis of the computational complexity was presented to demonstrate the efficiency of the proposed framework. Numerical experiments on X-ray tomographic problems demonstrated that EGKB-UPRE achieves reconstruction quality comparable to GSVD-based methods while substantially reducing computational time and storage requirements.
Citation: Abdulmajeed Alsubhi. Enlarged GKB for selecting the regularization parameter in an $ \ell_1 $-regularized problem[J]. AIMS Mathematics, 2026, 11(11): 37909-37933. doi: 10.3934/math.20261465
$ \ell_1 $ regularization is widely used to preserve important features of the desired solution in ill-posed inverse problems. We employed the split Bregman (SB) algorithm, which reformulates the $ \ell_1 $-regularized problem as a sequence of unconstrained optimization problems involving generalized Tikhonov minimization. Selecting the regularization parameter at each SB iteration was crucial for obtaining accurate reconstructions. To address this challenge, we transformed each generalized Tikhonov problem into standard form and determined the regularization parameter using the singular value decomposition (SVD) of a transformed coefficient matrix, thereby improving both stability and efficiency. An enlarged Krylov subspace strategy based on Golub–Kahan bidiagonalization (EGKB) was employed to compute an approximate truncated SVD, with the EGKB implemented in single precision to further reduce computational cost. We extended the unbiased predictive risk estimator (UPRE) to the transformed problem and used it to estimate stabilizing regularization parameters throughout the SB iterations. A theoretical analysis of the computational complexity was presented to demonstrate the efficiency of the proposed framework. Numerical experiments on X-ray tomographic problems demonstrated that EGKB-UPRE achieves reconstruction quality comparable to GSVD-based methods while substantially reducing computational time and storage requirements.
| [1] |
Å. Björck, Numerical methods for least squares problems, SIAM, Philadelphia, 1996. |
| [2] |
G. H. Golub, C. F. Van Loan, Matrix computations, Johns Hopkins University Press, Baltimore, 2013. |
| [3] |
P. C. Hansen, Regularization tools: A MATLAB package for analysis and solution of discrete ill-posed problems, Numer. Algorithms, 6 (1994), 1–35. https://doi.org/10.1007/BF02149761 doi: 10.1007/BF02149761
|
| [4] |
L. Eldén, A weighted pseudoinverse, generalized singular values, and constrained least squares problems, BIT Numer. Math., 22 (1982), 487–502. https://doi.org/10.1007/BF01934412 doi: 10.1007/BF01934412
|
| [5] |
M. Fuhry, L. Reichel, A new Tikhonov regularization method, Numer. Algorithms, 59 (2012), 433–445. https://doi.org/10.1007/s11075-011-9498-x doi: 10.1007/s11075-011-9498-x
|
| [6] |
G. H. Golub, P. C. Hansen, D. P. O'Leary, Tikhonov regularization and total least squares, SIAM J. Matrix Anal. Appl., 21 (1999), 185–194. https://doi.org/10.1137/S0895479897326432 doi: 10.1137/S0895479897326432
|
| [7] |
L. I. Rudin, S. Osher, E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259–268. https://doi.org/10.1016/0167-2789(92)90242-F doi: 10.1016/0167-2789(92)90242-F
|
| [8] |
A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20 (2004), 89–97. https://doi.org/10.1023/B:JMIV.0000011325.36760.1e doi: 10.1023/B:JMIV.0000011325.36760.1e
|
| [9] |
S. Gazzola, M. S. Landman, Flexible GMRES for total variation regularization, BIT Numer. Math., 59 (2019), 721–746. https://doi.org/10.1007/s10543-019-00750-x doi: 10.1007/s10543-019-00750-x
|
| [10] |
T. Goldstein, S. Osher, The split Bregman method for $\ell_1$-regularized problems, SIAM J. Imaging Sci., 2 (2009), 323–343. https://doi.org/10.1137/080725891 doi: 10.1137/080725891
|
| [11] |
A. Lanza, S. Morigi, L. Reichel, F. Sgallari, A generalized Krylov subspace method for $\ell_p-\ell_q$ minimization, SIAM J. Sci. Comput., 37 (2015), S30–S50. https://doi.org/10.1137/140967982 doi: 10.1137/140967982
|
| [12] |
C. R. Vogel, M. E. Oman, Iterative methods for total variation denoising, SIAM J. Sci. Comput., 17 (1996), 227–238. https://doi.org/10.1137/0917016 doi: 10.1137/0917016
|
| [13] |
M. Pasha, A. K. Saibaba, S. Gazzola, M. I. Español, E. de Sturler, A computational framework for edge-preserving regularization in dynamic inverse problems, Electron. T. Numer. Anal., 58 (2023), 486–516. https://doi.org/10.1553/etna_vol58s486 doi: 10.1553/etna_vol58s486
|
| [14] |
R. A. Renaut, S. Vatankhah, V. E. Ardestani, Hybrid and iteratively reweighted regularization by unbiased predictive risk and weighted GCV for projected systems, SIAM J. Sci. Comput., 39 (2017), B221–B243. https://doi.org/10.1137/15M1037925 doi: 10.1137/15M1037925
|
| [15] |
J. Chung, S. Gazzola, Computational methods for large-scale inverse problems: A survey on hybrid projection methods, SIAM Rev., 66 (2024), 205–284. https://doi.org/10.1137/21M1441420 doi: 10.1137/21M1441420
|
| [16] |
S. Gazzola, P. C. Hansen, J. G. Nagy, IR Tools: A MATLAB package of iterative regularization methods and large-scale test problems, Numer. Algorithms, 81 (2019), 773–811. https://doi.org/10.1007/s11075-018-0570-7 doi: 10.1007/s11075-018-0570-7
|
| [17] |
P. C. Hansen, J. G. Nagy, D. P. O'Leary, Deblurring images: Matrices, spectra, and filtering, SIAM, Philadelphia, 2006. https://doi.org/10.1137/1.9780898718874 |
| [18] |
C. R. Vogel, Computational methods for inverse problems, SIAM, Philadelphia, 2002. https://doi.org/10.1137/1.9780898717570 |
| [19] |
C. Van Loan, N. Pitsianis, Approximation with Kronecker products, Technical Report, Cornell University, 1992. |
| [20] |
J. G. Nagy, Decomposition of block Toeplitz matrices into a sum of Kronecker products with applications in image restoration, Technical Report, Citeseer, 1996. |
| [21] |
J. Kamm, J. G. Nagy, Optimal Kronecker product approximation of block Toeplitz matrices, SIAM J. Matrix Anal. Appl., 22 (2000), 155–172. https://doi.org/10.1137/S0895479898345540 doi: 10.1137/S0895479898345540
|
| [22] |
J. G. Nagy, M. K. Ng, L. Perrone, Kronecker product approximations for image restoration with reflexive boundary conditions, SIAM J. Matrix Anal. Appl., 25 (2003), 829–841. https://doi.org/10.1137/S0895479802419580 doi: 10.1137/S0895479802419580
|
| [23] |
B. F. Sweeney, M. I. Español, R. A. Renaut, Efficient decomposition-based algorithms for $\ell_1$-regularized inverse problems with column-orthogonal and Kronecker product matrices, Inverse Probl., 41 (2025), 075016. https://doi.org/10.1088/1361-6420/adec12 doi: 10.1088/1361-6420/adec12
|
| [24] |
T. Bonesky, Morozov's discrepancy principle and Tikhonov-type functionals, Inverse Probl., 25 (2008), 015015. https://doi.org/10.1088/0266-5611/25/1/015015 doi: 10.1088/0266-5611/25/1/015015
|
| [25] |
P. C. Hansen, Rank-deficient and discrete ill-posed problems: Numerical aspects of linear inversion, SIAM, Philadelphia, 1998. https://doi.org/10.1137/1.9780898719697 |
| [26] |
P. C. Hansen, D. P. O'Leary, The use of the L-curve in the regularization of discrete ill-posed problems, SIAM J. Sci. Comput., 14 (1993), 1487–1503. https://doi.org/10.1137/0914086 doi: 10.1137/0914086
|
| [27] |
A. Alsubhi, R. A. Renaut, Enlarged GKB and RSVD for KP approximations illustrated for mixed precision $\ell_1$ image restoration, Numer. Algorithms, 101 (2026), 2245–2267. https://doi.org/10.1007/s11075-025-02086-w doi: 10.1007/s11075-025-02086-w
|
| [28] |
B. Lewis, L. Reichel, Arnoldi–Tikhonov regularization methods, J. Comput. Appl. Math., 226 (2009), 92–102. https://doi.org/10.1016/j.cam.2008.05.003 doi: 10.1016/j.cam.2008.05.003
|
| [29] |
A. Buccini, M. Pasha, L. Reichel, Linearized Krylov subspace Bregman iteration with nonnegativity constraint, Numer. Algorithms, 87 (2021), 1177–1200. https://doi.org/10.1007/s11075-020-01004-6 doi: 10.1007/s11075-020-01004-6
|
| [30] |
M. Alotaibi, A. Buccini, L. Reichel, Krylov subspace split Bregman methods, Appl. Numer. Math., 184 (2023), 371–390. https://doi.org/10.1016/j.apnum.2022.10.009 doi: 10.1016/j.apnum.2022.10.009
|
| [31] |
A. Buccini, F. Chen, M. Pasha, L. Reichel, Krylov subspace based FISTA-type methods for linear discrete ill-posed problems, Numer. Linear Algebr. Appl., 32 (2025), e2610. https://doi.org/10.1002/nla.2610 doi: 10.1002/nla.2610
|
| [32] |
N. J. Higham, T. Mary, Mixed precision algorithms in numerical linear algebra, Acta Numer., 31 (2022), 347–414. https://doi.org/10.1017/S0962492922000022 doi: 10.1017/S0962492922000022
|
| [33] |
G. Golub, W. Kahan, Calculating the singular values and pseudo-inverse of a matrix, J. Soc. Ind. Appl. Math. Ser. B: Numer. Anal., 2 (1965), 205–224. https://doi.org/10.1137/0702016 doi: 10.1137/0702016
|
| [34] |
C. C. Paige, M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM T. Math. Software, 8 (1982), 43–71. https://doi.org/10.1145/355984.355989 doi: 10.1145/355984.355989
|
| [35] |
R. M. Larsen, Lanczos bidiagonalization with partial reorthogonalization, DAIMI Rep. Ser., 1998. https://doi.org/10.7146/dpb.v27i537.7070 |
| [36] |
R. A. Renaut, J. D. Hogue, S. Vatankhah, S. Liu, A fast methodology for large-scale focusing inversion of gravity and magnetic data using the structured model matrix and the 2-D fast Fourier transform, Geophys. J. Int., 223 (2020), 1378–1397. https://doi.org/10.1093/gji/ggaa372 doi: 10.1093/gji/ggaa372
|
| [37] |
H. D. Simon, H. Zha, Low-rank matrix approximation using the Lanczos bidiagonalization process with applications, SIAM J. Sci. Comput., 21 (2000), 2257–2274. https://doi.org/10.1137/S1064827597327309 doi: 10.1137/S1064827597327309
|
| [38] |
I. Yamazaki, S. Tomov, J. Dongarra, Mixed-precision Cholesky QR factorization and its case studies on multicore CPU with multiple GPUs, SIAM J. Sci. Comput., 37 (2015), C307–C330. https://doi.org/10.1137/14M0973773 doi: 10.1137/14M0973773
|
| [39] |
S. Gazzola, E. Onunwor, L. Reichel, G. Rodriguez, On the Lanczos and Golub–Kahan reduction methods applied to discrete ill-posed problems, Numer. Linear Algebr. Appl., 23 (2016), 187–204. https://doi.org/10.1002/nla.2020 doi: 10.1002/nla.2020
|
| [40] |
P. C. Hansen, Regularization, GSVD and truncated GSVD, BIT Numer. Math., 29 (1989), 491–504. https://doi.org/10.1007/BF02219234 |
| [41] |
P. C. Hansen, Discrete inverse problems: Insight and algorithms, SIAM, Philadelphia, PA, 2010. https://doi.org/10.1137/1.9780898718836 |
| [42] |
Z. Bai, The CSD, GSVD, their applications and computations, Inst. Math. Appl., 1992. |
| [43] |
M. Baboulin, O. Kaya, T. Mary, M. Robeyns, Mixed precision iterative refinement for low-rank matrix and tensor approximations, SIAM J. Sci. Comput., 47 (2025), A2906–A2935. https://doi.org/10.1137/23M1576992 doi: 10.1137/23M1576992
|
| [44] |
The MathWorks, Inc., MATLAB Version R2025b, Natick, MA, USA, 2025. |
| [45] |
C. Boutsikas, P. Drineas, I. C. F. Ipsen, Small singular values can increase in lower precision, SIAM J. Matrix Anal. Appl., 45 (2024), 1518–1540. https://doi.org/10.1137/23M1557209 doi: 10.1137/23M1557209
|
The true image of $ 64 \times 64 $ pixels, true sinogram, and noisy sinogram with 6% additive white Gaussian noise, for the problem in Example 6.1
Approximation of the singular values using the true SVD, GKB, and EGKB in SP and DP with $ k = 27 $ and $ p = 27 $ for the transformation $ \tilde{A} $ in (4.9) in Example 6.1
SB solutions at convergence for Figure 1(c). The regularization parameter is selected using the optimal approach, the GSVD, or the EGKB
The corresponding RE, PSNR, RC, and $ \lambda^{(\ell)} $ in the outer iterations $ \ell $ in the SB algorithm for the methods applied to Example 6.1. Note that $ \lambda $ is fixed with Optimal and GSVD
The true image of $ 256 \times 256 $ pixels, true sinogram, and noisy sinogram with 10% Gaussian noise, for the problem in Example 6.2
SB solution with EGKB at convergence for Figure 5(c)
The corresponding RE, PSNR, RC, and $ \lambda^{(\ell)} $ in the outer iterations $ \ell $ in the SB algorithm for the EGKB applied to Example 6.2