research-article

Iteratively reweighted least squares and slime mold dynamics: connection and convergence

Authors:

Damian Straszak,

Nisheeth K. VishnoiAuthors Info & Claims

Mathematical Programming, Volume 194, Issue 1-2

Pages 685 - 717

https://doi.org/10.1007/s10107-021-01644-z

Published: 01 July 2022 Publication History

Abstract

We present a connection between two dynamical systems arising in entirely different contexts: the Iteratively Reweighted Least Squares (IRLS) algorithm used in compressed sensing and sparse recovery to find a minimum

ℓ_{1}

-norm solution in an affine space, and the dynamics of a slime mold (Physarum polycephalum) that finds the shortest path in a maze. We elucidate this connection by presenting a new dynamical system – Meta-Algorithm – and showing that the IRLS algorithms and the slime mold dynamics can both be obtained by specializing it to disjoint sets of variables. Subsequently, and building on work on slime mold dynamics for finding shortest paths, we prove convergence and obtain complexity bounds for the Meta-Algorithm that can be viewed as a “damped” version of the IRLS algorithm. A consequence of this latter result is a slime mold dynamics to solve the undirected transshipment problem that computes a

(1 + ε) -

approximate solution in time polynomial in the size of the input graph, maximum edge cost, and

\frac{1}{ε}

– a problem that was left open by the work of (Bonifaci V et al. [10] Physarum can compute shortest paths. Kyoto, Japan, pp. 233–240).

References

[1]

Adil, D., Kyng, R., Peng, R., Sachdeva, S.: Iterative refinement for

ℓ_{p}

-norm regression. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 1405–1424 (2019).

[2]

Adil, D., Peng, R., Sachdeva, S.: Fast, provably convergent IRLS algorithm for p-norm linear regression. In: H.M. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E.B. Fox, R. Garnett (eds.) Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 14166–14177 (2019). URL http://papers.nips.cc/paper/9565-fast-provably-convergent-irls-algorithm-for-p-norm-linear-regression

[3]

Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., Bar-Joseph, Z.: A biological solution to a fundamental distributed computing problem. Science 331(6014), 183–185 (2011). URL http://science.sciencemag.org/content/331/6014/183

[4]

Ba DE, Babadi B, Purdon PL, and Brown EN Convergence and stability of iteratively re-weighted least squares algorithms IEEE Trans. Signal Process. 2014 62 1 183-195

[5]

Becchetti, L., Bonifaci, V., Dirnberger, M., Karrenbauer, A., Mehlhorn, K.: Physarum can compute shortest paths: Convergence proofs and complexity bounds. In: Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II, pp. 472–483 (2013)

[6]

Becchetti, L., Bonifaci, V., Dirnberger, M., Karrenbauer, A., Mehlhorn, K.: Physarum can compute shortest paths: Convergence proofs and complexity bounds. In: Full version (2014)

[7]

Beck A On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes SIAM J. Opt. 2015 25 1 185-209

[8]

Becker R, Bonifaci V, Karrenbauer A, Kolev P, and Mehlhorn K Two results on slime mold computations Theor. Comput. Sci. 2019 773 79-106

[9]

Bissantz N, Dümbgen L, Munk A, and Stratmann B Convergence analysis of generalized iteratively reweighted least squares algorithms on convex function spaces SIAM J. Opt. 2009 19 4 1828-1845

[10]

Bonifaci, V., Mehlhorn, K., Varma, G.: Physarum can compute shortest paths. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pp. 233–240 (2012)

[11]

Brimberg J and Love RF Global convergence of a generalized iterative procedure for the minisum location problem with lp distances Oper. Res. 1993 41 6 1153-1163

[12]

Bubeck, S., Cohen, M.B., Lee, Y.T., Li, Y.: An homotopy method for

ℓ_{p}

regression provably beyond self-concordance and in input-sparsity time. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pp. 1130–1137 (2018).

[13]

Burrus, C.: Iterative reweighted least squares (2012). URL https://cnx.org/contents/krkDdys0@12/Iterative-Reweighted-Least-Squares

[14]

Burrus CS, Barreto JA, and Selesnick IW Iterative reweighted least-squares design of FIR filters IEEE Trans. Signal Process. 1994 42 11 2926-2936

[15]

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

[16]

Candès E and Tao T Decoding by linear programming Inf. Theor., IEEE Trans. 2005 51 12 4203-4215

[17]

Cardelli L and Csikász-Nagy A The cell cycle switch computes approximate majority Sci. Rep. 2012 2 656

[18]

Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: Acoustics, Speech and Signal Processing, 2008. ICASSP 2008. IEEE International Conference on, pp. 3869–3872 (2008)

[19]

Chastain, E., Livnat, A., Papadimitriou, C., Vazirani, U.: Algorithms, games, and evolution. Proceedings of the National Academy of Sciences 111(29), 10620–10623 (2014). URL http://www.pnas.org/content/111/29/10620.abstract

[20]

