Top

Journal of Combinatorial Optimization

Published in:

08-04-2020

Weighted thresholding homotopy method for sparsity constrained optimization

Authors: Wenxing Zhu, Huating Huang, Lanfan Jiang, Jianli Chen

Published in: Journal of Combinatorial Optimization | Issue 3/2022

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

search-config

AI-assisted search

Off

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.

previous article A primal-dual algorithm for the minimum power partial cover problem

next article Capacitated vehicle routing problem on line with unsplittable demands

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

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

Title: Weighted thresholding homotopy method for sparsity constrained optimization
Authors: Wenxing Zhu
Huating Huang
Lanfan Jiang
Jianli Chen
Publication date: 08-04-2020
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2022
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00563-7

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

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

Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties

Bipartite communities via spectral partitioning

The bi-criteria seeding algorithms for two variants of k-means problem

Capacitated vehicle routing problem on line with unsplittable demands

Computation and algorithm for the minimum k-edge-connectivity of graphs

Premium Partner