Smoothness of Discrete Functions

In summary, there is a concept of smoothness for discrete functions that measures how much the objective function result changes when the input is altered by a minimum amount. This is similar to the concept of smoothness for differentiable functions, but there are also other methods such as the calculus of finite differences and the definition of smoothness in actuarial science. A discrete function is considered smooth if the function grows at a rate of Θ(n) and is not smooth if it grows at a rate of o(n).
  • #1
The Number Juggler
1
0
Hi Physics Forums

Is there a specific technique to measure how smooth a discrete function is?

By smooth I mean that if you change the input by a minimum amount then you know that the objective function result will not have a big jump.

For example The Closest String Problem is completely smooth function, since if you change the input string by only one letter, then the distance to the furthest string will change by at most one.

The Traveling Salesman Problem is also smooth, but not completely so. If you change only the order that you visit two cities then the total distance traveled could not change as much as if you altered more. However there could be larger and smaller jumps.

Moving around a grid of random numbers would be completely unsmooth.

I'm sure there must be another word for this phenomena and some research done already. But google is providing anything except "smoothing discrete functions" which is a completely different thing altogether!
 
Physics news on Phys.org
  • #2
The Number Juggler said:
Hi Physics Forums

Is there a specific technique to measure how smooth a discrete function is?

By smooth I mean that if you change the input by a minimum amount then you know that the objective function result will not have a big jump.

It isn't clear what you have in mind for the domain of the function - one real variable ?, a vector of variables ?

If you want to look at methods that are analogous to those used for differentiable functions (e.g. first derivative being bounded or partial derivatives being bounded) investigate "the calculus of finite differences".
 
  • #3
The only thing I can recall is a function is from actuarial science: Barnett n-th order smooth iff ##|{\Delta^n a_x}| \cdot 7^n < a_x##. But this is really for life tables.
 
  • #4
A discrete function is smooth if f(2n) = Θ(n) (theta of n). If f(2n) = o(n), it is not smooth. Source: Algorithms by Neapolitan, Appendix B.2.
 

1. What is the definition of smoothness in discrete functions?

In discrete functions, smoothness refers to the property of a function being continuous and having continuous derivatives up to a certain order. This means that the function has no abrupt changes or corners, and can be represented by a smooth curve.

2. How is smoothness of a discrete function measured?

The smoothness of a discrete function is measured by the number of continuous derivatives it has. This is known as the order of smoothness. A function with higher order of smoothness will have more continuous derivatives, indicating a smoother curve.

3. Why is smoothness important in discrete functions?

In many applications, discrete functions are used to model real-world phenomena. Smoothness is important because it allows us to accurately describe and predict the behavior of these phenomena. Additionally, smooth functions are easier to work with in mathematical calculations and often have more desirable properties.

4. Can a discrete function be both smooth and non-smooth?

No, a discrete function cannot be both smooth and non-smooth. A function can be either smooth or non-smooth, depending on its properties. However, a function can have both smooth and non-smooth regions, where it is smooth in some parts and non-smooth in others.

5. How can we improve the smoothness of a discrete function?

The smoothness of a discrete function can be improved by using interpolation methods or applying smoothing techniques, such as averaging or filtering. These methods can help reduce the noise and make the function appear smoother. Additionally, choosing a higher order of interpolation or using a larger dataset can also improve the smoothness of a function.

Similar threads

  • Beyond the Standard Models
Replies
7
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
734
  • Differential Geometry
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
14
Views
1K
  • Introductory Physics Homework Help
Replies
17
Views
2K
  • Calculus and Beyond Homework Help
Replies
11
Views
3K
Replies
18
Views
1K
  • Special and General Relativity
2
Replies
51
Views
2K
  • Beyond the Standard Models
Replies
2
Views
2K
Back
Top