Engineering
Computer Science-2021.gz:143128
Computer Science
e8d4e4b8af0b7021071de19757d9ad0522eb2aa6
Windowed total variation denoising and noise variance monitoring

We proposed a real time Total-Variation denosing method with an automatic choice of hyper-parameter $\lambda$, and the good performance of this method provides a large application field. In this article, we adapt the developed method to the non stationary signal in using the sliding window, and propose a noise variance monitoring method. The simulated results show that our proposition follows well the variation of noise variance.


I. INTRODUCTION
The signal y = (y 1 , · · · , y n ) ∈ R n collected by the sensor can be modeled as y = u + : a random noise is added into the useful physical quantity u with E( ) = 0 and V( ) = σ 2 .
Motivated by the local influence of new sample to the actual restoration, we propose a new online TV-restoration algorithm with an automatic choice of λ for a stationary 1D signal in [3] following the work of [4] and [5]. The simulations show that our proposition of λ has a similar performance as the existing methods (SURE [6] and cross-validation). Further more, our method is appropriate for real time applications, especially for monitoring a huge amount of sensors in the plants.
In this paper, we adapt our online TV restoration to nonstationary signals and propose a noise variance monitoring method. The key idea is to use our method on sliding windows, assuming a local-stationary hypothesis for the signal. This hypothesis is strong but commonly used already (e.g. Fourier analysis, wavelet transforms). In order to apply our method to non-stationary signals, two problems are to be solved: • Adaptation of the online method to the sliding window • Choice of the length of window (noted m) The first point ensures the efficiency of the real time estimation, while the second point guarantees the good performance of method. Indeed, the choice of m needs to get a compromise between the local stationarity assumption and the performance of the restoration : the local influence of new sample vanishes inside a large window, but the local stationarity may not be respected. In this article, we present how we deal with the first point by supposing the influence of new sample stays inside the actual window. The choice of window size is the immediate perspective of this work.
The increasing of the ground noise is one of the index for the failures of the sensors or the production lines. This motivates us to build a real time application for detecting the variance behaviour by tracking the windowed restoration residuals y − u * (λ ours ) based on the automatic determination of hyper-parameter λ ours .
Here some approaches for the estimation of noise variance σ 2 are listed: • Most of the existing methods are based on the separation of signal and noise by digital filters [7] or the restoration methods (i.e. wavelet transform) [8] [9] [10]. See more details in [11]. • Median absolute deviation (MAD) proposed by [12] is a heuristic method largely used in many applications, especially for the choice of threshold for wavelet restoration. σ can be estimated by the median absolute deviation of the finest scale of wavelet coefficients By of signal.
With respect to the previous cited method, our approach, based on the separation of signal and noise, proposes a procedure for simultaneously signal denoising and variance tracking, while being implementable as an online application. Thanks to its low time and space complexity, our proposition is well fitted to the cases with limited computation resource.
The paper continues as it follows: in Section II we will at first present our TV-based denosing method with an automatic choice of parameter. Then, in Section III we adapt our online implementation to the sliding window. After that, in Section IV, we will present an application of our algorithms: noise variance monitoring, and compare with an existing method. Finally, conclusions and perspectives are depicted.

II. AUTOMATIC TOTAL VARIATION DENOISING METHOD
In this section, we will present the automatic TV-denoising method proposed in [3]. We aim to recover the unknown vector u from the noisy samples y by minimizing (1). The restored signal is given by (2).
Since we work on a finite sample of signal, the solution u * (λ) can be seen as piece-wise constant. We use the segment representation [5] for the constant pieces: a set of index {j, j + 1, · · · , k} of consecutive points whose restored value u * j (λ) = · · · = u * k (λ) is called a segment if it can not be enlarged, which means if u * j−1 (λ) = u * j (λ) (or j = 1) and u * k (λ) = u * k+1 (λ) (or k = n). The segments number of u * (λ) is noted as K(λ). The following notations are introduced for the j th segment: ) and the cutting set N (λ) = {N 1 (λ), · · · , N K (λ)}. By knowing the cutting set N (λ), let with j = 1, · · · , K(λ), the segment length T j = i∈Nj (λ) τ i and the mean value inside j th segment y * j = i∈N j (λ) τiyi Tj . A different value of λ may provide a solution with distinct cutting set: λ = 0 gives u * = y, while λ = ∞ implies a parsimonious solution u * = mean(y). The authors in [4] and [5] show there exists a sequence Λ = (λ 1 , · · · ) such that for every λ ∈ Λ, two segments are merged together by moving λ − η to λ with η → 0 and η > 0. In [3], we propose a rapid algorithm to estimate the dynamic of the restoration in function of λ, and the dynamic is saved in i the value of λ for which the points i and i + 1 are merged into the same segment. Λ • allows the computation of the cutting set and also the restoration (3) for every λ.
Based on the variation of the extremums number (noted g(λ)) of the restoration u * (λ) in function of λ, an adaptive choice of hyper-parameter λ is proposed. The simulations show that our estimation λ ours has a similar performance as the state of the art, all near the optimal choice λ op = arg min |u * (λ) − u net | 2 with u net the original signal. The variation ∆g(λ) = g(λ − η) − g(λ) for every λ ∈ Λ with η → 0 and η > 0 can be estimated simultaneously as the estimation of Λ • .
Besides, we analysed the local influence for Λ • by introducing a new sample at the end of the sequence: only a small part of Λ • will be changed. Based on this local property, we proposed an online algorithm (c.f. Algorithm 2 in [3]) for updating the changed part of Λ • , which is more efficient than the offline estimation. The locality of the TV-denoising method motives the adaption of sliding windows in order to deal with the non-stationary signal by supposing the local stationarity inside the window.

III. ADAPTATION TO SLIDING WINDOWS
In this section, we will present some theoretical elements about the local behaviour of the restoration and adapt the online algorithm to the sliding window.
Let's consider two successive sliding windows w m For the simplify of the presentation, the elements concerning about w m i will be noted with the symbol * , and that for w m i+1 will be noted with the hat symbol. For example, with a given λ,

A. Influence of slide movement
The update of the restored signal and Λ • need to consider the sliding of index from w m i to w m i+1 : a restored signal point is unchanged under the influence of slide movement meanŝ In [3], we have shown the following theorem: The diffusion from the "new" sample y i+m changes only the last part of the restoration of w i m up to the junction of two segments whose sign of the variation We can establish a similar theorem (c.f. Theorem 2) about the influence of the first sample y i for the sliding window w m i : the removing of y i changes only the first part of the restoration.
To sum up, for updating u * (λ) toû(λ), only the first part and the last part of w m i are changed. We introduce the following definitions:

B. Independence between segments
For a given λ (notedλ), the cutting set N (λ) is given by {λ • >λ}. In [3], we showed the points inside a segment of u * (λ) are merged for λ ≤λ, and the value of λ provoking the merge is independent to the points outside the segment. By introducing the virtual segment (c.f. Definition 2), the estimation of Λ • can be broken into some sub-problems for each virtual segment, shown in proposition 1. Combining with Theorem 1 and 2, the elements of {λ • ≤λ} inside the isolated sequence are not influenced by the sliding movement.
We will only talk about the online estimation of Λ •,i+1 from Λ •,i in detail. By following, we note an application of Algorithm 1 in [3] to a given sequence of {y} and {τ } as Λ • = DP-TV({y}, {τ }).
After choosingλ ≥ 0, called the cutting point, the restoration for w m i is u * (λ). We note p and j * p respectively the last point and the last segment of the non left-isolated sequence of u * (λ), l and j * l respectively the first point and the first segment of the non right-isolated sequence of u * (λ). Λ •,i+1 can be splitted into four parts: (1) Some elements of {λ •,i+1 >λ} are changed following Proposition 1; (2) The non left-isolated sequence {λ •,i j ≤λ} for j ≤ p is influenced by the removal of the first point y i ; (3) The non right-isolated sequence {λ •,i j ≤λ} for j ≥ l is influenced by the new point y i+m ; (4) All λ •,i j ≤λ remains the same for p < j < l. We treat at first the unchanged part of Λ •,i+1 : due to the sliding, we have λ •,i+1 1,··· ,p−1 ≤λ} can be estimated by DP-TV(y + b , τ + b ) with the virtual segment: The isolated and non-isolated sequences can be assembled Finally, Λ •,i+1 can be assembled in the following way: with α : Z → Z giving the index of i in the vector d.

Algorithm 1 Adaptation of online implementation to sliding window
Require: (y i , · · · , y i+m−1 ), (τ i , · · · , τ i+m−1 ), (y i+m , τ i+m ) Require: The algorithm adapted for the sliding window is gathered in Algorithm 1. With a nice choice ofλ, only a small part (Λ a , Λ b , Λ d ) of the window w m i+1 needs to be updated from w m i . The overall complexity for estimating the restoration in a window of size m is in O(m).

IV. PERFORMANCE ANALYSIS A. Application: noise variance monitoring
We propose a method to detect the shift of noise's variance based on our restoration method. For an observed signal y of size n, we take a sliding window of size m with m < n. For each window w m i = [i, i + m − 1], we apply our denoising algorithm with the automatic choice of λ on the sequence (y i , · · · , y i+m−1 ) and (τ i , · · · , τ i+m−1 ) for estimating the restored signal u * (λ ours ) = (u * 1 , · · · , u * m ). The windowed restoration residual for j = 1, · · · , m is given by r j = y j+i−1 − u * j (λ ours ). The variance of the residual inside w m i can be estimated by: with the mean value of residual r i = 1 m m j=1 r j . For the simulation, the realisation of noise isˆ j = y j − u net,j with u net the original signal and j = 1, · · · , n. The estimation of noise variance inside w m i is given by Since u * (λ ours ) is a good restoration of y, u * (λ ours ) is similar to u net , which means that σ m * i is close toσ m i inside each window w m i . The noise variance σ m * i is not available for the real data, so we propose to detect the variance shift in using the residual standard deviation vector σ m * = (σ m * 1 , · · · , σ m * n−m+1 ) with σ m * i obtained by (5)

B. Results
For the variance monitoring, the method needs to estimate accurately the noise variance in the ideal case or capture the variation of noise variance in a more realistic case. We use the following criteria to evaluate the performance of variance monitoring: It is indeed the R 2 score between σ m * andσ m after adjusting those two items to the same mean value. The range of RVE is between 0 and 1, and RVE = 1 indicates our estimation explains perfectly the variation of σ m * . We compare our method with Median Absolute Deviation (MAD) following the proposition of [12] and [13] σ = 1.4826 median(By − median(By)) with By = √ 2(y 2 − y 1 , · · · , y n − y n−1 ).
At first, we will fix the window length m = 400. Our proposition requires a parameter q which stands for the length of the approximation of derivative, see p13 in [3] for more details. We apply our method to a simulated piecewise constant signal with the parameter log 10 (q) = 1. An example of y = u net + with ∼ N (0, σ 2 a (t)) and the noise variance estimations for 400-point windows w 400 i and i = 1, · · · , 1601 are shown in Figure 1. Both MAD and our method propose an estimation similar to the variance of the noise realisation for every sliding windows. In this example, our method underestimates the variance, but the variation of our estimation inside each sliding window follows well that of σ 400 . The estimation of MAD propose a precise estimation, Fig. 1: Up: example of simulated signal: y = u net + with ∼ N (0, σ 2 a (t)). Colors : y (red) and u net (blue). Middle: the standard deviation of the noise realisation = y − u net (red line), that estimated by our method (green line) and by MAD (blue line) inside every w 400 i . Down : histogram of non-rightisolated sequence's length inside each sliding window but does not follow the variation ofσ 400 . The lengths of nonright-isolated sequence of each window (shown in Figure 1) are all smaller than the window size m = 400, which means the influence of new sample remains inside each window and validates our assumption about the local influence.
3) U(−d(t), d(t)) with d(t) = 1 + 0.0005t. 4) N (0, σ 2 a (t)) + U(−1, 1). We have done 100 simulations for each type of noise, and the results are gathered in Figure 2. For the most of simulations, our method has RVE > 0.95 and over-performs MAD. The high RVE score indicates the variation of our proposition fits well that of the real values, which allows us to monitor the variation of noise variance for the real signal collected from plants. However, the result of Bias shows our method always underestimates the noise variance, and the bias depends on the type of noise, which means we can not estimate an universal offset for removing this bias in a general case.
The windows length m plays an important role in the restoration and the variance monitoring, and needs to be chosen carefully. A short window can capture the local variation of the noise variance, but the new point (i.e (i + m) th point) may still have a strong influence for the pass (i.e. i − 1, i − 2, · · · ), which limits the restoration performance for the pass points.  We test m = 200, 400, 600 with the noise ∼ N (0, σ 2 a (t)), and the results are shown in Figure 3. A longer window provides a better performance of monitoring. But the local variation of σ 2 will be neglected for a long window, and the stationarity hypothesis inside the window is not validated anymore. The choice of m is out of the scope of this article, and it remains an open question.
To sum up, our method can not provide a precise estimation of the noise's variance values, but our estimation follows well that of the real value with an estimation error depending on the type of noise and the shape of original signal.
One of the applications of our method is to detect the shift of noise variance. The residual variance may stay stable (i.e σ m * i = σ) during the correct functional period, and the noise variance shift can be detected by a prefixed threshold over σ m * i comparing to the stable regime: e.g σ m * i > 1.2σ for some successive sliding windows w m i .

V. CONCLUSION
In this article, we adapt the TV denoising method proposed in [3] to sliding windows based on the local property of the TV-denoising signal. We believe our adaptive choice of λ works also for the non-stationary signal. We applied the adaption to some signals with time varying noise variance. The simulated results shows that the variance of the restoration residuals follows well that of the noise, and this method can be used to monitor the ground noise variance in real time with a limited computation resource. However, the performance of these methods (both restoration and variance monitoring) depends on the choice of window length m which is our ongoing research interest. The application to the real data is also one of on-going works.
ACKNOWLEDGMENT This work has been supported by the EIPHI Graduate School (ANR-17-EURE-0002).