Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations

28/08/2013
Auteurs : Ben Jeuris
OAI : oai:www.see.asso.fr:2552:4864
DOI :

Résumé

Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations

Métriques

832
215
729.54 Ko
 application/pdf
bitcache://2241e9e4c5d5c9b1d0665116ba31006055be311c

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

logo_gdr-mia.png
logo_inria.png
image010.png
logothales.jpg

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/2552/4864</identifier><creators><creator><creatorName>Ben Jeuris</creatorName></creator></creators><titles>
            <title>Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Mon 16 Sep 2013</date>
	    <date dateType="Updated">Mon 25 Jul 2016</date>
            <date dateType="Submitted">Mon 15 Oct 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">2241e9e4c5d5c9b1d0665116ba31006055be311c</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>9612</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Introduction Generalizations Analysis Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Ben Jeuris KU Leuven, Belgium August 30, 2013 Joint work with Raf Vandebril (KU Leuven, Belgium). Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis The geometric mean The basic idea Outline 1 Introduction The geometric mean The basic idea 2 Generalizations Initial ideas Combining theories 3 Analysis Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis The geometric mean The basic idea Geometric mean: What? Scalar version The geometric mean of positive numbers a1, . . . , ak is defined as k √ a1 · · · ak Generalization to the set of positive definite matrices Pn: problem of non-commutativity Matrix version Definition based on list of properties instead of closed form. Monotonicity Invariance under congruence Invariance under inversion . . . Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis The geometric mean The basic idea Geometric mean: Why? Useful when comparing ratios Interesting in applications where positive definite matrices naturally appear, e.g., DTI Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis The geometric mean The basic idea Geometric mean: Which? Intuitively developed means Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis The geometric mean The basic idea Geometric mean: Which? Intuitively developed means The Karcher mean This mean is defined as the minimizer of the sum of squared distances, measured in the geometry of Pn, the set of positive definite matrices: G(A1, . . . , Ak ) = arg min X∈Pn k i=1 log(A −1/2 i XA −1/2 i ) 2 F Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis The geometric mean The basic idea Geometric mean: How? Riemannian optimization Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis The geometric mean The basic idea Harmonic and arithmetic iterations: scalar version h(a1, a2) = a−1 1 + a−1 2 2 −1 , a(a1, a2) = a1 + a2 2 Algorithm (Two numbers) Let a1, a2 be two positive numbers while a1 = a2 b1 = a(a1, a2); b2 = h(a1, a2); a1 = b1; a2 = b2; end Algorithm converges to g(a1, a2) = √ a1a2. Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis The geometric mean The basic idea Harmonic and arithmetic iterations: matrix version H (A1, A2) = A−1 1 + A−1 2 2 −1 , A(A1, A2) = A1 + A2 2 Algorithm (Two matrices) Let A1, A2 be two positive definite matrices while A1 = A2 B1 = A(A1, A2); B2 = H (A1, A2); A1 = B1; A2 = B2; end Algorithm converges to G(A1, A2) = A1 A−1 1 A2 1/2 . Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Initial ideas Combining theories Outline 1 Introduction The geometric mean The basic idea 2 Generalizations Initial ideas Combining theories 3 Analysis Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Initial ideas Combining theories Crude midpoint guess Immediate generalization Algorithm (Crude guess) Let A1, . . . , An be n positive matrices B1 = A(A1, . . . , An); B2 = H (A1, . . . , An); The result is G(B1, B2). – Very rough approximation + Cheap to compute + Some properties are satisfied, e.g., invariance under inversion Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Initial ideas Combining theories Circular mean Suggested by M. Palfia Generalization of any mean of two matrices Order dependent Algorithm (Circular mean) Let A1, . . . , An be n positive matrices while not converged For all i set Bi = G(Ai , A(i mod n)+1); For all i set Ai = Bi . end Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Initial ideas Combining theories Circular mean Convergence to elliptic setting Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Initial ideas Combining theories Circular mean Convergence to elliptic setting Introduce a randomization Algorithm (Randomized circular mean) Let A1, . . . , An be n positive matrices while not converged For all i set Bi = G(Ai , A(i mod n)+1); For all i set Ap(i) = Bi , with p a random permutation of [1, . . . , n]. end Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Initial ideas Combining theories Circular mean 0.2625 0.263 0.2635 0.264 0.2645 0.265 0.2655 0.2660.29 0.295 0.3 0.785 0.79 0.795 0.8 0.805 0.81 0.815 0.262 0.264 0.266 0.268 0.2860.2880.290.2920.2940.2960.2980.3 0.788 0.79 0.792 0.794 0.796 0.798 0.8 0.802 0.804 0.806 0.808 Approximately close results Randomized results similar proximity to Karcher mean Results all appear in plain, as suggested by A. Elmachtoub and C. Van Loan Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Initial ideas Combining theories Symmetric function means T-mean and P-mean, based on electrical networks In each iteration, n-tuple of matrices updates using functions Ti,n or Pi,n, i = 1, . . . , n T1,n = P1,n = A Tn,n = Pn,n = H Algorithm Let A1, . . . , An be n positive matrices while not converged For all i set Bi = Ti,n(A1, . . . , An); For all i set Ai = Bi . end Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Initial ideas Combining theories Harmonic and arithmetic iterations Combine original algorithm with circular mean Algorithm (HA mean) Let A1, . . . , An be n positive matrices For all i set Bi = Ai and Ci = Ai ; while not converged For all i set ˜Bi = H (Bi , C(i mod n)+1); For all i set ˜Ci = A(Bi , C(i mod n)+1); For all i set Ci = ˜Ci , Bi = ˜Bi . end Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Initial ideas Combining theories Harmonic and arithmetic iterations Observations Sets B and C converge fast to each other Same convergence to elliptic setting as the circular mean, randomization introduced Properties similar to circular mean Results appear close to Karcher mean and in the same plane as circular mean Fixed stepsize and randomized results display similar accuracy Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Outline 1 Introduction The geometric mean The basic idea 2 Generalizations Initial ideas Combining theories 3 Analysis Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Computational speed 2 4 6 8 10 10 −4 10 −3 10 −2 10 −1 10 0 10 1 Number of matrices Computationaltime(s) Crude Circ fixed HA fixed HA rand Randomized algorithms faster than when using fixed stepsize Crude guess is very fast Symmetric function means suffer from recursive definition Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Distance to Karcher mean 10 0 10 5 10 10 10 −2 10 −1 10 0 10 1 Order of magnitude of condition number DistancetotheKarchermean Crude T Circ fixed HA rand Circ fixed, Circ rand, HA fixed, and HA rand all give very similar accuracy Crude guess is very rough approximation Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Initial guess Table: Number of iterations required for the Conjugate Gradient algorithm for the Karcher mean to converge, using the specified mean as an initial guess (averaged over some repetitions). condition number 1e1 1e8 Circular, fixed 15 14 Circular, random 15 15 Crude guess 18 17 HA, fixed 14 11 HA, random 16 13 T-mean 16 15 P-mean 18 17 Arithmetic mean 19 16 Harmonic mean 21 17 CHEAP mean 15 16 Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis Conclusion No fixed standard for generalization of arithmetic-harmonic algorithm Randomization to avoid elliptic setting resulted in speed-up without loss of accuracy HA fixed mean appears optimal, both as approximation and as intial guess for the Karcher mean Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations Introduction Generalizations Analysis References Foster, D., Phillips, G.: The arithmetic-harmonic mean. Mathematics of Computation 42, 183191 (1984) Palfia, M.: A multivariable extension of two-variable matrix means. SIAM Journal on Matrix Analysis and Applications 32(2), 385393 (2011) Elmachtoub, A., Van Loan, C.: From random polygon to ellipse: an eigenanalysis. SIAM Review 52(1), 151170 (2010) Thank you Ben Jeuris Geometric Mean Algorithms Based on Harmonic and Arithmetic Iterations