Kybernetika 60 no. 2, 197-209, 2024

Multi-step-length gradient iterative method for separable nonlinear least squares problems

Hai-Rong Cui, Jing Lin and Jian-Nan SuDOI: 10.14736/kyb-2024-2-0197

Abstract:

Separable nonlinear least squares (SNLLS) problems are critical in various research and application fields, such as image restoration, machine learning, and system identification. Solving such problems presents a challenge due to their nonlinearity. The traditional gradient iterative algorithm often zigzags towards the optimal solution and is sensitive to the initial guesses of unknown parameters. In this paper, we improve the convergence rate of the traditional gradient method by implementing a multi-step-length gradient iterative algorithm. Moreover, we incorporate the variable projection (VP) strategy, taking advantage of the separable structure observed in SNLLS problems. We propose a multi-step-length gradient iterative-based VP (Mul-GI-VP) method to solve such nonlinear optimization problems. Our simulation results verify the feasibility and high efficiency of the proposed algorithm.

Keywords:

image restoration, multi-step-length gradient iterative method, variable projection algorithm, separable nonlinear least squares

Classification:

49M99

References:

  1. A. Y. Aravkin, D. Drusvyatskiy and T. van Leeuwen: Efficient quadratic penalization through the partial minimization technique. IEEE Trans. Automat. Control 63 (2017), 7, 2131-2138.   DOI:10.1109/TAC.2017.2754474
  2. G. Y. Chen, M. Gan, C. P. Chen and L. Chen: A two-stage estimation algorithm based on variable projection method for gps positioning. IEEE Trans. Instrument. Measur. 67 (2018), 11, 2518-2525.   CrossRef
  3. G. Y. Chen, M. Gan, C. P. Chen and H. X. Li: Basis function matrix-based flexible coefficient autoregressive models: A framework for time series and nonlinear system modeling. IEEE Trans. Cybernet. 51 (2021), 2, 614-623.   DOI:10.1109/TCYB.2019.2900469
  4. G. Y. Chen, S. Q. Wang, M. Gan and C. P. Chen: Insights into algorithms for separable nonlinear least squares problems. IEEE Trans. Imagw Process. 30 (2021), 2, 1207-1218.   DOI:10.1109/TIP.2020.3043087
  5. J. Chen and F. Ding: Modified stochastic gradient identification algorithms with fast convergence rates. J. Vibration Control 17 (2011), 9, 1281-1286.   DOI:10.1177/1077546310376989
  6. J. Chen, F. Ding, Y. Liu and Q. Zhu: Multi-step-length gradient iterative algorithm for equation-error type models. Systems Control Lett. 115 (2018), 15-21.   DOI:10.1016/j.sysconle.2018.03.003
  7. J. Chung, J. G and Nagy: An efficient iterative approach for large-scale separable nonlinear inverse problems. SIAM J. Scientif. Comput. 31 (2010), 6, 4654-4674.   DOI:10.1137/080732213
  8. A. Cornelio, E. L. Piccolomini and J. G. Nagy: Constrained numerical optimization methods for blind deconvolution. Numer. Algorithms 65 (2014) 1, 23-42.   DOI:10.1007/s11075-013-9693-z
  9. F. Ding: Coupled-least-squares identification for multivariable systems. IET Control Theory Appl. 7 (2013), 1, 68-79.   DOI:10.1049/iet-cta.2012.0171
  10. F. Ding, G. Liu and X. P. Liu: Partially coupled stochastic gradient identification methods for non-uniformly sampled systems. IEEE Trans. Automat. Control 55 (2010), 8, 1976-1981.   DOI:10.1109/TAC.2010.2050713
  11. F. Ding, Y. Liu and B. Bao: Gradient-based and least-squares-based iterative estimation algorithms for multi-input multi-output systems. Proc. Inst. Mechanic. Engrs, Part I: J. Systems Control Engrg. 226 (2012), 1, 43-55.   DOI:10.1177/0959651811409491
  12. N. B. Erichson, P. Zheng, K. Manohar, S. L. Brunton, J. N. Kutz and A. Y. Aravkin: Sparse principal component analysis via variable projection. SIAM J. Appl. Math. 80 (2020), 2, 977-1002.   DOI:10.1137/18M1211350
  13. M. Gan, C. P. Chen, G. Y. Chen and L. Chen: On some separated algorithms for separable nonlinear least squares problems. IEEE Trans. Cybernet. 48 (2018), 10, 2866-2874.   DOI:10.1109/TCYB.2017.2751558
  14. M. Gan, Y. Guan, G. Y. Chen and C. P. Chen: Recursive variable projection algorithm for a class of separable nonlinear models. IEEE Trans. Neural Netw. Learn. Syst. (2020).   CrossRef
  15. M. Gan, H. X. Li and H. Peng: A variable projection approach for efficient estimation of rbf-arx model. IEEE Trans. Cybernet. 45 (2014), 3, 462-471.   DOI:10.1109/TSMC.2014.2358635
  16. M. Gan and H. Peng: Stability analysis of rbf network-based state-dependent autoregressive model for nonlinear time series. Appl. Soft Comput. 12 (2012), 1, 174-181.   DOI:10.1016/j.asoc.2011.08.055
  17. G. Golub and V. Pereyra: Separable nonlinear least squares: the variable projection method and its applications. Inverse Problems 19 (2003), R1.   DOI:10.1088/0266-5611/19/2/201
  18. G. .H Golub and V. Pereyr: The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate. SIAM J. Numer. Snal. 10 (1973), 2, 413-432.   DOI:10.1137/0710036
  19. V. Haggan and T. Ozaki: Modelling nonlinear random vibrations using an amplitude-dependent autoregressive time series model. Biometrika 68 (1981), 1, 189-196.   DOI:10.1093/biomet/68.1.189
  20. P. Ch. Hansen, J. G. Nagy and D. P. O'leary: Deblurring images: matrices, spectra, and filtering. SIAM 2006.   CrossRef
  21. A Hussu: The conjugate-gradient method for optimal control problems with undetermined final time. Int. J. Control 15 (1972), 1, 79-82.   DOI:10.1080/00207177208932130
  22. L. Kaufman: A variable projection method for solving separable nonlinear least squares problems. BIT Numer. Math. 15 (1975), 1, 49-57.   DOI:10.1007/BF01932995
  23. J. Li, Y. Zheng and Z. Lin: Recursive identification of time-varying systems: Self-tuning and matrix rls algorithms. Syst. Control Lett. 66 (2014), 104-110.   DOI:10.1016/j.sysconle.2014.01.004
  24. M. Li, A. Abubakar, F. Gao and T. M Habashy: Application of the variable projection scheme for calibration in electromagnetic data inversion. IEEE Trans. Antennas Propag. 64 (2015), 1, :332-335.   DOI:10.1109/TAP.2015.2498946
  25. Y. Liu, F. Ding and Y. Shi: An efficient hierarchical identification method for general dual-rate sampled-data systems. Automatica 50 (2014), 3, 962-970.   DOI:10.1016/j.automatica.2013.12.025
  26. T. Okatani and K. Deguchi: On the wiberg algorithm for matrix factorization in the presence of missing components. Int. J. Comput. Vision 72 (2007), 3, 329-337.   DOI:10.1007/s11263-006-9785-5
  27. M. R, Osborne and G. K. Smyth: A modified prony algorithm for exponential function fitting. SIAM J. Scient. Comput. 16 (1995), 1, :119-138.   DOI:10.1137/0916008
  28. H. Peng, T. Ozaki, Y. Toyoda, H. Shioya, K. Nakano, V. Haggan-Ozaki and M. Mori: Rbf-arx model-based nonlinear system modeling and predictive control with application to a nox decomposition process. Control Engrg. Practice 12 (2004), 2, 191-203.   DOI:10.1016/S0967-0661(03)00050-9
  29. A. Ruhe and Pe. A. Wedin: Algorithms for separable nonlinear least squares problems. SIAM Rev. 22 (1980), 3, 318-337.   DOI:10.1137/1022057
  30. J. Sjoberg and M. Viberg: Separable non-linear least-squares minimization-possible improvements for neural net fitting. In: Neural Networks for Signal Processing VII. Proc. 1997 IEEE Signal Processing Society Workshop, IEEE 1997, pp. 345-354.   CrossRef
  31. G. Stathopoulos, M. Korda and C. N. Jones: Solving the infinite-horizon constrained lqr problem using accelerated dual proximal methods. IEEE Trans. Automat. Control. 62 (2016), 4, 1752-1767.   DOI:10.1109/TAC.2016.2594381
  32. H. Yang, J. Gao and Z. Wu: Blur identification and image super-resolution reconstruction using an approach similar to variable projection. IEEE Signal Process. Lett. 15 (2008), 289-292.   DOI:10.1109/LSP.2007.911743
  33. D. Yu, C. P. Chen and H. Xu: Fuzzy swarm control based on sliding-mode strategy with self-organized omnidirectional mobile robots system. IEEE Trans. Systems Man Cybernet.: Systems 52 (2021), 4, 2262-2274.   DOI:10.1109/TSMC.2020.3048733
  34. D. Yu, H. Xu, C. P. Chen, W. Bai and Z. Wang: Dynamic coverage control based on k-means. IEEE Trans. Industr. Electron. 2021.   CrossRef
  35. J. Zeng, T. He and M. Wang: A fast proximal gradient algorithm for decentralized composite optimization over directed networks. Systems Control Lett. 107 (2017), 36-43.   DOI:10.1016/j.sysconle.2017.07.005