Research article

Enlarged GKB for selecting the regularization parameter in an $ \ell_1 $-regularized problem

  • Published: 13 November 2026
  • MSC : 65F22, 65F10, 68W40

  • $ \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

    Related Papers:

  • $ \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
  • Reader Comments
  • © 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)

Metrics

Article views(87) PDF downloads(26) Cited by(0)

Article outline

Figures and Tables

Figures(7)  /  Tables(4)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog