﻿ Continuous Piecewise Linear Approximation of BV Function

Applied Mathematics
Vol.5 No.4(2014), Article ID:43572,5 pages DOI:10.4236/am.2014.54063

Continuous Piecewise Linear Approximation of BV Function

Hua Yi*, Tao Yu, Zhiquan Chen, Jingwen Zhu

School of Mathematics and Physics, Jinggangshan University, Ji’an, China

Email: *yihua@whu.edu.cn, yutao@jgsu.edu.cn, chenzhiquanji@126.com, zhujingwen666@163.com  Received 19 December 2013; revised 19 January 2014; accepted 27 January 2014

ABSTRACT

Nonlinear approximation is widely used in signal processing. Real-life signals can be modeled as functions of bounded variation. Thus the variable knot of approximating function could be selfadaptively chosen by balancing the total variation of the target function. In this paper, we adopt continuous piecewise linear approximation instead of the existing piecewise constants approximation. The results of experiments show that this new method is superior to the old one.

Keywords:Nonlinear Approximation; Bounded Variation; Continuous Piecewise Linear Basis Function; Piecewise Constant Basis Function; Compression; Denoising 1. Introduction

The fundamental problem of approximation theory is to resolve a possibly complicated function, called the target function, by simpler, easier to compute functions called the approximants   . The early methods utilized approximation from finite-dimensional linear spaces. In the beginning, these were typically spaces of polynomials, both algebraic and trigonometric. It was noted shortly thereafter that there were some advantages to be gained by not limiting the approximations to come from linear spaces  . In nonlinear approximation, the approximating function is not restricted to come from spaces of piece wise polynomials with a fixed partition; rather, the partition was allowed to depend on the target function. In principle, the idea was simple: we should use a finer mesh where the target function is not very smooth (singular) and a coarser mesh where it is smooth. Thus, an important question in nonlinear approximation is how we should measure this smoothness in order to obtain definitive results.

Kahane (1961)  gave a result which was concerned with how to obtain the variable knot of function in bounded variation space. Zhang (2009)  gave the corresponding numerical experiments by using the piecewise constants function. Moreover, the advantages of Zhang’s method over other denoising methods, such as Visushrink  and SureShrinkage  were also analyzed  .

In this paper, we use piecewise linear basis functions instead of the piecewise constants basis functions adopted by Kahane, which is motivated by continuous piecewise linear approximation studied by Y. Shi (2010)  . The experimental results of this new method are superior to those of the old one.

2. The Method for the Selection of Variable Knots and Continuous Piecewise Linear Approximation

We can consider that a real-life signal f is defined on and . In order to self-adaptively select the knots according to the target function, we can balance the total variation (TV) of this function  . The TV of f is given by (1.1)

where the supremum is taken over the set of all partitions of . The TV function  is non-negative monotone continuous function on with . We divide the range of (which is the interval ) on the y-axis into n pieces corresponding to the y values . We denote the preimage of these points by , we have (1.2)

Hence, forms the partition balancing the TV of over each interval . Then the target function can be approximated by piecewise constants  . That is, (1.3)

is the approximating function of . In this case, the —error to is (1.4)

However, is not continuous. In order to approximate the target function by continuous function, we construct the continuous piecewise linear basis function as follows  : (1.5)

We can substitute for Haar scaling function(the piecewise constant function) to achieve continuous piecewise linear approximation, and the corresponding error analysis has been thoroughly studied in  .

We define (1.6)

where , , , . Then, achieves the continuous piecewise linear approximation for the target function.

3. Numerical Experiments

In this section, we give comparisons of methods in signal compression and denoising by two examples. The signal leleccum is composed of 1000 points, presented in Figure 1(a). TV function of the original function is shown in Figure 1(b). By dividing the range of the TV function on the y-axis into n pieces to get y-values, the preimage of these y-values form the self-adaptively knots of the target function. In this experiment of this paper, we let . So the original signal can be represented by a compressed version with 500 points. Figure 1(e) provides the compressed signal by Zhang’s method, i.e., using the piecewise constants approximation. Figure 1(c) presents the compressed signal by using continuous piecewise linear approximation. We use norm to measure the error of compression. That is, (1.7)

We see that the proposed method is superior to the old one as long as we notice that for our method is less than for the old one. The compressed signal with by VisuShrink is also presented in Figure 1(d).

The second example is related to a natural noisy signal which is shown in Figure 2(a). The restored signals by using our method and by using the old one are respectively shown in Figures 2(d) and (c). The advantages of our method over the old one consist of two aspects. Firstly, of the denoised signal in Figure 2(d) is larger than in Figure 2(c). At this time, SNR of the denoised signal is defined as Figure 1. compression for signal leleccum. Figure 2. (a) Noise reduction for signal noisdopp; (b) Restored signal by Visu Shrink with SNR = 13.29; (c) Restored signal by Zhang’s method with n = 450, SNR = 13.91; (d) Restored signal by using our method with n = 450, SNR = 13.93. (1.8)

Secondly, the signal in Figure 2(d) is more smooth. See the rectangle parts of Figures 2(c) and (d) for details. The sawtooth nature of denoised signal in Figure 2(c) may be caused by the shape of piecewise constant basis function.

4. Conclusion

Nonlinear approximation is the theoretical foundation of compression and denoising of signals. Zhang has presented a general partition method to obtain the variable knots according to the target function. However, the drawback of Zhang’s method is that the smoothness of the restored signal is bad when n is small. In this paper, we use continuous piecewise linear basis function as a substitute for the piecewise constant basis function adopted by Zhang. Our method performs better than the old one both in terms of SNR and vision.

Funding

The work was supported by jskjz  32-8,  32-7, National Natural Science Foundation of China under Grant No. 11347210, the Doctoral Starting up Foundation of Jinggangshan University (Grant No. JZB1304), the Natural Science Foundation of Jiangxi Province, China (Grant No. 20132BAB211018).

References

1. DeVore, R.A. and Lorentz, G.G. (1993) Constructive Approximation. Volume 303. Springer, Berlin.
2. DeVore, R.A. (1998) Nonlinear Approximation. In Acta Numerica, Cambridge University Press, Cambridge, 51-150.
3. Kahane, J.P. (1961) Teora Constructiva de Funciones, Volume 5. Universidad de Buenos Aires, Buenos Aires.
4. Zhang, T., Fan, Q. and Shu, H. (2009) Approximation of BV Function by Piecewise Constants and Its Application in Signal Denoising and Compression. 2nd International Congress on Image and Signal Processing, Tianjin, 17-19 October 2009, 1-5.
5. Donoho, D.L. and Johnstone, J.M. (1994) Ideal Spatial Adaptation by Wavelet Shrinkage. Biometrika, 81, 425-455. http://dx.doi.org/10.1093/biomet/81.3.425
6. Donoho, D.L. and Johnstone, I.M. (1995) Adapting to Unknown Smoothness via Wavelet Shrinkage. Journal of the American Statistical Association, 90, 1200-1224. http://dx.doi.org/10.1080/01621459.1995.10476626

NOTES *Corresponding author.