Top

Journal of Scientific Computing

Published in:

01-05-2024

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

Authors: Chao Wang, Ming Yan, Junjie Yu

Published in: Journal of Scientific Computing | Issue 2/2024

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Admissibility Preserving Subcell Limiter for Lax–Wendroff Flux Reconstruction

next article A Weighted Hybridizable Discontinuous Galerkin Method for Drift-Diffusion Problems

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

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

Title: Sorted Minimization for Sparse Signal Recovery
Authors: Chao Wang
Ming Yan
Junjie Yu
Publication date: 01-05-2024
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 2/2024
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-024-02497-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2024

The Order-p Tensor Linear Complementarity Problem for Images Deblurring

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

High-Order Multi-resolution Central Hermite WENO Schemes for Hyperbolic Conservation Laws

A Descent Scheme for Thick Elastic Curves with Self-contact and Container Constraints

Analysis of an Energy-Dissipating Finite Volume Scheme on Admissible Mesh for the Aggregation-Diffusion Equations

A New Complex Structure-Preserving Method for QSVD

Premium Partner