# Method for finding the best non-increasing approximation function of a given signal

I have a discrete-time signal (with noise) and I want to determine the best non-increasing function that represents it.

Of course it would be useful if the obtained function were defined in terms of a continuous variable of time, but to me this sounds too general. I think it is not a good idea to specify a particular equation with coefficients to be determined, simply because in so doing I am imposing a too restrictive space of test functions, thus possibly causing "underfitting". For example, I could impose an exponential function like $f(t) = c \, \exp(-\lambda t)$, where $c$ and $\lambda$ are parameters to be determined, but what if the given signal has another form?

For a discrete signal I think it is better try to generate a discrete approximation as well. In this case, the "fit" would be a non-increasing discrete function that is the best representation of the given general signal. Does anybody know a method to do that?

One could use either the raw signal or then a low-pass filter firstly. As a remark I would like to say that polynomial interpolation simply does not work because of the noise.

• That is an interesting open topic in signal processing. How would you characterize the "best", and what features of signal and noise could you disclose? Such a formulation ought to be cast into some optimization problem – Laurent Duval Mar 28 '18 at 20:24
• Can you make it a bit more specific please? ARMA models don't specify equations or coefficients of fitting and neither neural networks when applied to interpolation or prediction. – A_A Mar 28 '18 at 23:54
• A_A, I didn't know about ARMA models. I will take a look on that. Tks. – Diego S. Rodrigues Mar 29 '18 at 2:49
• We can build an optimization problem with constraints of non increasing signal, is that the direction you're after? – Royi Oct 24 '18 at 6:29

You will find some pointers with the correct wording. There is a lot of statistical literature on monotone or monotonic regression (sometimes called isotonic regression). A more generic term is "shape-constrained estimation".

For instance, a few references:

• Constrained statistical inference: inequality, order, and shape restrictions, 2005, Mervyn J. Silvapulle and Pranab Kumar Sen
• Polynomial algorithms for isotonic regression, 1997, Victor Chepoi and Daniel Cogneau and Bernard Fichet
• Fitting monotonic polynomials to data, 1994, Douglas M. Hawkins

The most common version is a least square fit with piecewise constant or linear functions, see for instance Scikit-learn: Isotonic Regression

An illustration of the isotonic regression on generated data. The isotonic regression finds a non-decreasing approximation of a function while minimizing the mean squared error on the training data. The benefit of such a model is that it does not assume any form for the target function such as linearity. For comparison a linear regression is also presented.

With more recent progress in optimization, there are works on fitting under other norms ($$\ell_1$$, $$\ell_\infty$$) and contraints on the lower or upper bound of the derivative, which should be either positive or negative, to impose non-increasing or non-decreasing approximations.

[EDIT:2018/12/24] Now, on the question whether the signal should be low-pass or not: if you think that a paramteric function is too restrictive, a low-pass filter would probably too restrictive as well. Indeed, how do you know that the characteristics or the filter is sufficient? wgy should it be linear? does it cope with the nature of the signal and noise well enough?

What is unacceptable about polynomial fitting (usually called polyfit as a function call)? If your data are non-increasing, the best fit will be too. It is general purpose and doesn't really assume any predefined shape as compared to say a exponential decay function.

This statement of yours, "(I do not want to specify a particular equation and coefficients of fitting, simply because it could be 'anything')", confuses me. That is what you want for a best fit approximation.

Ced

Followup:

Using a polynomial fit is like using an adjustable wrench, it'll work on any sized nut. Of course, a fixed size wrench that fits is going to be better. The adjustable wrench can tell you the size of the fixed size wrench to use.

There are tons of ways to parameterize monotonically decreasing functions. Here are some possibilities:

$$e^{rt}$$

With $r<0$

$$\frac{ a }{ 1 + bt }$$

$$\frac{ a }{ 1 + bt^2 }$$

...

Each of these will have a polynomial expansion with a certain pattern to the coefficients. If you do a general polynomial fit, perhaps you can recognize one these patterns in the coefficients you get.

• Cedron Dawg, I changed the statement that you've pointed out in order to clarity my problem. Thank you. – Diego S. Rodrigues Mar 29 '18 at 2:53
• @DiegoS.Rodrigues, I added a followup. – Cedron Dawg Mar 29 '18 at 19:53
• There are many ways to polynomial fitting. In your "What is unacceptable about polynomial fitting", what are the stakes? It is possible to constrain them with sparsity, convexity, monotony, etc. – Laurent Duval Mar 29 '18 at 20:29
• Instead of ARMA models, I think that Multivariate Adaptive Regression Splines can be better applied, but I do not know if it is possible to impose a non-increasing function for the fit. – Diego S. Rodrigues Apr 11 '18 at 20:54
• @DiegoS.Rodrigues, Could you post a plot of some sample data? I find this "As a remark I would like to say that polynomial fitting fit simply does not work because of the noise." hard to believe. – Cedron Dawg Apr 11 '18 at 22:19