Top

Journal of Scientific Computing

Published in:

01-08-2023

A Reduced Half Thresholding Algorithm

Authors: Xiubo Liang, Guoqiang Wang, Bo Yu

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

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

search-config

AI-assisted search

Off

Abstract

In this paper, a reduced half thresholding algorithm and its accelerated version, a reduced fast half thresholding algorithm, are proposed for solving large-scale \(L_{1/2}\)-regularized problems. At each iteration, the large-scale original problem is reduced into a sequence of small-scale subproblems, and the subproblems are solved by the (fast) half thresholding algorithm. Global convergence of the reduced half thresholding algorithm is proven, and two techniques: the Newton acceleration technique and the shrinking technique are presented to improve the performance. Compared with the state-of-the-art algorithms, the numerical results show that the presented algorithms are promising. As an example, our algorithms are efficient to recover the signal recovery problem with 19,264,097 samples and signal length 29,890,095

previous article Müntz Ball Polynomials and Müntz Spectral-Galerkin Methods for Singular Eigenvalue Problems

next article Optimal-Order Convergence of a Two-Step BDF Method for the Navier–Stokes Equations with Initial Data

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

https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets.

https://www.csie.ntu.edu.tw/\(\sim \)cjlin/libsvmtools/datasets.

Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2, 183–202 (2009)MathSciNetCrossRefMATH

Large-scale regression with non-convex loss and penalty: Buccini, A., De la Cruz Cabrera, O., Donatelli et al., M. Appl. Numer. Math. 157, 590–601 (2020)

Candes, E.J., Randall, P.A.: Highly robust error correction byconvex programming. IEEE Trans. Inf. Theory 54, 2829–2840 (2008)CrossRefMATH

Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9, 717–772 (2009)MathSciNetCrossRefMATH

Candès, E.J., Romberg, J.: Quantitative robust uncertainty principles and optimally sparse decompositions. Found. Comput. Math. 6, 227–254 (2006)MathSciNetCrossRefMATH

Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 489–509 (2006)MathSciNetCrossRefMATH

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

Candes, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59, 1207–1223 (2006)MathSciNetCrossRefMATH

Candes, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theor 52, 489–509 (2006)MathSciNetCrossRefMATH

10.

Chan, R. H., Liang, H. X.: Half-quadratic algorithm for \(\ell _p-\ell _q\) problems with applications to TV-\(\ell _1 \) image restoration and compressive sensing, In Efficient algorithms for global optimization methods in computer vision (2014).pp. 78-103. Springer, Berlin, Heidelberg

11.

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

12.

Chartrand, R., Fast algorithms for nonconvex compressive sensing: mri reconstruction from very few data, in,: IEEE International Symposium on Biomedical Imaging: From Nano to Macro. IEEE 2009, 262–265 (2009)

13.

Chartrand, R., Staneva, V.: Restricted isometry properties and nonconvex compressive sensing. Inverse Prob. 24, 035020 (2008)MathSciNetCrossRefMATH

14.

Chen, X., Ge, D., Wang, Z., Ye, Y.: Complexity of unconstrained \(l_2-l_p\) minimization. Math. Program. 143, 371–383 (2014)MathSciNetCrossRefMATH

15.

Daubechies, I., Defrise, M., Mol, C.D.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57, 1413–1457 (2004)MathSciNetCrossRefMATH

16.

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

17.

Donoho, D.L.: High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension. Dis. Comput. Geom. 35, 617–652 (2006)MathSciNetCrossRefMATH

18.

Esser, E., Lou, Y., Xin, J.: A method for finding structured sparse solutions to nonnegative least squares problems with applications. SIAM J. Imag. Sci. 6, 2010–2046 (2013)MathSciNetCrossRefMATH

19.

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

20.

Ge, D., Jiang, X., Ye, Y.: A note on the complexity of \(l_p\) minimization. Math. Program. 21, 1721–1739 (2011)

21.

Krishnan, D., Fergus, R.: Fast image deconvolution using hyper-laplacian priors. Adv. Neural. Inf. Process. Syst. 22, 1033–1041 (2009)

22.

Lee, H., Battle, A., Raina, R., Ng, A. Y.: Efficient sparse coding algorithms, In Advances in Neural Information Processing Systems, MIT Press: Vancourver, Canada, (2006), pp. 801–808

23.

Lanza, A., Morigi, S., Reichel, L., Sgallari, F.: A generalized Krylov subspace method for \(\ell _p-\ell _q\) minimization. SIAM J. Sci. Comput. 37(5), S30–S50 (2015)CrossRefMATH

