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

Cui, Hai-Rong ; Lin, Jing ; Su, Jian-Nan

Kybernetika, Tome 60 (2024) no. 2, pp. 197-209

Abstract (VO)

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.

Détail

DOI : 10.14736/kyb-2024-2-0197

Classification : 49M99
Keywords: separable nonlinear least squares; multi-step-length gradient iterative method; variable projection algorithm; image restoration

Bibliographie

[1] Aravkin, A. Y., Drusvyatskiy, D., Leeuwen, T. van: Efficient quadratic penalization through the partial minimization technique. IEEE Trans. Automat. Control 63 (2017), 7, 2131-2138. | DOI | MR

[2] Chen, G. Y., Gan, M., Chen, C. P., Chen, L.: A two-stage estimation algorithm based on variable projection method for gps positioning. IEEE Trans. Instrument. Measur. 67 (2018), 11, 2518-2525. | DOI

[3] Chen, G. Y., Gan, M., Chen, C. P., Li, H. X.: 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

[4] Chen, G. Y., Wang, S. Q., Gan, M., Chen, C. P.: Insights into algorithms for separable nonlinear least squares problems. IEEE Trans. Imagw Process. 30 (2021), 2, 1207-1218. | DOI | MR

[5] Chen, J., Ding, F.: Modified stochastic gradient identification algorithms with fast convergence rates. J. Vibration Control 17 (2011), 9, 1281-1286. | DOI | MR

[6] Chen, J., Ding, F., Liu, Y., Zhu, Q.: Multi-step-length gradient iterative algorithm for equation-error type models. Systems Control Lett. 115 (2018), 15-21. | DOI | MR

[7] Chung, J., G, J., Nagy: An efficient iterative approach for large-scale separable nonlinear inverse problems. SIAM J. Scientif. Comput. 31 (2010), 6, 4654-4674. | DOI | MR

[8] Cornelio, A., Piccolomini, E. L., Nagy, J. G.: Constrained numerical optimization methods for blind deconvolution. Numer. Algorithms 65 (2014) 1, 23-42. | DOI | MR

[9] Ding, F.: Coupled-least-squares identification for multivariable systems. IET Control Theory Appl. 7 (2013), 1, 68-79. | DOI | MR

[10] Ding, F., Liu, G., Liu, X. P.: Partially coupled stochastic gradient identification methods for non-uniformly sampled systems. IEEE Trans. Automat. Control 55 (2010), 8, 1976-1981. | DOI | MR

[11] Ding, F., Liu, Y., Bao, B.: 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

[12] Erichson, N. B., Zheng, P., Manohar, K., Brunton, S. L., Kutz, J. N., Aravkin, A. Y.: Sparse principal component analysis via variable projection. SIAM J. Appl. Math. 80 (2020), 2, 977-1002. | DOI | MR

[13] Gan, M., Chen, C. P., Chen, G. Y., Chen, L.: On some separated algorithms for separable nonlinear least squares problems. IEEE Trans. Cybernet. 48 (2018), 10, 2866-2874. | DOI

[14] Gan, M., Guan, Y., Chen, G. Y., Chen, C. P.: Recursive variable projection algorithm for a class of separable nonlinear models. IEEE Trans. Neural Netw. Learn. Syst. (2020). | MR

[15] Gan, M., Li, H. X., Peng, H.: A variable projection approach for efficient estimation of rbf-arx model. IEEE Trans. Cybernet. 45 (2014), 3, 462-471. | DOI

[16] Gan, M., Peng, H.: Stability analysis of rbf network-based state-dependent autoregressive model for nonlinear time series. Appl. Soft Comput. 12 (2012), 1, 174-181. | DOI

[17] Golub, G., Pereyra, V.: Separable nonlinear least squares: the variable projection method and its applications. Inverse Problems 19 (2003), R1. | DOI | MR

[18] Golub, G. .H, Pereyr, V.: The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate. SIAM J. Numer. Snal. 10 (1973), 2, 413-432. | DOI | MR

[19] Haggan, V., Ozaki, T.: Modelling nonlinear random vibrations using an amplitude-dependent autoregressive time series model. Biometrika 68 (1981), 1, 189-196. | DOI | MR

[20] Hansen, P. Ch., Nagy, J. G., O'leary, D. P.: Deblurring images: matrices, spectra, and filtering. SIAM 2006. | MR

[21] Hussu, A: The conjugate-gradient method for optimal control problems with undetermined final time. Int. J. Control 15 (1972), 1, 79-82. | DOI

[22] Kaufman, L.: A variable projection method for solving separable nonlinear least squares problems. BIT Numer. Math. 15 (1975), 1, 49-57. | DOI | MR

[23] Li, J., Zheng, Y., Lin, Z.: Recursive identification of time-varying systems: Self-tuning and matrix rls algorithms. Syst. Control Lett. 66 (2014), 104-110. | DOI | MR

[24] Li, M., Abubakar, A., Gao, F., Habashy, T. M: Application of the variable projection scheme for calibration in electromagnetic data inversion. IEEE Trans. Antennas Propag. 64 (2015), 1, :332-335. | DOI | MR

[25] Liu, Y., Ding, F., Shi, Y.: An efficient hierarchical identification method for general dual-rate sampled-data systems. Automatica 50 (2014), 3, 962-970. | DOI | MR

[26] Okatani, T., Deguchi, K.: On the wiberg algorithm for matrix factorization in the presence of missing components. Int. J. Comput. Vision 72 (2007), 3, 329-337. | DOI

[27] R, M., Osborne, Smyth, G. K.: A modified prony algorithm for exponential function fitting. SIAM J. Scient. Comput. 16 (1995), 1, :119-138. | DOI | MR

[28] Peng, H., Ozaki, T., Toyoda, Y., Shioya, H., Nakano, K., Haggan-Ozaki, V., Mori, M.: 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

[29] Ruhe, A., Wedin, Pe. A.: Algorithms for separable nonlinear least squares problems. SIAM Rev. 22 (1980), 3, 318-337. | DOI | MR

[30] Sjoberg, J., Viberg, M.: 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.

[31] Stathopoulos, G., Korda, M., Jones, C. N.: Solving the infinite-horizon constrained lqr problem using accelerated dual proximal methods. IEEE Trans. Automat. Control. 62 (2016), 4, 1752-1767. | DOI | MR

[32] Yang, H., Gao, J., Wu, Z.: Blur identification and image super-resolution reconstruction using an approach similar to variable projection. IEEE Signal Process. Lett. 15 (2008), 289-292. | DOI

[33] Yu, D., Chen, C. P., Xu, H.: 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

[34] Yu, D., Xu, H., Chen, C. P., Bai, W., Wang, Z.: Dynamic coverage control based on k-means. IEEE Trans. Industr. Electron. 2021.

[35] Zeng, J., He, T., Wang, M.: A fast proximal gradient algorithm for decentralized composite optimization over directed networks. Systems Control Lett. 107 (2017), 36-43. | DOI | MR