\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents
Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

Minimizing quotient regularization model

  • *Corresponding author: Yifei Lou

    *Corresponding author: Yifei Lou

The first author is supported by the Natural Science Foundation of China 12201286, the Shenzhen Science and Technology Program 20231115165836001, and Guangdong Basic and Applied Research Foundation 2024A1515012347. The second and third authors acknowledge the support of the European Union's Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No777826. The third author acknowledges support by ISF grant 534/19 and ISF 1472/23. The last author is supported by NSF CAREER award 2414705. This work was initiated while J-F. Aujol and Y. Lou were visiting the Mathematical Department of UCLA

Abstract / Introduction Full Text(HTML) Figure(5) / Table(4) Related Papers Cited by
  • Quotient regularization models (QRMs) are a class of powerful regularization techniques that have gained considerable attention in recent years, due to their ability to handle complex and highly nonlinear data sets. However, the nonconvex nature of QRM poses a significant challenge in finding its optimal solution. We are interested in scenarios where both the numerator and the denominator of QRM are absolutely one-homogeneous functions, which is widely applicable in the fields of signal processing and image processing. In this paper, we utilize a gradient flow to minimize such QRM in combination with a quadratic data fidelity term. Our scheme involves solving a convex problem iteratively. The convergence analysis is conducted on a modified scheme in a continuous formulation, showing the convergence to a stationary point. Numerical experiments demonstrate the effectiveness of the proposed algorithm in terms of accuracy, outperforming the state-of-the-art QRM solvers.

    Mathematics Subject Classification: Primary: 65F22, 65Y04; Secondary: 52A41, 49N45.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  A 2D illustration of $ L_1/L_2 $ and $ L_1/Q_1 $ that give a better approximation to the $ L_0 $ norm with a comparison to the convex $ L_1 $ norm

    Figure 2.  The objective function (7) respect to the iteration counts: $ L_1/L_2 $ and $ L_1/Q_K $ for signal recovery (left) and $ L_1/L_2 $ on the gradient for image recovery (right). The decay in each objective function provides empirical evidence of the convergence of the proposed scheme (11)

    Figure 3.  Numerical verification for the decreasing property revealed by Theorem 3.6: if $ \|Au^0\|_2\geq \|f\|_2 $, then $ \|u^k\|_2 $ decreases with respect to the iteration (left); otherwise, $ \|u^k\|_2 $ increases (right). We plot $ \|u^k\|_2 $ on the top row, while $ \|Au^0\|_2-\|f\|_2 $ with a baseline of 0 (red dash line) on the bottom row

    Figure 4.  MRI reconstruction on the SL phantom with a noise level of $ \sigma = 0.05 $ with 7 radial lines. Top row – reconstruction results, bottom row – difference from ground truth. The proposed algorithm outperforms the previous ADMM approach at the outer ring and boundaries of the three middle oval shapes, better seen in the difference map

    Figure 5.  MRI reconstruction on the FB phantom with a noise level of $ \sigma = 0.05 $ with 13 radial lines. Top row – reconstruction results, bottom row – difference from ground truth. The proposed algorithm is able to better preserve the overall geometric shapes, compared to competing methods

    Table 1.  Impact of the parameter $ K $ on the sparse recovery via the $ L_1/Q_K $ model. The sensing matrix $ A $ is of size $ m \times n $, where $ m $ ranges from 250 to 360 and $ n = 512 $. The ground-truth sparse vector contains $ s = 130 $ nonzero elements. Each recorded value is averaged over 100 random realizations. The baseline model refers to the $ L_1 $ minimization, whose solution serves as the initial condition for $ L_1/Q_K $. When $ K $ is chosen to be close to the true sparsity level (e.g., $ K = 100, 150 $ versus $ s = 130 $), $ L_1/Q_K $ yields top-notch performance; otherwise (e.g., $ K = 10 $), $ L_1/L_2 (K = n) $ is the best

    250 260 270 280 290 300
    baseline 5.27 4.97 4.59 4.44 4.20 3.91
    10 5.20 4.87 4.44 4.19 3.93 3.69
    100 4.95 4.57 4.12 3.80 3.56 3.29
    150 4.92 4.55 4.10 3.80 3.53 3.29
    $ n $ 5.01 4.65 4.19 3.90 3.65 3.43
    310 320 330 340 350 360
    baseline 3.73 3.55 3.49 3.26 3.13 3.02
    10 3.42 3.25 3.11 2.97 2.86 2.75
    100 3.01 2.86 2.70 2.57 2.46 2.34
    150 3.02 2.86 2.71 2.58 2.49 2.39
    $ n $ 3.16 3.04 2.91 2.81 2.73 2.65
     | Show Table
    DownLoad: CSV

    Table 2.  MSEs of recovering a sparse vector of length $ n = 512 $ with $ s = 130 $ nonzero elements from $ m $ noisy measurements ($ m = 240:20:360 $ following the MatLab's notation). We compare $ L_1/L_2 $ and $ L_1/Q_K $ for $ K = 100 $ under the settings of FP (35) and QRM (3). We observe that QRM is a better framework than FB for sparse recovery. The best results are consistently given by the proposed algorithm for solving the $ L_1/Q_K $ model when the value of $ K = 100 $ is close to the true sparsity level ($ 130 $). The $ L_1/L_2 $ (when $ K = n $) model achieves the second best in performance

    model-algorithm 240 260 280 300 320 340 360
    FP $ L_1/L_2 $-ADMM 5.51 4.76 4.00 3.48 3.15 2.86 2.67
    $ L_1/L_2 $-PGSA_BE 11.12 8.60 6.28 4.40 3.37 2.83 2.52
    $ L_1/Q_K $-PGSA_BE 5.62 4.75 3.92 3.41 3.08 2.83 2.68
    QRM $ L_1/L_2 $-DCA 5.56 4.87 4.14 3.61 3.27 2.95 2.69
    $ L_1/L_2 $-ADMM 5.53 4.75 3.96 3.45 3.12 2.86 2.68
    $ L_1/L_2 $-proposed 5.50 4.70 3.92 3.40 3.07 2.81 2.64
    $ L_1/Q_K $-DCA 5.52 4.77 4.01 3.48 3.15 2.86 2.67
    $ L_1/Q_K $-proposed 5.44 4.65 3.83 3.26 2.91 2.57 2.33
     | Show Table
    DownLoad: CSV

    Table 3.  F1 score on support identification, with $ s = 130 $ nonzero elements from $ m $ noisy measurements ($ m = 240:20:360 $ following the MatLab's notation). We compare $ L_1/L_2 $ and $ L_1/Q_K $ for $ K = 100 $ under the settings of FP (4) and QRM (3). The best results are consistently given by the proposed algorithm for solving the $ L_1/Q_K $ model when the value of $ K = 100 $ is close to the true sparsity level ($ 130 $)

    model-algorithm 240 260 280 300 320 340 360
    FP $ L_1/L_2 $-ADMM 0.41 0.41 0.41 0.41 0.41 0.41 0.41
    $ L_1/L_2 $-PGSA_BE 0.44 0.51 0.58 0.65 0.69 0.70 0.70
    $ L_1/Q_K $-PGSA_BE 0.49 0.50 0.50 0.50 0.50 0.49 0.49
    QRM $ L_1/L_2 $-DCA 0.41 0.41 0.41 0.41 0.41 0.41 0.41
    $ L_1/L_2 $-ADMM 0.49 0.49 0.50 0.49 0.49 0.48 0.47
    $ L_1/L_2 $-proposed 0.49 0.50 0.51 0.50 0.50 0.49 0.48
    $ L_1/Q_K $-DCA 0.41 0.41 0.41 0.41 0.41 0.41 0.41
    $ L_1/Q_K $-proposed 0.59 0.61 0.65 0.66 0.67 0.67 0.67
     | Show Table
    DownLoad: CSV

    Table 4.  MRI reconstruction from different numbers of radial lines and different noise levels

    Image $ \sigma $ Line $ L_1 $ $ L_1/L_2 $-ADMM $ L_1/L_2 $-proposed
    RE PSNR RE PSNR RE PSNR
    SL 0.01 7 46.06% 19.50 25.36% 24.09 3.74% 40.72
    10 16.29% 28.66 3.41% 41.53 2.91% 42.90
    13 6.85% 36.52 1.91% 46.55 1.71% 47.49
    0.05 7 52.31% 18.33 43.63% 19.38 31.90% 22.10
    10 33.09% 22.42 14.34% 29.04 14.08% 29.24
    13 22.67% 26.10 10.50% 31.75 10.41% 31.82
    FB 0.01 7 21.63% 21.49 13.80% 24.89 1.11% 26.94
    10 18.14% 23.08 14.98% 24.17 12.90% 25.47
    13 9.51% 28.29 1.41% 44.71 1.17% 46.31
    0.05 7 26.03% 19.9 22.14% 20.78 16.50% 23.36
    10 18.14% 23.08 14.98% 24.17 12.90% 25.47
    13 14.48% 24.79 12.67% 25.64 12.30% 25.89
     | Show Table
    DownLoad: CSV
  • [1] J.-F. AujolG. Gilboa and N. Papadakis, Theoretical analysis of flows estimating eigenfunctions of one-homogeneous functionals, SIAM J. Imaging Sci., 11 (2018), 1416-1440.  doi: 10.1137/17M1139126.
    [2] H. Bauschke and P. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, 2017. doi: 10.1007/978-3-319-48311-5.
    [3] M. Benning, G. Gilboa, J. S. Grah and C.-B. Schönlieb, Learning filter functions in regularisers by minimising quotients, International Conference on Scale Space and Variational Methods in Computer Vision (SSVM), Kolding, Denmark, Springer, 6 (2017), 511-523. doi: 10.1007/978-3-319-58771-4_41.
    [4] M. BenningG. Gilboa and C.-B. Schönlieb, Learning parametrised regularisation functions via quotient minimisation, PAMM, 16 (2016), 933-936.  doi: 10.1002/pamm.201610451.
    [5] S. Boyd, N. Parikh and E. Chu, Distributed Optimization and Statistical Learning Via the Alternating Direction Method of Multipliers, Now Publishers Inc, 2011. doi: 10.1561/9781601984616.
    [6] X. Bresson, T. Laurent, D. Uminsky and J. V. Brecht, Convergence and energy landscape for Cheeger cut clustering, Adv. Neural Inf. Process. Syst., (2012), 1385-1393.
    [7] L. BungertE. Hait-FraenkelN. Papadakis and G. Gilboa, Nonlinear power method for computing eigenvectors of proximal operators and neural networks, SIAM J. Imaging Sci., 14 (2021), 1114-1148.  doi: 10.1137/20M1384154.
    [8] M. BurgerG. GilboaM. MoellerL. Eckardt and D. Cremers, Spectral decompositions using one-homogeneous functionals, SIAM Journal on Imaging Sciences, 9 (2016), 1374-1408.  doi: 10.1137/15M1054687.
    [9] A. CherniE. ChouzenouxL. Duval and J.-C. Pesquet, SPOQ $\ell_p $-over-$\ell_q $ regularization for sparse signal recovery applied to mass spectrometry, IEEE Trans. Signal Process., 68 (2020), 6070-6084.  doi: 10.1109/TSP.2020.3025731.
    [10] L. Demanet and P. Hand, Scaling law for recovering the sparsest element in a subspace, Information and Inference: A Journal of the IMA, 3 (2014), 295-309.  doi: 10.1093/imaiai/iau007.
    [11] T. FeldJ.-F. AujolG. Gilboa and N. Papadakis, Rayleigh quotient minimization for absolutely one-homogeneous functionals, Inverse Probl., 35 (2019), 064003.  doi: 10.1088/1361-6420/ab0cb2.
    [12] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.
    [13] M. Hein and T. Bühler, An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse pca, Adv. Neural Inf. Process. Syst., 23.
    [14] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 2012. doi: 10.1017/CBO9781139020411.
    [15] P. O. Hoyer, Non-negative matrix factorization with sparseness constraints., J. Mach. Learn. Res., 5.
    [16] Y. HuD. ZhangJ. YeX. Li and X. He, Fast and accurate matrix completion via truncated nuclear norm regularization, IEEE Trans. Pattern Anal. Mach. Intell., 35 (2012), 2117-2130.  doi: 10.1109/TPAMI.2012.271.
    [17] N. Hurley and S. Rickard, Comparing measures of sparsity, IEEE Trans. Inf. Theory, 55 (2009), 4723-4741.  doi: 10.1109/TIT.2009.2027527.
    [18] H. K. Klein and M. D. Myers, A set of principles for conducting and evaluating interpretive field studies in information systems, MIS Quarterly, 67-93. doi: 10.2307/249410.
    [19] J. LeiQ. Liu and X. Wang, Physics-informed multi-fidelity learning-driven imaging method for electrical capacitance tomography, Eng. Appl. Artif. Intell., 116 (2022), 105467.  doi: 10.1016/j.engappai.2022.105467.
    [20] Q. LiL. ShenN. Zhang and J. Zhou, A proximal algorithm with backtracked extrapolation for a class of structured fractional programming, Appl. Comput. Harmon. Anal., 56 (2022), 98-122.  doi: 10.1016/j.acha.2021.08.004.
    [21] B. S. Mordukhovich, Variational Analysis and Generalized Differentiation II: Applications, Springer, 331 (2006). doi: 10.1007/3-540-31246-3.
    [22] R. Z. Nossek and G. Gilboa, Flows generating nonlinear eigenfunctions, J. Sci. Comput., 75 (2018), 859-888.  doi: 10.1007/s10915-017-0577-6.
    [23] T.-H. OhY.-W. TaiJ.-C. BazinH. Kim and I. S. Kweon, Partial sum minimization of singular values in robust PCA: Algorithm and applications, IEEE Trans. Pattern Anal. Mach. Intell., 38 (2015), 744-758.  doi: 10.1109/TPAMI.2015.2465956.
    [24] T. Pham-Dinh and H. A. Le-Thi, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133 (2005), 23-46.  doi: 10.1007/s10479-004-5022-1.
    [25] Y. Rahimi, C. Wang, H. Dong and Y. Lou, A scale-invariant approach for sparse signal recovery, SIAM J. Sci. Comput., 41 (2019), A3649-A3672. doi: 10.1137/18M123147X.
    [26] M. Tao, Minimization of $L_1$ over $L_2$ for sparse signal recovery with convergence guarantee, SIAM J. Sci. Comput., 44 (2022), A770-A797. doi: 10.1137/20M136801X.
    [27] C. WangM. TaoC.-N. ChuahJ. Nagy and Y. Lou, Minimizing $L_1$ over $L_2$ norms on the gradient, Inverse Probl., 38 (2022), 065011.  doi: 10.1088/1361-6420/ac64fb.
    [28] C. WangM. TaoJ. G. Nagy and Y. Lou, Limited-angle CT reconstruction via the $L_1/L_2$ minimization, SIAM J. Imaging Sci., 14 (2021), 749-777. 
    [29] C. WangM. YanY. Rahimi and Y. Lou, Accelerated schemes for the $L_1/L_2 $ minimization, IEEE Trans. Signal Process., 68 (2020), 2660-2669. 
    [30] J. Wang, A wonderful triangle in compressed sensing, Information Sciences, 611 (2022), 95-106. 
    [31] T. WuZ. MaoZ. LiY. Zeng and T. Zeng, Efficient color image segmentation via quaternion-based $l_1/l_2$ regularization, J. Sci. Comput., 93 (2022), 9.  doi: 10.1007/s10915-022-01970-0.
    [32] Y. XuA. NarayanH. Tran and C. G. Webster, Analysis of the ratio of $\ell_1$ and $\ell_2$ norms in compressed sensing, Appl. Comput. Harmon. Anal., 55 (2021), 486-511.  doi: 10.1016/j.acha.2021.06.006.
    [33] Z. Yu, F. Noo, F. Dennerlein, A. Wunderlich, G. Lauritsch and J. Hornegger, Simulation tools for two-dimensional experiments in x-ray computed tomography using the FORBILD head phantom, Phys. Med. Biol., 57 (2012), N237. doi: 10.1088/0031-9155/57/13/N237.
    [34] N. Zhang and Q. Li, First-order algorithms for a class of fractional optimization problems, SIAM J. Optim., 32 (2022), 100-129. 
  • 加载中

Figures(5)

Tables(4)

SHARE

Article Metrics

HTML views(468) PDF downloads(192) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return