Dear,
I am looking for the simplification of a formula to improve the
calculation speed of my program. Therefore I want to simplify the
following formula:
H = sum{i=0..n-1 , [ sum {j=0..m-1 , sqrt ( (Ai - Bj)^2 + (Ci -
Dj)^2) } ] }
where:
A, C = two vectors (with numerical data) of length n
B, D = two vectors (with numerical data) of length m
sqrt = square root
Ai = element of A with index i
Bj = element of B with index j
Ci = element of C with index i
Dj = element of C with index j
I am calculating H in a merging process so A, B will merge in step 2
into A' and C, D into C':
A' = {A,B} : vector of length (n+m)
C' = {C,D} : vector of length (n+m)
Then again I will calculate H with two new vectors X and Y (of length
p):
H = sum{i=0..n+m-1 , [ sum {j=0..p-1 , sqrt ( (A'i - Xj)^2 + (C'i -
Yj)^2) } ] }
These steps are iterated in a loop with always new vectors (e.g. X and
Y)
Now I'am looking for a simplication of H in order to avoid long
calculation time.
I know a computional simplified formula exists for the standard
deviation (sd) that is much easier in iterative programming. Therefore
I wondered I anybody knew about analog simplifications to simplify H:
sd = sqrt [ sum{i=0..n-1, (Xi - mean(X) )^2 ) /n } ] -> simplified
computation
-> sqrt [ (n * sum{i=0..n-1, X^2 } ) - ( sum{i=0..n-1, X } ^2 ) /
n^2 ]
This simplied formula is much easier in iterative programming, since I
don't have to keep every element of X .
For example if we want to calculate sd of A' with the vectors A and C:
sd(A')
= sqrt [ ((n+m) * sum{i=0..n+m-1, A'^2 } ) - ( sum{i=0..n+m-1, A' }
^2 ) / (n+m)^2 ]
= sqrt [ ((n+m)* (sum{i=0..n, A^2 } + sum{i=0..m, C^2 } ) )
- ( ( sum{i=0..n-1, A } + sum{i=0..m-1, C } )^2 ) / (n+m)^2 ]
The advantage of this formula is, that I don't have to keep every value
of A and C to calculate sd(A'). I can do the following replacements:
sum{i=0..n, A^2 } = A2
sum{i=0..m, C^2 } = C2
sum{i=0..n-1, A } = A3
sum{i=0..m-1, C } = C3
So sd(A') sqrt [ ( (n+m)*(A2+ C2) ) - ( (A3 + C3)^2 ) / (n+m)^2 ]
In this way my computation intensive calculation is replaced by a
calculation of simple numbers.
Can anybody help me to do something comparable for H? Any other help to
calculate H easily in an iterative process is also welcome!
Kind regards,
Stef
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
Hello Stefaan, I'm not an expert, but maybe something like this is quite straightforward withourtusing for-loops? (It is an idea I wrote down, but check of course if this is correct!) term1 =(matrix(A,ncol=m,nrow=n)-matrix(B,ncol=m,nrow=n,byrow=TRUE))^2 term2 =(matrix(C,ncol=m,nrow=n)-matrix(D,ncol=m,nrow=n,byrow=TRUE))^2 H = sum(sqrt(term1+term2)) Kind regards, Kristel Stefaan Lhermitte wrote:> Dear, > > I am looking for the simplification of a formula to improve the > calculation speed of my program. Therefore I want to simplify the > following formula: > > H = sum{i=0..n-1 , [ sum {j=0..m-1 , sqrt ( (Ai - Bj)^2 + (Ci - > Dj)^2) } ] } > > where: > A, C = two vectors (with numerical data) of length n > B, D = two vectors (with numerical data) of length m > sqrt = square root > Ai = element of A with index i > Bj = element of B with index j > Ci = element of C with index i > Dj = element of C with index j > > I am calculating H in a merging process so A, B will merge in step 2 > into A' and C, D into C': > A' = {A,B} : vector of length (n+m) > C' = {C,D} : vector of length (n+m) > > Then again I will calculate H with two new vectors X and Y (of length > p): > H = sum{i=0..n+m-1 , [ sum {j=0..p-1 , sqrt ( (A'i - Xj)^2 + (C'i - > Yj)^2) } ] } > > These steps are iterated in a loop with always new vectors (e.g. X and > Y) > > Now I'am looking for a simplication of H in order to avoid long > calculation time. > I know a computional simplified formula exists for the standard > deviation (sd) that is much easier in iterative programming. Therefore > I wondered I anybody knew about analog simplifications to simplify H: > > sd = sqrt [ sum{i=0..n-1, (Xi - mean(X) )^2 ) /n } ] -> simplified > computation > -> sqrt [ (n * sum{i=0..n-1, X^2 } ) - ( sum{i=0..n-1, X } ^2 ) / > n^2 ] > > This simplied formula is much easier in iterative programming, since I > don't have to keep every element of X . > > For example if we want to calculate sd of A' with the vectors A and C: > sd(A') > = sqrt [ ((n+m) * sum{i=0..n+m-1, A'^2 } ) - ( sum{i=0..n+m-1, A' } > ^2 ) / (n+m)^2 ] > = sqrt [ ((n+m)* (sum{i=0..n, A^2 } + sum{i=0..m, C^2 } ) ) > - ( ( sum{i=0..n-1, A } + sum{i=0..m-1, C } )^2 ) / (n+m)^2 ] > > The advantage of this formula is, that I don't have to keep every value > of A and C to calculate sd(A'). I can do the following replacements: > sum{i=0..n, A^2 } = A2 > sum{i=0..m, C^2 } = C2 > sum{i=0..n-1, A } = A3 > sum{i=0..m-1, C } = C3 > > So sd(A')> sqrt [ ( (n+m)*(A2+ C2) ) - ( (A3 + C3)^2 ) / (n+m)^2 ] > > In this way my computation intensive calculation is replaced by a > calculation of simple numbers. > > Can anybody help me to do something comparable for H? Any other help to > calculate H easily in an iterative process is also welcome! > > Kind regards, > Stef > > Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm > > ______________________________________________ > R-help at stat.math.ethz.ch mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html-- _________________________________________________________________ Kristel Joossens Ph.D. Student Faculty of Economics and Applied Economics Research center ORSTAT K.U. Leuven Naamsestraat 69 B-3000 Leuven Belgium Tel: +32 16 326929 Fax: +32 16 326732 E-mail: Kristel.Joossens at econ.kuleuven.be Url: http://www.econ.kuleuven.ac.be/Kristel.Joossens/public/ Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
you could consider something like:
H <- sum(sqrt(outer(A, B, "-")^2 + outer(C, D, "-")^2))
I hope it helps.
Best,
Dimitris
----
Dimitris Rizopoulos
Ph.D. Student
Biostatistical Centre
School of Public Health
Catholic University of Leuven
Address: Kapucijnenvoer 35, Leuven, Belgium
Tel: +32/(0)16/336899
Fax: +32/(0)16/337015
Web: http://www.med.kuleuven.be/biostat/
http://www.student.kuleuven.be/~m0390867/dimitris.htm
----- Original Message -----
From: "Stefaan Lhermitte" <stefaan.lhermitte at biw.kuleuven.be>
To: <r-help at stat.math.ethz.ch>
Sent: Friday, November 04, 2005 10:28 AM
Subject: [R] Simplify iterative programming
> Dear,
>
> I am looking for the simplification of a formula to improve the
> calculation speed of my program. Therefore I want to simplify the
> following formula:
>
> H = sum{i=0..n-1 , [ sum {j=0..m-1 , sqrt ( (Ai - Bj)^2 + (Ci -
> Dj)^2) } ] }
>
> where:
> A, C = two vectors (with numerical data) of length n
> B, D = two vectors (with numerical data) of length m
> sqrt = square root
> Ai = element of A with index i
> Bj = element of B with index j
> Ci = element of C with index i
> Dj = element of C with index j
>
> I am calculating H in a merging process so A, B will merge in step 2
> into A' and C, D into C':
> A' = {A,B} : vector of length (n+m)
> C' = {C,D} : vector of length (n+m)
>
> Then again I will calculate H with two new vectors X and Y (of
> length
> p):
> H = sum{i=0..n+m-1 , [ sum {j=0..p-1 , sqrt ( (A'i - Xj)^2 +
> (C'i -
> Yj)^2) } ] }
>
> These steps are iterated in a loop with always new vectors (e.g. X
> and
> Y)
>
> Now I'am looking for a simplication of H in order to avoid long
> calculation time.
> I know a computional simplified formula exists for the standard
> deviation (sd) that is much easier in iterative programming.
> Therefore
> I wondered I anybody knew about analog simplifications to simplify
> H:
>
> sd = sqrt [ sum{i=0..n-1, (Xi - mean(X) )^2 ) /n } ] -> simplified
> computation
> -> sqrt [ (n * sum{i=0..n-1, X^2 } ) - ( sum{i=0..n-1, X } ^2 )
> /
> n^2 ]
>
> This simplied formula is much easier in iterative programming, since
> I
> don't have to keep every element of X .
>
> For example if we want to calculate sd of A' with the vectors A and
> C:
> sd(A')
> = sqrt [ ((n+m) * sum{i=0..n+m-1, A'^2 } ) - ( sum{i=0..n+m-1,
> A' }
> ^2 ) / (n+m)^2 ]
> = sqrt [ ((n+m)* (sum{i=0..n, A^2 } + sum{i=0..m, C^2 } ) )
> - ( ( sum{i=0..n-1, A } + sum{i=0..m-1, C } )^2 ) / (n+m)^2 ]
>
> The advantage of this formula is, that I don't have to keep every
> value
> of A and C to calculate sd(A'). I can do the following replacements:
> sum{i=0..n, A^2 } = A2
> sum{i=0..m, C^2 } = C2
> sum{i=0..n-1, A } = A3
> sum{i=0..m-1, C } = C3
>
> So sd(A')> sqrt [ ( (n+m)*(A2+ C2) ) - ( (A3 + C3)^2 ) / (n+m)^2
]
>
> In this way my computation intensive calculation is replaced by a
> calculation of simple numbers.
>
> Can anybody help me to do something comparable for H? Any other help
> to
> calculate H easily in an iterative process is also welcome!
>
> Kind regards,
> Stef
>
> Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
>
> ______________________________________________
> R-help at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
>
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm