0
$\begingroup$

I have developed an algorithm that counts the number of times a particular block (within a 2D Matrix) crosses zero. Here's an example:

Matrix = {             1, 2, -1, -0.1,             4, 3, -6, -12,             12, 2, -5, 19,             8, -1, 12, -9,           } 

Then the matrix is split into sub-matrices (or blocks)

B1 = {         1, 2,         4, 3      }  B2 = {         -1, -0.1,         -6, -12,      }  ...,  ...,   ... 

An example summing up each of the blocks is:

Ex=∑n|x[n]|2

Find the signum value of each element within the block (will return "1", "-1", "0") respectively.

If the signum value returns -1 then count increments by 1.

This will repeat until the there is no blocks, however, will only produce 1 value per block.

I am looking for a way to put all this process into an equation so I can demonstrate this rather than having to explain the processes in written text everytime. Is this possible?

  • 0
    I've added the "algorithms" tag, but I'm not entirely sure it's a good choice. Someone else please re-tag if you know of an appropriate one.2012-11-21
  • 0
    Suppose your data is $x_1,...x_n$, then $C(x) = |\{i | i = 0,...,n-1, \ \text{sgn} x_i \neq \text{sgn} x_{i+1} \} |$.2012-11-21
  • 0
    I don't understand at all. What do you mean by "block" - a polygon in the plane? What do you mean "crosses zero"?2012-11-21
  • 0
    @gt6989b Basically, a block as in I have a 2D matrix containing 1D blocks of data. By "crosses zero" I mean simply the number of negative values, like in the example, there is 3 negative values so there ZC = 3;2012-11-21
  • 0
    Now I am confused. Maybe you could be explicit about what are the '1D' blocks in your example.2012-11-21
  • 0
    Still not clear. if you have 3 1D blocks of data: $(1,4), (-1,-3), (0.12, -2.3)$, only the last pair crosses zero -- to go from 1 to 4, no 0 is crossed, and neither from -1 to -3?2012-11-21
  • 0
    @gt6989b No, no, apologizes. Basically the example shows 1 block hence "B1" so therefore you could have:
    B1 = {1, 4, -1, -3, 0.12, -2.3}
     (the answer would be 3).. Then another block.. B2 = {1, 2, 5, -21, -0.1} = 2 .. make sense? – 2012-11-21
     
  • 0
    Then the formula above for $C(x)$ will work.2012-11-21
  • 0
    @copper.hat Could you put it as an answer please? Then I can look at it closer, I think I understand what is going on there.2012-11-21
  • 0
    I may have an error. I presume a sequence like $1,...,1,0,0,0,-1,...,-1$ would constitute just one crossing? Would $0,0,0,1,1,1$ constitute a crossing?2012-11-21
  • 0
    @copper.hat I'm confused what you mean. 0, 0, 0, 1, 1, 1 wouldn't constitute a crossing because they are all positive values. Only negative values constitute a negative crossing. The "1,...,1,0,0,0,−1,...,−1" would constitute 1 crossing, for that particular block, but to me, you are representing multiple blocks inside the 2D matrix.2012-11-21
  • 1
    I still don't understand what you mean by 1D and 2D blocks. I presume that $0,-1,0$ is not a crossing either.2012-11-21
  • 0
    @copper.hat I have updated the question, please let me know if this clears things up..2012-11-21
  • 0
    @Phorce Please clarify the criteria you are using to split matrices into blocks. For instance, gt6989b gave an example which had 3 blocks...but you claimed it is only 1 block. Why?2012-11-21
  • 0
    @ErickWong If we forget about the "blocks" and just assumed we have an array of double values.. "0.1, -0.90, ...," would copper.hat's equation be right?2012-11-21

2 Answers 2

2

Suppose your data is $x_1,...,x_n$, then let $C(x) = | \{i | i=0,...,n-1,\ \mathbb{sgn}\, x_i \neq \mathbb{sgn}\, x_{i+1} \} |$.

Unfortunately the above is wrong when $x$ contains zeros. The fix is cumbersome: $$ C(x) = | \{i | i < n,\, \exists j >i,\, j\leq n,\, |\mathbb{sgn}\, x_i -\mathbb{sgn}\, x_j|=2, \, x_{i+1} = \cdots = x_{j-1} = 0 \} |$$ This presumes that $\mathbb{sgn}\, 0 = 0$.

  • 0
    Hey thanks, I just don't understand this bit: "xi≠xi+1" sign(x[i]) which would give either 1, or -1... But why do you have the NOT EQUAL symbol x[i]+1?2012-11-21
  • 0
    To find zero crossings, you find the sign of each value and look for when the sign changes, hence the $\neq$. However, there is an error in the formula above when dealing with zero values. I will fix it or delete it when I get a chance to look at it.2012-11-21
  • 0
    Thank you :)! Let me have a think about this, and see if I can come up with an equation based upon yours.2012-11-21
  • 0
    I think @Mohsen's suggestion of removing zeros first is the simplest fix.2012-11-21
  • 0
    but why = 2? I understand the math just not the 2 ha! Is there any test values that I can use to test this?2012-11-21
  • 0
    It is cumbersome. Take two numbers $x,y \in \{-1,0,1\}$. Then $|x-y| = 2$ iff either ($x=-1$ and $y=1$) or ($x=1$ and $y=-1$). Basically it makes sure that the sequence $x,y$ actually crosses zero.2012-11-21
  • 0
    Thank you :) I understand it a bit better, I'm going to plug some numbers in to see if I can understand it better. Is there a simplified solution to this? This seems a bit too big for such a task.2012-11-21
  • 0
    There might be, but not that I can think of. The main complication is dealing with zeros in the input. If this is a computational issue and the blocks are of fixed size (as in 4 above) I would do an array lookup (on the value $(\mathbb{sgn}\, x_1,...,\mathbb{sgn}\, x_4)$) rather than computing the value. If the purpose is expository, then I am out of ideas :-(.2012-11-21
  • 0
    No no, what you have done is great. I have developed and coded the algorithm and it's perfect, I just needed a way to represent it mathematically. But thank you once again for your help2012-11-21
2

If data is $B=(b_1, b_2, \ldots, b_n)$ and all numbers are nonzero then the number of zero cross-overs will be

$N(B)=\sum_{i=1}^{n-1} \frac{1}{2}|\mathrm{sgn} b_i - \mathrm{sgn} b_{i+1} |$

If you have zeros in the data, you should remove them before applying this, otherwise a closed-form equation would be too cumbersome.

  • 0
    Thank you. But, I don't understand why there is no if statement in the equation (if value[x] == -1)) etc.. Or am I missing the point?2012-11-21
  • 0
    The if is implied in $\frac{1}{2}|\mathrm{sgn} x_i - \mathrm{sgn} x_{i+1} |$. If two consecutive values have similar sign (both positive or negative) this value will be zero, otherwise it will be 1. So summation over this will give you the number of zero cross-overs.2012-11-21
  • 0
    Ok, I understand it.. Just the "−" between the two sgn .. are you representing the values with this line?2012-11-21