nach oben

Journal of Combinatorial Optimization

Erschienen in:

08.04.2020

Weighted thresholding homotopy method for sparsity constrained optimization

verfasst von: Wenxing Zhu, Huating Huang, Lanfan Jiang, Jianli Chen

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We propose in this paper a novel weighted thresholding method for the sparsity-constrained optimization problem. By reformulating the problem equivalently as a mixed-integer programming, we investigate the Lagrange duality with respect to an \(l_1\)-norm constraint and show the strong duality property. Then we derive a weighted thresholding method for the inner Lagrangian problem, and analyze its convergence. In addition, we give an error bound of the solution under some assumptions. Further, based on the proposed method, we develop a homotopy algorithm with varying sparsity level and Lagrange multiplier, and prove that the algorithm converges to an L-stationary point of the primal problem under some conditions. Computational experiments show that the proposed algorithm is competitive with state-of-the-art methods for the sparsity-constrained optimization problem.

Vorheriger Artikel A primal-dual algorithm for the minimum power partial cover problem

Nächster Artikel Capacitated vehicle routing problem on line with unsplittable demands

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

MATLAB packages for NIHT and AIHT: http://www.personal.soton.ac.uk/tb1m08/sparsify/sparsify.html.

MATLAB packages for ECME and DORE: http://home.eng.iastate.edu/~ald/DORE.htm.

MATLAB package for GraSP: http://sbahmani.ece.gatech.edu/GraSP.html.

Bahmani S, Raj B, Boufounos P (2013) Greedy sparsity-constrained optimization. J Mach Learn Res 14(1):807–841MathSciNetMATH

Beck A, Hallak N (2016) On the minimization over sparse symmetric sets: projections, optimality conditions, and algorithms. Math Oper Res 41(1):196–223MathSciNetCrossRef

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

Bi S, Liu X, Pan S (2014) Exact Penalty Decomposition Method for Zero-Norm Minimization Based on MPEC Formulation. SIAM J Sci Comput 36(4):A1451–A1477MathSciNetCrossRef

Blumensath T (2012) Accelerated iterative hard thresholding. Sig Process 92(3):752–756CrossRef

Blumensath T, Davies ME (2008) Iterative thresholding for sparse approximations. J Fourier Anal Appl 14(5–6):629–654MathSciNetCrossRef

Blumensath T, Davies ME (2010) Normalised itertive hard thresholding: guaranteed stability and performance. IEEE J Sel Top Signal Process 4(2):298–309CrossRef

Candès EJ, Tao T (2005) Decoding by linear programming. IEEE Trans Inf Theory 51(12):4203–4215MathSciNetCrossRef

Candès EJ, Wakin MB, Boyd SP (2008) Enhancing sparsity by reweighted \(l_1\) minimization. J Fourier Anal Appl 14(5–6):877–905MathSciNetCrossRef

Chen Y, Ye Y, Wang M (2019) Approximation hardness for a class of sparse optimization problems. J Mach Learn Res 20:1–27MathSciNetMATH

Dong Z, Zhu W (2018) Homotopy methods based on \(l_0\) norm for the compressed sensing problem. IEEE Trans Neural Netw Learn Syst 29(4):1132–1146CrossRef

Donoho DL, Tsaig Y (2008) Fast solution of \(l_1\)-norm minimization problems when the solution may be sparse. IEEE Trans Inf Theory 54(11):4789–4812CrossRef

Elad M (2010) Sparse and redundant representations: from theory to applications in signal and image processing. Springer, New YorkCrossRef

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

Friedman J, Hastie T, Tibshirani R (2010) Regularization paths for generalized linear models via coordinate descent. J Stat Softw 33(1):1–22CrossRef

Guyon I, Gunn S, Ben-Hur A, Dror G (2005) Result analysis of the nips 2003 feature selection challenge. In: Saul LK, Weiss Y, Bottou L (eds) Advances in neural information processing system 17. MIT-Press, Cambridge, MA, pp 545–552

Jain P, Rao N, Dhillon I (2016) Structured sparse regression via greedy hard-thresholding. In: Advances in neural information processing systems (NIPS), pp 1516–1524

Jiao Y, Jin B, Lu X (2015) A primal dual active set with continuation algorithm for the \(l_0\)-regularized optimization problem. Appl Comput Harmon Anal 39(3):400–426MathSciNetCrossRef

Khajehnejad MA, Xu W, Avestimehr AS, Hassibi B (2009) Weighted \(l_1\) minimization for sparse recovery with prior information. In 2009 IEEE international conference on symposium on information theory, pp 483–487

Koh K, Kim S, Boyd S (2007) An interior-point method for large-scale \(l_1\)-regularized logistic regression. J Mach Learn Res 8:1519–1555MathSciNetMATH

Li Q, Bai Y, Yu C, Yuan Y-X (2019) A new piecewise quadratic approximation approach for \(l_0\) norm minimization problem. Sci China Math 62(1):185–204MathSciNetCrossRef

