nach oben

Journal of Scientific Computing

Erschienen in:

01.05.2024

Sorted \(L_1/L_2\) Minimization for Sparse Signal Recovery

verfasst von: Chao Wang, Ming Yan, Junjie Yu

Erschienen in: Journal of Scientific Computing | Ausgabe 2/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper introduces a novel approach for recovering sparse signals using sorted \(L_1/L_2\) minimization. The proposed method assigns higher weights to indices with smaller absolute values and lower weights to larger values, effectively preserving the most significant contributions to the signal while promoting sparsity. We present models for both noise-free and noisy scenarios, and rigorously prove the existence of solutions for each case. To solve these models, we adopt a linearization approach inspired by the difference of convex functions algorithm. Our experimental results demonstrate the superiority of our method over state-of-the-art approaches in sparse signal recovery across various circumstances, particularly in support detection.

Vorheriger Artikel Admissibility Preserving Subcell Limiter for Lax–Wendroff Flux Reconstruction

Nächster Artikel A Weighted Hybridizable Discontinuous Galerkin Method for Drift-Diffusion Problems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Andreani, R., Birgin, E.G., Mart, J.M., Schuverdt, M.L.: On augmented Lagrangian methods with general lower-level constraints. SIAM J. Optim. 18(4), 1286–1309 (2008)MathSciNetCrossRef

Bishop, C.M., Nasrabadi, N.M.: Pattern Recognition and Machine Learning, vol. 4. Springer, Berlin (2006)

Candes, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51(12), 4203–4215 (2005)MathSciNetCrossRef

Chartrand, R.: Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Process. Lett. 10(14), 707–710 (2007)CrossRef

Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289–1306 (2006)MathSciNetCrossRef

Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348–1360 (2001)MathSciNetCrossRef

Fannjiang, A., Liao, W.: Coherence pattern-guided compressive sensing with unresolved grids. SIAM J. Imag. Sci. 5(1), 179–202 (2012)MathSciNetCrossRef

Fannjiang, A., Liao, W.: Coherence pattern-guided compressive sensing with unresolved grids. SIAM J. Imag. Sci. 5(1), 179–202 (2012). https://doi.org/10.1137/110838509MathSciNetCrossRef

Ge, H., Chen, W., Ng, M.K.: Analysis of the ratio of \(\ell _1\) and \(\ell _2\) norms for signal recovery with partial support information. Inf. Inference J. IMA 12(3), iaad015 (2023). https://doi.org/10.1093/imaiai/iaad015MathSciNetCrossRef

10.

Guo, W., Lou, Y., Qin, J., Yan, M.: A novel regularization based on the error function for sparse recovery. J. Sci. Comput. 87(1), 31 (2021)MathSciNetCrossRef

11.

Hoyer, P.O.: Non-negative sparse coding. In Proceedings of the IEEE Workshop Neural Networks Signal Processing, pp. 557–565 (2002)

12.

Hu, Y., Zhang, D., Ye, J., Li, X., He, X.: Fast and accurate matrix completion via truncated nuclear norm regularization. IEEE Trans. Pattern Anal. Mach. Intell. 35(9), 2117–2130 (2012)CrossRef

13.

Huang, X.L., Shi, L., Yan, M.: Nonconvex sorted l1 minimization for sparse approximation. J. Oper. Res. Soc. China 3(2), 207–229 (2015)MathSciNetCrossRef

14.

Lou, Y., Yan, M.: Fast \(L_1\)-\(L_2\) minimization via a proximal operator. J. Sci. Comput. 74(2), 767–785 (2018)MathSciNetCrossRef

15.

Lou, Y., Yin, P., He, Q., Xin, J.: Computing sparse representation in a highly coherent dictionary based on difference of \({L_1}\) and \({L_2}\). J. Sci. Comput. 64(1), 178–196 (2015)MathSciNetCrossRef

16.

Lou, Y., Yin, P., Xin, J.: Point source super-resolution via non-convex l1 based methods. J. Sci. Comput. 68, 1082–1100 (2016)MathSciNetCrossRef

17.

Lv, J., Fan, Y.: A unified approach to model selection and sparse recovery using regularized least squares. Ann. Stat. 3498–3528 (2009)

18.

Ma, T.H., Lou, Y., Huang, T.Z.: Truncated l_1-2 models for sparse recovery and rank minimization. SIAM J. Imag. Sci. 10(3), 1346–1380 (2017)CrossRef

19.

Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 227–234 (1995)

20.

Optimization, G.: Gurobi optimizer reference manual (2015)

21.

Pham-Dinh, T., Le-Thi, H.A.: A DC optimization algorithm for solving the trust-region subproblem. SIAM J. Optim. 8(2), 476–505 (1998)MathSciNetCrossRef

22.

Pham-Dinh, T., Le-Thi, H.A.: The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133(1–4), 23–46 (2005)MathSciNet

23.

Rahimi, Y., Wang, C., Dong, H., Lou, Y.: A scale-invariant approach for sparse signal recovery. SIAM J. Sci. Comput. 41(6), A3649–A3672 (2019)MathSciNetCrossRef

24.

Shen, X., Pan, W., Zhu, Y.: Likelihood-based selection and sharp parameter estimation. J. Am. Stat. Assoc. 107(497), 223–232 (2012)MathSciNetCrossRef

25.

Tao, M.: Minimization of \(L_1\) over \(L_2\) for sparse signal recovery with convergence guarantee. SIAM J. Sci. Comput. 44(2), A770–A797 (2022)CrossRef

