{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T14:41:46Z","timestamp":1781275306082,"version":"3.54.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T00:00:00Z","timestamp":1616112000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T00:00:00Z","timestamp":1616112000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008991","name":"Universit\u00e0 degli Studi Roma Tre","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008991","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a novel differentiable reformulation of the linearly-constrained<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u2113<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>minimization problem, also known as the basis pursuit problem. The reformulation is inspired by the Laplacian paradigm of network theory and leads to a new family of gradient-based methods for the solution of<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u2113<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>minimization problems. We analyze the iteration complexity of a natural solution approach to the reformulation, based on a multiplicative weights update scheme, as well as the iteration complexity of an accelerated gradient scheme. The results can be seen as bounds on the complexity of iteratively reweighted least squares (IRLS) type methods of basis pursuit.<\/jats:p>","DOI":"10.1007\/s10589-021-00270-x","type":"journal-article","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T13:04:49Z","timestamp":1616159089000},"page":"441-469","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Laplacian approach to $$\\ell _1$$-norm minimization"],"prefix":"10.1007","volume":"79","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9038-6901","authenticated-orcid":false,"given":"Vincenzo","family":"Bonifaci","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,3,19]]},"reference":[{"issue":"2","key":"270_CR1","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/S0363012902419977","volume":"43","author":"F Alvarez","year":"2004","unstructured":"Alvarez, F., Bolte, J., Brahic, O.: Hessian Riemannian gradient flows in convex programming. SIAM J. Control Optim. 43(2), 477\u2013501 (2004)","journal-title":"SIAM J. Control Optim."},{"key":"270_CR2","volume-title":"Inf. Geom. Appl.","author":"S Amari","year":"2016","unstructured":"Amari, S.: Information Geometry and Its Applications. Springer, Berlin (2016)"},{"issue":"1","key":"270_CR3","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory Comput. 8(1), 121\u2013164 (2012)","journal-title":"Theory Comput."},{"issue":"1","key":"270_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000015","volume":"4","author":"F Bach","year":"2012","unstructured":"Bach, F., Jenatton, R., Mairal, J., Obozinski, G.: Optimization with sparsity-inducing penalties. Found. Trends Mach. Learn. 4(1), 1\u2013106 (2012)","journal-title":"Found. Trends Mach. Learn."},{"issue":"4","key":"270_CR5","first-page":"1","volume":"15","author":"N Bansal","year":"2019","unstructured":"Bansal, N., Gupta, A.: Potential-function proofs for gradient methods. Theory Comput. 15(4), 1\u201332 (2019)","journal-title":"Theory Comput."},{"issue":"2","key":"270_CR6","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1287\/moor.2016.0817","volume":"42","author":"H Bauschke","year":"2017","unstructured":"Bauschke, H., Bolte, J., Teboulle, M.: A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications. Math. Oper. Res. 42(2), 330\u2013348 (2017)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"270_CR7","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1137\/13094829X","volume":"25","author":"A Beck","year":"2015","unstructured":"Beck, A.: On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes. SIAM J Optim. 25(1), 185\u2013209 (2015)","journal-title":"SIAM J Optim."},{"key":"270_CR8","doi-asserted-by":"crossref","unstructured":"Beck, A.: First-Order Methods in Optimization. SIAM, Philadelphia, PA (2017)","DOI":"10.1137\/1.9781611974997"},{"issue":"3","key":"270_CR9","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0167-6377(02)00231-6","volume":"31","author":"A Beck","year":"2003","unstructured":"Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3), 167\u2013175 (2003)","journal-title":"Oper. Res. Lett."},{"key":"270_CR10","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.tcs.2018.08.027","volume":"773","author":"R Becker","year":"2019","unstructured":"Becker, R., Bonifaci, V., Karrenbauer, A., Kolev, P., Mehlhorn, K.: Two results on slime mold computations. Theor. Comput. Sci. 773, 79\u2013106 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"270_CR11","doi-asserted-by":"publisher","first-page":"107417","DOI":"10.1016\/j.sigpro.2019.107417","volume":"169","author":"A Benfenati","year":"2020","unstructured":"Benfenati, A., Chouzenoux, \u00c9., Pesquet, J.: Proximal approaches for matrix optimization problems: Application to robust precision matrix estimation. Signal Process. 169, 107417 (2020)","journal-title":"Signal Process."},{"key":"270_CR12","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Springer, New York, NY (1998)","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"270_CR13","unstructured":"Bonifaci, V.: On the convergence time of a natural dynamics for linear programming. In Proc. of the 28th Int. Symposium on Algorithms and Computation, pages 17:1\u201317:12. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl (2017)"},{"key":"270_CR14","unstructured":"Bonifaci, V.: MATLAB implementation of Laplacian-based gradient methods for L1-norm minimization. http:\/\/ricerca.mat.uniroma3.it\/users\/vbonifaci\/soft\/l1opt.zip, (2020)"},{"key":"270_CR15","doi-asserted-by":"crossref","unstructured":"Bonifaci, V., Mehlhorn, K., Varma, G.: Physarum can compute shortest paths. In Proc. of the 23rd ACM-SIAM Symposium on Discrete Algorithms, pages 233\u2013240. SIAM, (2012)","DOI":"10.1137\/1.9781611973099.21"},{"key":"270_CR16","unstructured":"Boyd, S., Vanderberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"issue":"268","key":"270_CR17","doi-asserted-by":"publisher","first-page":"2127","DOI":"10.1090\/S0025-5718-09-02242-X","volume":"78","author":"J Cai","year":"2009","unstructured":"Cai, J., Osher, S.J., Shen, Z.: Convergence of the linearized Bregman iteration for $$\\ell _1$$-norm minimization. Math. Comput. 78(268), 2127\u20132136 (2009)","journal-title":"Math. Comput."},{"key":"270_CR18","unstructured":"Cand\u00e8s, E., Romberg, J.: $$\\ell _1$$-magic: Recovery of sparse signals via linear programming. https:\/\/statweb.stanford.edu\/ candes\/l1magic\/downloads\/l1magic.pdf, (2005)"},{"key":"270_CR19","doi-asserted-by":"crossref","unstructured":"Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In Proc. of IEEE Int. Conf. on Acoustics, Speech and Signal Processing, pages 3869\u20133872. IEEE, (2008)","DOI":"10.1109\/ICASSP.2008.4518498"},{"issue":"1","key":"270_CR20","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1137\/S003614450037906X","volume":"43","author":"SS Chen","year":"2001","unstructured":"Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM Rev. 43(1), 129\u2013159 (2001)","journal-title":"SIAM Rev."},{"key":"270_CR21","doi-asserted-by":"crossref","unstructured":"Chin, H.H., Madry, A., Miller, G.L., Peng, R.: Runtime guarantees for regression problems. In Proc. of Innovations in Theoretical Computer Science, pages 269\u2013282. ACM, (2013)","DOI":"10.1145\/2422436.2422469"},{"key":"270_CR22","doi-asserted-by":"crossref","unstructured":"Christiano, P., Kelner, J.A., Madry, A., Spielman, D.A., Teng, S.-H.: Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proc. of the 43rd ACM Symp. on Theory of Computing, pages 273\u2013282. ACM, (2011)","DOI":"10.1145\/1993636.1993674"},{"issue":"1","key":"270_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/cpa.20303","volume":"63","author":"I Daubechies","year":"2010","unstructured":"Daubechies, I., DeVore, R., Fornasier, M., G\u00fcnt\u00fcrk, C.: Iteratively reweighted least squares minimization for sparse recovery. Comm. on Pure Appl. Math. 63(1), 1\u201338 (2010)","journal-title":"Comm. on Pure Appl. Math."},{"issue":"6","key":"270_CR24","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1002\/cpa.20132","volume":"59","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: For most large underdetermined systems of linear equations the minimal $$\\ell _1$$-norm solution is also the sparsest solution. Commun. Pure Appl. Math. 59(6), 797\u2013829 (2006)","journal-title":"Commun. Pure Appl. Math."},{"key":"270_CR25","unstructured":"Ene, A., Vladu, A.: Improved convergence for $$\\ell _1$$ and $$\\ell _\\infty$$ regression via iteratively reweighted least squares. In Proceedings of the 36th International Conference on Machine Learning, pages 1794\u20131801, (2019)"},{"key":"270_CR26","unstructured":"Facca, E., Cardin, F., Putti, M.: Physarum dynamics and optimal transport for basis pursuit. arXiv:1812.11782v1 [math.NA], (2019)"},{"key":"270_CR27","doi-asserted-by":"crossref","unstructured":"Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Birkh\u00e4user, New York, NY (2013)","DOI":"10.1007\/978-0-8176-4948-7"},{"issue":"1","key":"270_CR28","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1137\/050645452","volume":"50","author":"A Ghosh","year":"2008","unstructured":"Ghosh, A., Boyd, S., Saberi, A.: Minimizing effective resistance of a graph. SIAM Rev. 50(1), 37\u201366 (2008)","journal-title":"SIAM Rev."},{"key":"270_CR29","doi-asserted-by":"crossref","unstructured":"Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, Berlin (2001)","DOI":"10.1007\/978-1-4613-0163-9"},{"issue":"4","key":"270_CR30","doi-asserted-by":"publisher","first-page":"2675","DOI":"10.1109\/TIT.2018.2800768","volume":"64","author":"T Goldstein","year":"2018","unstructured":"Goldstein, T., Studer, C.: Phasemax: Convex phase retrieval via basis pursuit. IEEE Trans. Inf. Theory 64(4), 2675\u20132689 (2018)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"270_CR31","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1111\/j.2517-6161.1984.tb01288.x","volume":"46","author":"PJ Green","year":"1984","unstructured":"Green, P.J.: Iteratively reweighted least squares for maximum likelihood estimation, and some robust and resistant alternatives. J. R. Statist. Soc., Series B 46(2), 149\u2013192 (1984)","journal-title":"J. R. Statist. Soc., Series B"},{"key":"270_CR32","doi-asserted-by":"crossref","unstructured":"Hofbauer, J., Sigmund, K.: Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge (1998)","DOI":"10.1017\/CBO9781139173179"},{"key":"270_CR33","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (2013)"},{"key":"270_CR34","doi-asserted-by":"crossref","unstructured":"Kao, J., Tian, D., Mansour, H., Ortega, A., Vetro, A.: Disc-glasso: Discriminative graph learning with sparsity regularization. In Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing, pages 2956\u20132960. IEEE (2017)","DOI":"10.1109\/ICASSP.2017.7952698"},{"issue":"1","key":"270_CR35","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/16M1099546","volume":"28","author":"H Lu","year":"2018","unstructured":"Lu, H., Freund, R.M., Nesterov, Y.: Relatively smooth convex optimization by first-order methods, and applications. SIAM J. Optim. 28(1), 333\u2013354 (2018)","journal-title":"SIAM J. Optim."},{"key":"270_CR36","doi-asserted-by":"crossref","unstructured":"Magnus, J.R., Neudecker, H.: Matrix Differential Calculus with Applications in Statistics and Econometrics. Wiley, Oxford (2019)","DOI":"10.1002\/9781119541219"},{"key":"270_CR37","doi-asserted-by":"publisher","first-page":"2125","DOI":"10.1214\/12-EJS740","volume":"6","author":"R Mazumder","year":"2012","unstructured":"Mazumder, R., Hastie, T.: The graphical lasso: New insights and alternatives. Electron. J. Statist. 6, 2125\u20132149 (2012)","journal-title":"Electron. J. Statist."},{"issue":"1","key":"270_CR38","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y Nesterov","year":"2005","unstructured":"Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127\u2013152 (2005)","journal-title":"Math. Program."},{"key":"270_CR39","unstructured":"Osborne, M.R.: Finite Algorithms in Optimization and Data Analysis. Wiley, Oxford (1985)"},{"key":"270_CR40","unstructured":"Rao, C., Toutenburg, H., Heumann, S.: Linear Models and Generalizations. Springer, Berlin (2008)"},{"key":"270_CR41","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton, NJ (1970)"},{"key":"270_CR42","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.amc.2019.02.073","volume":"355","author":"T Saha","year":"2019","unstructured":"Saha, T., Srivastava, S., Khare, S., Stanimirovic, P.S., Petkovic, M.D.: An improved algorithm for basis pursuit problem and its applications. Appl. Math. Comput. 355, 385\u2013398 (2019)","journal-title":"Appl. Math. Comput."},{"key":"270_CR43","unstructured":"Straszak, D., Vishnoi, N.K.: IRLS and slime mold: Equivalence and convergence. arXiv:1601.02712 [cs.DS], (2016)"},{"key":"270_CR44","doi-asserted-by":"crossref","unstructured":"Straszak, D., Vishnoi, N.K.: Natural algorithms for flow problems. In Proc. of the 27th ACM-SIAM Symposium on Discrete Algorithms, pages 1868\u20131883. SIAM, (2016)","DOI":"10.1137\/1.9781611974331.ch131"},{"key":"270_CR45","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/j.jtbi.2006.07.015","volume":"244","author":"A Tero","year":"2007","unstructured":"Tero, A., Kobayashi, R., Nakagaki, T.: A mathematical model for adaptive transport network in path finding by true slime mold. J. Theor. Biol. 244, 553\u2013564 (2007)","journal-title":"J. Theor. Biol."},{"key":"270_CR46","unstructured":"Wilson, A.: Lyapunov arguments in optimization. Ph.D. dissertation, University of California at Berkeley, (2018)"},{"issue":"8","key":"270_CR47","doi-asserted-by":"publisher","first-page":"3234","DOI":"10.1109\/TIP.2013.2262292","volume":"22","author":"AY Yang","year":"2013","unstructured":"Yang, A.Y., Zhou, Z., Balasubramanian, A.G., Sastry, S.S., Ma, Y.: Fast $$\\ell _1$$-minimization algorithms for robust face recognition. IEEE Trans. Image Process. 22(8), 3234\u20133246 (2013)","journal-title":"IEEE Trans. Image Process."},{"issue":"1","key":"270_CR48","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/070703983","volume":"1","author":"W Yin","year":"2008","unstructured":"Yin, W., Osher, S.J., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for $$\\ell _1$$-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1(1), 143\u2013168 (2008)","journal-title":"SIAM J. Imaging Sci."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00270-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-021-00270-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00270-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T10:56:38Z","timestamp":1724669798000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-021-00270-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,19]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["270"],"URL":"https:\/\/doi.org\/10.1007\/s10589-021-00270-x","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,19]]},"assertion":[{"value":"9 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}