Li X, Zhao T, Arora R, Liu H, Haupt J (2016) Stochastic variance reduced optimization for nonconvex sparse learning. In: International conference on machine learning (ICML), pp 917–925

Liu B, Yuan X, Wang L, Liu Q, Metaxas DN (2017) Dual iterative hard thresholding: from non-convex sparse minimization to non-smooth concave maximization. In: International conference on machine learning (ICML), pp 2179–2187

Liu Y, Bi S, Pan S (2018) Equivalent Lipschitz surrogates for zero-norm and rank optimization problems. J Global Optim 72(4):679–704MathSciNetCrossRef

Lu Z (2014) Iterative hard thresholding methods for \(l_0\) regularized convex cone programming. Math Program 147(1–2):125–154MathSciNetCrossRef

Lu Z, Zhang Y (2013) Sparse approximation via penalty decomposition methods. SIAM J Optim 23(4):2448–2478MathSciNetCrossRef

Mairal J, Bach F, Ponce J (2014) Sparse modeling for image and vision processing. Found Trends Comput Graphics Vis 8(2–3):85–283CrossRef

Mallat S, Zhang Z (1993) Matching pursuits with time-frequency dictionaries. IEEE Trans Signal Process 41(12):3397–3415CrossRef

Needell D, Tropp JA (2009) Cosamp: iterative signal recovery from incomplete and inaccurate samples. Appl Comput Harmon Anal 26(3):301–321MathSciNetCrossRef

Newman D, Hrttich S, Blake C, Merz C (1998) UCI repository of machine learing databases. www.ics.uci.edu/~mlearn/MLRepository.html

Nguyen N, Needell D, Woolf T (2017) Linear convergence of stochastic iterative greedy algorithms with sparse constraints. IEEE Trans Inf Theory 63(11):6869–6895MathSciNetCrossRef

Qiu K, Dogandžić A (2012) Sparse signal reconstruction via ecme hard thresholding. IEEE Trans Signal Process 60(9):4551–4569MathSciNetCrossRef

Rakotomamonjy A, Koco S, Ralaivola L (2017) Greedy methods, randomization approaches, and multiarm bandit algorithms for efficient sparsity-constrained optimization. IEEE Trans Neural Netw Learn Syst 28(11):2789–2802MathSciNetCrossRef

Shen X, Pan W, Zhu Y, Zhou H (2013) On constrained and regularized high-dimensional regression. Ann Inst Stat Math 65(5):807–832MathSciNetCrossRef

Soussen C, Idier J, Duan J, Brie D (2015) Homotopy based algorithms for \(l_0\)-regularized least-squares. IEEE Trans Signal Process 63(13):3301–3316MathSciNetCrossRef

Tropp JA, Gilbert AC (2007) Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans Inf Theory 53(12):4655–4666MathSciNetCrossRef

Xiang S, Shen X, Ye J (2015) Efficient nonconvex sparse group feature selection via continuous and discrete optimization. Artif Intell 224:28–50MathSciNetCrossRef

Xiao L, Zhang T (2013) A proximal-gradient homotopy method for the sparse least-squares problem. SIAM J Optim 23(2):1062–1091MathSciNetCrossRef

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

Yuan X, Li P, Zhang T (2018) Gradient hard thresholding pursuit. J Mach Learn Res 18:1–43MathSciNetMATH

Zhang C-H, Zhang T (2012) A general theory of concave regularization for high-dimensional sparse estimation problems. Stat Sci 27(4):576–593MathSciNetCrossRef

Zhang T (2010) Analysis of multi-stage convex relaxation for sparse regularization. J Mach Learn Res 11:1081–1107MathSciNetMATH

Zhang Z, Xu Y, Yang J, Li X, Zhang D (2015) A survey of sparse representation: algorithms and applications. IEEE Access 3:490–530CrossRef

Zhao Y (2018) Sparse optimization theory and methods. CRC Press/Taylor and Francis Group, Boca RatonCrossRef

Zhao Y, Li D (2012) Reweighted \(l_1\)-minimization for sparse solutions to underdetermined linear systems. SIAM J Optim 22(3):1065–1088MathSciNetCrossRef

Titel: Weighted thresholding homotopy method for sparsity constrained optimization
verfasst von: Wenxing Zhu
Huating Huang
Lanfan Jiang
Jianli Chen
Publikationsdatum: 08.04.2020
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2022
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00563-7

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 3/2022

An approximation algorithm for stochastic multi-level facility location problem with soft capacities

The price of fairness for a two-agent scheduling game minimizing total completion time

Approximation algorithms for constructing required subgraphs using stock pieces of fixed length

On the approximability of Time Disjoint Walks

On metric dimension of plane graphs with number of 10 sided faces

Atomic congestion games with random players: network equilibrium and the price of anarchy

Premium Partner