26.

Tao, M., Zhang, X.P.: Study on \(L_1\) over \(L_2\) minimization for nonnegative signal recovery. J. Sci. Comput. 95(3), 94 (2023)CrossRef

27.

Vavasis, S.A.: Derivation of compressive sensing theorems from the spherical section property. University of Waterloo, CO 769 (2009)

28.

Wang, C., Tao, M., Chuah, C.N., Nagy, J., Lou, Y.: Minimizing \(L_1\) over \(L_2\) norms on the gradient. Inverse Prob. 38(6), 065011 (2022)CrossRef

29.

Wang, C., Tao, M., Nagy, J.G., Lou, Y.: Limited-angle CT reconstruction via the \(L_1/L_2\) minimization. SIAM J. Imag. Sci. 14(2), 749–777 (2021)CrossRef

30.

Wang, C., Yan, M., Rahimi, Y., Lou, Y.: Accelerated schemes for the \(L_1/L_2\) minimization. IEEE Trans. Signal Process. 68, 2660–2669 (2020)MathSciNetCrossRef

31.

Wang, J., Ma, Q.: The variant of the iterative shrinkage-thresholding algorithm for minimization of the \(\ell _1\) over \(\ell _\infty \) norms. Signal Process. 211, 109104 (2023). https://doi.org/10.1016/j.sigpro.2023.109104CrossRef

32.

Wang, Y., Yin, W.: Sparse signal reconstruction via iterative support detection. SIAM J. Imag. Sci. 3(3), 462–491 (2010)MathSciNetCrossRef

33.

Wright, S.J.: Coordinate descent algorithms. Math. Progr. 151(1), 3–34 (2015). https://doi.org/10.1007/s10107-015-0892-3MathSciNetCrossRef

34.

Xie, H., Huang, J.: SCAD-penalized regression in high-dimensional partially linear models. Ann. Stat. 37(2), 673–696 (2009)MathSciNetCrossRef

35.

Xu, Y., Narayan, A., Tran, H., Webster, C.G.: Analysis of the ratio of \(\ell _1\) and \(\ell _2\) norms in compressed sensing. Appl. Comput. Harmon. Anal. 55, 486–511 (2021)MathSciNetCrossRef

36.

Xu, Z., Chang, X., Xu, F., Zhang, H.: \(l_{1/2}\) regularization: a thresholding representation theory and a fast solver. IEEE Trans. Neural Netw. Learn. Syst. 23(7), 1013–1027 (2012). https://doi.org/10.1109/TNNLS.2012.2197412CrossRef

37.

Yin, P., Esser, E., Xin, J.: Ratio and difference of \(l_1\) and \(l_2\) norms and sparse representation with coherent dictionaries. Commun. Inf. Syst. 14, 87–109 (2014)MathSciNetCrossRef

38.

Yin, P., Lou, Y., He, Q., Xin, J.: Minimization of \(\ell _{1-2}\) for compressed sensing. SIAM J. Sci. Comput. 37(1), A536–A563 (2015)MathSciNetCrossRef

39.

Zeng, L., Yu, P., Pong, T.K.: Analysis and algorithms for some compressed sensing models based on \(L_1/L_2\) minimization. SIAM J. Optim. 31(2), 1576–1603 (2021)MathSciNetCrossRef

40.

Zhang, C.H.: Nearly unbiased variable selection under minimax concave penalty. Ann. Stat. 38(2), 894–942 (2010)MathSciNetCrossRef

41.

Zhang, S., Xin, J.: Minimization of transformed \(l_1\) penalty: Theory, difference of convex function algorithm, and robust application in compressed sensing. Math. Progr. 169, 307–336 (2018)CrossRef

42.

Zhang, T.: Multi-stage convex relaxation for learning with sparse regularization. In Advances in Neural Information Processing Systems, pp. 1929–1936 (2009)

43.

Zhang, Y.: Theory of compressive sensing via \(L_1\)-minimization: a non-RIP analysis and extensions. J. Oper. Res. Soc. China 1(1), 79–105 (2013)CrossRef

44.

Zhou, Z., Yu, J.: Sparse recovery based on q-ratio constrained minimal singular values. Signal Process. 155, 247–258 (2019)CrossRef

45.

Zibulevsky, M., Elad, M.: \(L_1\)-\(L_2\) optimization in signal and image processing. IEEE Signal Process. Mag. 27(3), 76–88 (2010)CrossRef

Titel: Sorted Minimization for Sparse Signal Recovery
verfasst von: Chao Wang
Ming Yan
Junjie Yu
Publikationsdatum: 01.05.2024
Verlag: Springer US
Erschienen in: Journal of Scientific Computing / Ausgabe 2/2024
Print ISSN: 0885-7474
Elektronische ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-024-02497-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2024

An Iterative Method for the Inverse Eddy Current Problem with Total Variation Regularization

A Numerical Method for Solving Elliptic Equations on Real Closed Algebraic Curves and Surfaces

Asymptotically Compatible Energy and Dissipation Law of the Nonuniform L2- Scheme for Time Fractional Allen–Cahn Model

On the Dynamics of the Boundary Vorticity for Incompressible Viscous Flows

Efficient Convex Optimization for Non-convex Non-smooth Image Restoration

A Weighted Hybridizable Discontinuous Galerkin Method for Drift-Diffusion Problems

Premium Partner