A Proximal–Based Algorithm for Piecewise Sparse Approximation with Application to Scattered Data Fitting

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

doi:10.34768/amcs-2022-0046

Abstract

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.

References

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, 10.1137/080716542.
Search in Google Scholar Back to article
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.
Open DOI Search in Google Scholar Back to article
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.10.1090/S0025-5718-09-02242-X
Search in Google Scholar Back to article
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.10.1109/TMM.2016.2640759
Search in Google Scholar Back to article
Castaño, D. and Kunoth, A. (2005). Multilevel regularization of wavelet based fitting of scattered data some experiments, Numerical Algorithms 39(1): 81–96.10.1007/s11075-004-3622-0
Search in Google Scholar Back to article
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.10.1016/j.gmod.2008.03.001
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.10.1016/j.cagd.2012.03.025
Search in Google Scholar Back to article
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.
Open DOI Search in Google Scholar Back to article
Hirsch, M.W., Smale, S. and Devaney, R.L. (2004). Differential Equations, Dynamical Systems, and an Introduction to Chaos, Academic Press, Amsterdam.
Search in Google Scholar Back to article
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.
Open DOI Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Open DOI Search in Google Scholar Back to article
Li, C. and Zhong, Y.J. (2019). Piecewise sparse recovery in union of bases, arXiv 1903.01208.
Search in Google Scholar Back to article
McCoy, M.B. and Tropp, J.A (2014). Sharp recovery bounds for convex demixing, with applications, Foundations of Computational Mathematics 14(3): 503–567.10.1007/s10208-014-9191-2
Search in Google Scholar Back to article
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.10.1016/j.jcde.2017.10.004
Search in Google Scholar Back to article
Ni, Q., Wang, X. and Deng, J. (2019). Modified PHT-splines, Computer Aided Geometric Design 73(1): 37–53.10.1016/j.cagd.2019.07.001
Search in Google Scholar Back to article
Parikh, N. and Boyd, S. (2014). Proximal algorithms, Foundations and Trends in Optimization 1(3): 127–239, DOI: 10.1.1.398.7055.
Open DOI Search in Google Scholar Back to article
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.
Open DOI Search in Google Scholar Back to article
Rockafellar, R.T. (1970). Convex Analysis, Princeton University Press, Princeton.
Search in Google Scholar Back to article
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.10.1137/140964357
Search in Google Scholar Back to article
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.
Open DOI Search in Google Scholar Back to article
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.10.1007/s11432-017-9367-6
Search in Google Scholar Back to article
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.10.1007/s10915-016-0318-2
Search in Google Scholar Back to article
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.10.1137/19M1242276
Search in Google Scholar Back to article
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.10.1007/s10915-010-9408-8
Search in Google Scholar Back to article
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.
Open DOI Search in Google Scholar Back to article

A Proximal–Based Algorithm for Piecewise Sparse Approximation with Application to Scattered Data Fitting

Abstract

Paradigm

My account