Chazelle B Natural algorithms and influence systems Commun. ACM 2012 55 12 101-110

[21]

Chen C, He L, Li H, and Huang J Fast iteratively reweighted least squares algorithms for analysis-based sparse reconstruction Med. Image Analyt. 2018 49 141-152

[22]

Cook W, Cunningham W, Pulleyblank W, and Schrijver A Comb. opt. 1998 New York wiley

[23]

Daitch, S.I., Spielman, D.A.: Faster approximate lossy generalized flow via interior point algorithms. In: C. Dwork (ed.) Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pp. 451–460. ACM (2008).

[24]

Daubechies I, DeVore R, Fornasier M, and Güntürk CS Iteratively reweighted least squares minimization for sparse recovery Commun. Pure Appl. Math. 2010 63 1 1-38

[25]

Dong, H., Yang, L.: Iteratively reweighted least squares for robust regression via SVM and ELM. CoRR abs/1903.11202 (2019). URL http://arxiv.org/abs/1903.11202

[26]

Donoho, D.L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via

ℓ_{1}

minimization. Proceedings of the National Academy of Sciences 100(5), 2197–2202 (2003). URL http://www.pnas.org/content/100/5/2197.abstract

[27]

Donoho DL and Huo X Uncertainty principles and ideal atomic decomposition IEEE Trans. Inf. Theor. 2001 47 7 2845-2862

[28]

Eiben AE and Smith J From evolutionary computation to the evolution of things Nature 2015 521 7553 476-482

[29]

Ene, A., Vladu, A.: Improved convergence for

ℓ_{1}

and

ℓ_{\infty}

regression via iteratively reweighted least squares. In: Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 1794–1801 (2019). URL http://proceedings.mlr.press/v97/ene19a.html

[30]

Even S and Tarjan RE Network flow and testing graph connectivity SIAM J. Comput. 1975 4 4 507-518

[31]

Facca E, Cardin F, and Putti M Towards a stationary monge-kantorovich dynamics: The physarum polycephalum experience SIAM J. Appl. Math. 2018 78 2 651-676

[32]

Facca E, Karrenbauer A, Kolev P, and Mehlhorn K Convergence of the non-uniform directed physarum model Theor. Comput. Sci. 2020 816 184-194

[33]

Ford L and Fulkerson D Maximal flow through a network Canad. J. Math. 1956 8 399-404

[34]

Goldberg AV and Rao S Beyond the flow decomposition barrier J. ACM 1998 45 5 783-797

[35]

Gordon, D.M.: Ant Encounters: Interaction Networks and Colony Behavior. Primers in Complex Systems. Princeton University Press (2010). URL https://books.google.ch/books?id=MabwdXLZ9YMC

[36]

Gorodnitsky I and Rao B Sparse signal reconstruction from limited data using focuss: A re-weighted minimum norm algorithm Trans. Signal Proc. 1997 45 3 600-616

[37]

Green P Iteratively reweighted least squares for maximum likelihood estimation, and some robust and resistant alternatives (with discussion) J. Royal Statist. Soc., Series B: Methodol. 1984 46 149-192

[38]

Hopcroft JE and Karp RM An

n^{5 / 2}

algorithm for maximum matchings in bipartite graphs SIAM J. comput. 1973 2 4 225-231

[39]

Johannson, A., Zou, J.: A slime mold solver for linear programming problems. In: How the World Computes. Lecture Notes in Computer Science, vol. 7318, pp. 344–354. Springer, Berlin Heidelberg (2012)

[40]

Karam LJ and McClellan JH Complex chebyshev approximation for fir filter design IEEE Trans. Circuits Syst. II: Anal. Digit. Signal Process. 1995 42 3 207-216

[41]

Karlovitz L Construction of nearest points in the

l^{p}

,

p

even, and

l^{\infty}

norms. i J. Approx. Theor. 1970 3 2 123-127

[42]

Karrenbauer A, Kolev P, and Mehlhorn K Convergence of the non-uniform physarum dynamics Theor. Comput. Sci. 2020 816 260-269

[43]

Lecun Y, Bengio Y, and Hinton G Deep learning Nature 2015 521 7553 436-444

[44]

Lee, Y.T., Sidford, A.: Path finding methods for linear programming: Solving linear programs in

O (\sqrt{rank})

iterations and faster algorithms for maximum flow. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pp. 424–433 (2014).

[45]

Miyaji T and Ohnishi I Physarum can solve the shortest path problem on riemannian surface mathematically rigourously Int. J. Pure Appl. Matt. 2008 47 3 353-369

[46]

Mukhoty, B., Gopakumar, G., Jain, P., Kar, P.: Globally-convergent iteratively reweighted least squares for robust regression problems. In: K. Chaudhuri, M. Sugiyama (eds.) Proceedings of Machine Learning Research, Proceedings of Machine Learning Research, vol. 89, pp. 313–322. PMLR (2019). URL http://proceedings.mlr.press/v89/mukhoty19a.html

[47]