24.

Meinshausen, N., Yu, B., et al.: Lasso-type recovery of sparse representations for high-dimensional data. Ann. Stat. 37, 246–270 (2009)MathSciNetCrossRefMATH

25.

Mallat, S. G., Zhang, Z.: Matching pursuits with time-frequency dictionaries, IEEE Transactions on signal processing, 41.12(1993):pp.3397–3415

26.

Needell, D., Vershynin, R.: Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. IEEE J. Select.Top. Sig. Proc. 4, 310–316 (2010)CrossRef

27.

Needell, D. , Tropp, J. A.: CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl .Comput. Harm. Anal., 26.3(2009):pp.301–321

28.

Nocedal, J., Wright, S.: Numerical optimization (1999) Springer. New York

29.

Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103, 127–152 (2005)MathSciNetCrossRefMATH

30.

Nesterov, Y., et al.: Gradient methods for minimizing composite function. Math. Program. 140, 125–161 (2013)MathSciNetCrossRefMATH

31.

Natraajan, B.K.: Sparse approximation to linear systems. SIAM J. Comput. 24(2), 227–234 (1995)MathSciNetCrossRef

32.

Olshausen, B.A., Field, D.J.: Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature 381, 607–609 (1996)CrossRef

33.

Tibshirani, R.: Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society. Ser. B (Methodological), (1996), pp. 267–288

34.

Tropp, J. A., Gilbert, A. C.: Signal recovery from partial information via orthogonal matching pursuit, IEEE Trans. Inf. Theory, 53.12(2007):pp.4655–4666

35.

Wang, G., Wei, X., Yu, B., Xu, L.: An efficient proximal block coordinate homotopy method for large-scale sparse least squares problems. SIAM J. Sci. Comput. 42, A395–A423 (2020)MathSciNetCrossRefMATH

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, 1013–1027 (2012)CrossRef

37.

Xu, Z.B., Zhang, H., Wang, Y., Chang, X.Y., Yong, L.: \(l_{1/2}\) regularization, science China. Inf. Sci. 53, 1159–1169 (2010)MATH

38.

Xu, Z. B., Guo, H., Wang, Y., Zhang, H.: The representation of \(L_{1/2}\) regularizer among \(L_q\)\((0 < q < 1)\)regularizer: An experimental study based on phase diagram, Acta Autom. Sinica, (2011), to be published

39.

Xie, L. L.: A new algorithm for fast solving\(L_{1/2}\)-regularized problem (in Chinese), Master Thesis of Dalian University of Technology, (2014)

40.

Yuan, G.X., Chang, K.W., Hsieh, C.J., Lin, C.J.: A comparison of optimization methods and software for large-scale \(l_1\)-regularized linear classification. J. Mach. Learn. Res. 11, 3183–3234 (2010)MathSciNetMATH

41.

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

42.

Xu, Z., Liang, G., Yao, W., Zhang, H.: Representative of \(l_{1/2}\) regularization among \(L_q\)\((0< q\le 1)\) regularizations: an experimental study based on phase diagram. Acta Automatica Sinica 38, 1225–1228 (2012)MathSciNet

43.

Zeng, J., Xu, Z., Zhang, B., Hong, W., Wu, Y.: Accelerated \(l_{1/2}\) regularization based sar imaging via bcr and reduced newton skills. Signal Process. 93, 1831–1844 (2013)CrossRef

44.

Zhang, Y., Lee, J. D., Jordan, M. I.: \(l_1\)-regularized neural networks are improperly learnable in polynomial time, in International Conference on Machine Learning, PMLR, (2016), pp. 993–1001

45.

Zou, H.: The adaptive lasso and its oracle properties. J. Am. Stat. Assoc. 101, 1418–1429 (2006)MathSciNetCrossRefMATH

Title: A Reduced Half Thresholding Algorithm
Authors: Xiubo Liang
Guoqiang Wang
Bo Yu
Publication date: 01-08-2023
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 2/2023
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-023-02250-1

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/2023

Stability and Error Estimates of Local Discontinuous Galerkin Methods with Implicit–Explicit Backward Difference Formulas up to Fifth Order for Convection–Diffusion Equation

Discontinuous Galerkin and Related Methods for ODE

Correction to: A Line Search Based Proximal Stochastic Gradient Algorithm with Dynamical Variance Reduction

A Convergent Iterative Support Shrinking Algorithm for Non-Lipschitz Multi-phase Image Labeling Model

New Low-Dissipation Central-Upwind Schemes

Fast Gradient Method for Low-Rank Matrix Estimation

Premium Partner