A proximal-based algorithm for piecewise sparse approximation with application to scattered data fitting

Zhong, Yijun  ; Li, Chongjun ; Li, Zhong ; Duan, Xiaojuan

International Journal of Applied Mathematics and Computer Science, Tome 32 (2022) no. 4, pp. 671-682.

Résumé

In some applications, there are signals with a piecewise structure to be recovered. In this paper, we propose a piecewise sparse approximation model and a piecewise proximal gradient method (JPGA) which aim to approximate piecewise signals. We also make an analysis of the JPGA based on differential equations, which provides another perspective on the convergence rate of the JPGA. In addition, we show that the problem of sparse representation of the fitting surface to the given scattered data can be considered as a piecewise sparse approximation. Numerical experimental results show that the JPGA can not only effectively fit the surface, but also protect the piecewise sparsity of the representation coefficient.

Détail

Keywords: piecewise sparse approximation, proximal gradient, scattered data fitting
Mots-clés : aproksymacja rzadka, gradient proksymalny, dopasowanie danych

Bibliographie

[1] [1] Beck, A. and Teboulle, M. (2009). A fast iterative shrinkage thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences 2(1): 183–202, DOI: 10.1137/080716542.

[2] [2] Bingi, K., Ibrahim, R., Karsiti, M.N., Hassam, S.M. and Harindran, V.R. (2019). Frequency response based curve fitting approximation of fractional-order PID controllers, International Journal of Applied Mathematics and Computer Science 29(2): 311–326, DOI: 10.2478/amcs-2019-0023.

[3] [3] Cai, J.F., Osher, S. and Shen, Z. (2009). Convergence of the linearized Bregman iteration for [...] norm minimization, Mathematics of Computation 78(268): 2127–2136.

[4] [4] Cai, Z., Lan, T. and Zheng, C. (2016). Hierarchical MK splines: Algorithm and applications to data fitting, IEEE Transactions on Multimedia 19(5): 921–934.

[5] [5] Castaño, D. and Kunoth, A. (2005). Multilevel regularization of wavelet based fitting of scattered data some experiments, Numerical Algorithms 39(1): 81–96.

[6] [6] Deng, J., Chen, F., Li, X., Hu, C., Yang, Z. and Feng, Y. (2008). Polynomial splines over hierarchical T-meshes, Graphical Models 70(4): 76–86.

[7] [7] Franca, G., Robinson, D. and Vidal, R. (2018). ADMM and accelerated ADMM as continuous dynamical systems, International Conference on Machine Learning, PMLR 2018, Stockholm, Sweden, pp. 1559–1567.

[8] [8] Giannelli, C., Jüttler, B. and Speleers, H. (2012). THB-splines: The truncated basis for hierarchical splines, Computer Aided Geometric Design 29(7): 485–498.

[9] [9] Hao, Y., Li, C. and Wang, R. (2018). Sparse approximate solution of fitting surface to scattered points by MLASSO model, Science China Mathematics 61(7): 1319–1336, DOI: 10.1007/s11425-016-9087-y.

[10] [10] Hirsch, M.W., Smale, S. and Devaney, R.L. (2004). Differential Equations, Dynamical Systems, and an Introduction to Chaos, Academic Press, Amsterdam.

[11] [11] Johnson, M.J., Shen, Z. and Xu, Y. (2009). Scattered data reconstruction by regularization in B-spline and associated wavelet spaces, Journal of Approximation Theory 159(2): 197–223, DOI: 10.1016/j.jat.2009.02.005.

[12] [12] Kraft, D. (1997). Adaptive and linearly independent multilevel B-splines, in Le Méhauté et al. (Eds), Surface Fitting and Multiresolution Methods, Vanderbilt University Press, Nashville, pp. 209–218.

[13] [13] Lee, S., Wolberg, G. and Shin, S. (1997). Scattered data interpolation with multilevel B-splines, IEEE Transactions on Visualization and Computer Graphics 3(3): 228–244, DOI: 10.1109/2945.620490.

[14] [14] Li, C. and Zhong, Y.J. (2019). Piecewise sparse recovery in union of bases, arXiv 1903.01208.

[15] [15] McCoy, M.B. and Tropp, J.A (2014). Sharp recovery bounds for convex demixing, with applications, Foundations of Computational Mathematics 14(3): 503–567.

[16] [16] Moon, S. and Ko, K. (2018). A point projection approach for improving the accuracy of the multilevel b-spline approximation, Journal of Computational Design and Engineering 5(2): 173–179.

[17] [17] Ni, Q., Wang, X. and Deng, J. (2019). Modified PHT-splines, Computer Aided Geometric Design 73(1): 37–53.

[18] [18] Parikh, N. and Boyd, S. (2014). Proximal algorithms, Foundations and Trends in Optimization 1(3): 127–239, DOI: 10.1.1.398.7055.

[19] [19] Pięta, P. and Szmuc, T. (2021). Applications of rough sets in big data analysis: An overview, International Journal of Applied Mathematics and Computer Science 31(4): 659–683, DOI: 10.34768/amcs-2021-0046.

[20] [20] Rockafellar, R.T. (1970). Convex Analysis, Princeton University Press, Princeton.

[21] [21] Sun, D., Toh, K.C. and Yang, L. (2015). A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints, SIAM Journal on Optimization 25(2): 882–915.

[22] [22] Starck, J.L., Elad, M. and Donoho, D.L. (2005). Image decomposition via the combination of sparse representations and a variational approach, IEEE Transactions on Image Processing 14(10): 1570–1582, DOI: 10.1109/TIP.2005.852206.

[23] [23] Wang, F., Cao, W. and Xu, Z. (2018). Convergence of multi-block Bregman ADMM for nonconvex composite problems, Science China Information Sciences 61(12): 1–12.

[24] [24] Wei, D., Lai, M.J., Reng, Z. and Yin, W. (2017). Parallel multi-block ADMM with o(1/k) convergence, Journal of Scientific Computing 71(2): 712–736.

[25] [25] Zhang, J. and Luo, Z.Q. (2020). A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization, SIAM Journal on Optimization 30(3): 2272–2302.

[26] [26] Zhang, X., Burger, M. and Osher, S. (2011). A unified primal-dual algorithm framework based on Bregman iteration, Journal of Scientific Computing 46(1): 20–46.

[27] [27] Zhong, Y. and Li, C. (2020). Piecewise sparse recovery via piecewise inverse scale space algorithm with deletion rule, Journal of Computational Mathematics 38(2): 375–394, DOI: 10.4208/jcm.1810-m2017-0233.