What is the best algorithm to find the center of a wave on a matrix?

Question

Considering that I have a matrix (mXn) like this:

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 0 | 1 | 1 | 2 | 1 | 1 | 0 | 0 | 0 0 | 1 | 4 | 9 | 4 | 1 | 0 | 0 | 0 1 | 2 | 9 | # | 9 | 2 | 1 | 0 | 0 0 | 1 | 4 | 9 | 4 | 1 | 0 | 0 | 0 0 | 1 | 1 | 2 | 1 | 1 | 0 | 0 | 0 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 

Where there is a spot # randomly set. The values near that, are affected in a form of wave. The closer to that spot, closer the value gets to 10.

Which algorithm would work well on finding #, assuming it will be used on larger scales?

EDIT: I am more interested on how to find the the first non-zero number, than find # itself, which is the purpose, but not the real problem. Imagine a huge matrix full of zero and somewhere that # is hiding. The exhaustive part of the algorithm is to find the first non-zero.

Answer 1

Finding the first non-zero value only works when the signal is symmetric and contain no rotation. Consider the following example borrowed from Internet (zero = blue, max = red), note the first-non-zero value is somewhere by the top right corner:

_{(source: mathworks.com)}

You might want to have a look at gradient descent. The general algorithm is defined for continuous functions (yours is discrete), but you can still use it.

It basically gets initialized somewhere in your matrix, looks for the gradient at that point and moves in that direction, then repeat until it converges. You can initialize it by sampling randomly (pick a random cell until you get to a non-zero value, you could expect this to be faster than traversing and finding a non zero value in average, naturally depending on your matrix and signal size)

Some properties:

• Generally faster than an exhaustive search (iterating whole matrix)
• The bigger the search space gets (matrix) the faster it is comparatively with an exhaustive search.
• You are still fine even when the signal is not symmetric and centred (first non-zero aligned with the maximum value), can handle more complex signals!
• The same method can be used for 1 dimensional signals or scale to n-dimensions (which is kind-of cool if you think about it, and quite useful too :] )

Limitations:

• It can oscillate forever without converge to a value, specially on a discrete function, you need to handle this case in your code.
• You are not guaranteed to find the global maximum (can get caught in a local one, there are methods to overcome this)
• You need to either interpolate your function (not all, just a few cells, not a difficult thing to do, I wouldn't use linear interpolation) or make some adaptations to the algorithm (calculating the gradient in a discrete function vs. a continuous one, not difficult)

This might be an overkill for you, it might be appropriate, I don't know, you don't provide more detail but it might be worth it to have a look at it. Note that there's a whole family of algorithms, with many variations and optimizations. Have a look at the Wikipedia article first ;)