Nakagaki T, Yamada H, and Toth A Maze-solving by an amoeboid organism Nature 2000 407 6803 470

[48]

Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming, vol. 13. Society for Industrial and Applied Mathematics, (1994)

[49]

Olver, N., Végh, L.A.: A simpler and faster strongly polynomial algorithm for generalized flow maximization. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pp. 100–111 (2017).

[50]

Orecchia, L., Sachdeva, S., Vishnoi, N.K.: Approximating the exponential, the lanczos method and an õ(m)-time spectral algorithm for balanced separator. In: H.J. Karloff, T. Pitassi (eds.) Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pp. 1141–1160. ACM (2012).

[51]

Osborne MR Finite Algorithms in Optimization and Data Analysis 1985 New York, NY, USA John Wiley & Sons Inc

[52]

Perko L Differential equations and dynamical systems 2000 3 Berlin Springer Science & Business Media

[53]

Rao BD and Kreutz-Delgado K An affine scaling methodology for best basis selection IEEE Trans. Signal Process. 1999 47 1 187-200

[54]

Sherman, J.: Nearly maximum flows in nearly linear time. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pp. 263–269 (2013).

[55]

Spielman DA Algorithms, graph theory, and the solution of laplacian linear equations ICALP 2012 2 24-26

[56]

Spielman, D.A., Teng, S.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pp. 81–90 (2004).

[57]

Stonick VL and Alexander ST A relationship between the recursive least squares update and homotopy continuation methods IEEE Trans. Signal Process. 1991 39 2 530-532

[58]

Straszak, D., Vishnoi, N.K.: On a natural dynamics for linear programming. In: ACM Innovations in Theoretical Computer Science (2016)

[59]

Straszak, D., Vishnoi, N.K.: IRLS and slime mold: equivalence and convergence. CoRR. arXiv:1601.02712 (2016)

[60]

Straszak, D., Vishnoi, N.K.: Natural algorithms for flow problems. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016, pp. 1868–1883. (2016)

[61]

Teng, S.H.: The Laplacian paradigm: Emerging algorithms for massive graphs. In: TAMC, pp. 2–14 (2010)

[62]

Tero A, Kobayashi R, and Nakagaki T A mathematical model for adaptive transport network in path finding by true slime mold J. Theor. Biol. 2007 244 4 553

[63]

Valiant LG Evolvability J. ACM 2009 56 1 3:1-3:21

[64]

Végh LA A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives SIAM J. Comput. 2016 45 5 1729-1761

[65]

Vishnoi NK

L x = b

Foundat. Trends Theor. Comput. Sci. 2012 8 1–2 1-141

[66]

Vishnoi, N.K.: The speed of evolution. In: Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’15, pp. 1590–1601. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2015). URL http://dl.acm.org/citation.cfm?id=2722129.2722234

[67]

Wright, S.: Primal-Dual Interior-Point Methods. Society for Industrial and Applied Mathematics (1997)

Cited By

Balter ASchumacher JSchweizer N(2024)Solving Maxmin Optimization Problems via Population GamesJournal of Optimization Theory and Applications10.1007/s10957-024-02415-4201:2(760-789)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10957-024-02415-4
Celis LKumar AMehrotra AVishnoi NOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Bias in evaluation processesProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669283(72193-72247)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669283

Index Terms

Iteratively reweighted least squares and slime mold dynamics: connection and convergence
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
    2. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Mathematical optimization

Index terms have been assigned to the content through auto-classification.

Recommendations

Smoothed Low Rank and Sparse Matrix Recovery by Iteratively Reweighted Least Squares Minimization
This paper presents a general framework for solving the low-rank and/or sparse matrix minimization problems, which may involve multiple nonsmooth terms. The iteratively reweighted least squares (IRLSs) method is a fast solver, which smooths the objective ...
Low-rank Matrix Recovery via Iteratively Reweighted Least Squares Minimization

We present and analyze an efficient implementation of an iteratively reweighted least squares algorithm for recovering a matrix from a small number of linear measurements. The algorithm is designed for the simultaneous promotion of both a minimal ...
Harmonic mean iteratively reweighted least squares for low-rank matrix recovery

We propose a new iteratively reweighted least squares (IRLS) algorithm for the recovery of a matrix X ∈ C^d₁×d₂ of rank r ≪ min(d₁, d₂) from incomplete linear observations, solving a sequence of low complexity linear problems. The easily implementable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 194, Issue 1-2

Jul 2022

1173 pages

ISSN:0025-5610

Issue’s Table of Contents

© Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2021.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 July 2022

Accepted: 12 March 2021

Received: 05 December 2019

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Balter ASchumacher JSchweizer N(2024)Solving Maxmin Optimization Problems via Population GamesJournal of Optimization Theory and Applications10.1007/s10957-024-02415-4201:2(760-789)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10957-024-02415-4
Celis LKumar AMehrotra AVishnoi NOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Bias in evaluation processesProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669283(72193-72247)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669283

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents