2
$\begingroup$

I have an image with the size 5575x9440 and I'm implementing a modified version of the algorithm used in this paper on it, but because the code performance is low right now, I have divided the image to 52628 submatrices of the size 25x40 (1000 pixels) and my first experiments show that some lines of code that are marked in the following picture as yellow are not needed at all (meaning that the 2 and 3 degree polynomials always have at least one real positive root) and so there's no need to check it. (Deleting these ten lines will make the code 3rd times faster and I have other plans to accelerate the code further)

enter image description here

Because the code is slow right now, I cannot experiment all of these 52628 matrices and I have to choose a sample size and choose some random matrices to try. But how to calculate the sample size?

What comes below is just to show my effort. And if you're not willing to read it, there's no necessity.


I've already done as follows


This is for lines 121 and 122. The approach for the other two lines (134 and 135) is the same.

We want to test the following hypothesis.

Hypothesis: the line 121, 122 will not be run even one time for the whole image.

Hypothesis(scientifically): We can be 95% or 99% (confidence level) sure that those lines will be run just for 0.25% pixels (confidence interval) of the image.

Up to know I have tried this way:

First of all we have a random variable X = two lines of code that can have just two values: they will run (1) or they will not run(0). So the random variable will have the Bernoulli distribution

For each pixel, this experiment is done 62271 times and so in each submatrix, it will be done 62271000 times independently. So the random variable X = Number of times that the 2 lines are run that its value can be an integer number in the range $[0,62271000]$ is the sum of a huge number (62271000) of bernoulli distributed variables and so X will have a normal distribution according to the Central limit theorem so the random variable Z:
$$Z=\frac{X-np}{\sqrt{npq}}$$


Edit: (Based on the discussion between me and @Wiley in the comments) I should say that from the theoretic concepts of my model, I know that $\Delta>0$ for 2d and 3d polynomials. So the roots are real but it is their sign that determines whether the highlighted cod is needed or not

For 2D Polynomials: there are 4 cases

enter image description here
if there's at least one positive root, the highlighted code is not needed ($p=\frac{3}{4}$)
if all of the roots are negative, the highlighted code is needed. ($q=\frac{1}{4}$)

For 3D Polynomials: there are 8 cases
enter image description here
if there's at least one positive root, the highlighted code is not needed ($p=\frac{7}{8}$)
if all of the roots are negative, the highlighted code is needed. ($q=\frac{1}{8}$)


will have a Standard normal distribution
So for the 3d polynomial we have: $p=\frac{7}{8}\;,q=\frac{1}{8}$ and also $n = 62271000$, so we will have:
$$Z = \frac{X-54487125}{5219}\qquad 0\le X\le 62271000\Rightarrow -10440\le Z\le 1491$$

But from now on, I thinking I'm making some mistakes.


Our confidence interval is 0.25% of pixels
$$0.25\times 0.01\times 5575\times 9440 = 131570$$

meaning that the number of pixels that do not fit our hypothesis should be less than 131570
If we assume that these pixels are distributed homogeneously across the whole image, then the number of pixels in each submatrix that do not fit our hypothesis should be less than:
$$\frac{131570}{52628}=2.5$$
so $0\le X\le 155677.5\Rightarrow -10440\le Z\le -10410$
so our confidence interval is $-10410-(-10440)=30$
and our confidence level is 95% or 99%, means that the probability that $Z$ lies in the above range should be 0.95 or 0.99.
$$p(Z)=N(0,1)=\frac{1}{\sqrt{2\pi}}\exp(-\frac{z^2}{2})$$
$$p(-10440\le Z\le -10410)=\frac{1}{\sqrt{2\pi}} \int_{-10440}^{-10410}\exp(-\frac{z^2}{2})\,dz = 0.95\; \text{or}\; 0.99$$
Then if we consider 52628 matrices as a stochastic process as a collection of 52628 (population) random variables with standard normal distribution, how many members of this process should be experimented (sample size)?

$\endgroup$
9
  • $\begingroup$ I might misunderstand the graphs you posted, but I'm not sure why you think that the probability p=1/2 in your Bernoulli model, given that the code highlighted only ran a few hundred of times out of ~62 million runs. Your objective is to confirm that this probability is tiny so you could remove these lines that are computationally heavy, right? I can see two ways of proceeding: (1) use the data you have collected from these sub-matrices to estimate this probability p and its confidence level, e.g., en.wikipedia.org/wiki/Binomial_proportion_confidence_interval (cont.) $\endgroup$
    – Wiley
    Jun 8 '16 at 21:53
  • $\begingroup$ (2) if you know ab initio what the distribution of d's that go into your quadratic / cubic equations, there are ways to calculate the probability of these equations having a real positive root (based on random matrix theory). $\endgroup$
    – Wiley
    Jun 8 '16 at 22:00
  • $\begingroup$ @Wiley as you see in the tables of the graphs, we have: Code lines that did not run: 2 and those lines are root=0;end;. Because the if statement is never true. (meaning that the 2d/3d polynomials always have at least 1 positive root). Now I say because the code is written for polynomials of $\Delta>0$, which have real roots, the are two possibilities. For a 3d polynomial 1- at least one of the roots is positive ($p=\frac{7}{8}$) the code will not run 2-all of the roots are negative ($q=\frac{1}{8}$) the code will run. And for a 2d polynomial 1- at least one of the roots is $\endgroup$ Jun 9 '16 at 10:36
  • $\begingroup$ @Wiley positive $(p=\frac{3}{4})$ the code will not run 2-all of the roots are negative $(q=\frac{1}{4})$ the code will run. Yes, you were right $\endgroup$ Jun 9 '16 at 10:40
  • $\begingroup$ @Wiley I'm going to take your first way. I have selected 30 of these matrices and I do run my code on those matrices to find that probability and its confidence interval. But what do you mean by your second way? I mean what do you mean by the sentence if you know a initio what the distribution of d's go into your quadratic/cubic equations, I should say that 62271000s aQuardratics and *aCubics are constant across the whole image. And for each pixel the 62271x1 vector of bs in quadratic equation and 62271x1 vectors of b and cs in cubic equation is the same. I mean the vector (cont.) $\endgroup$ Jun 12 '16 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.