Multicomponent Decompositions for a Sample of S0 galaxies

a r X i v :a l g -g e o m /9506012v 1 19 J u n 1995Semiorthogonal decompositionsfor algebraic varieties.A.BondalD.OrlovAlgebra section,Slaviansky br.Steklov Math Institute d.9,corp.4Vavilova 42,kv.80117333Moscow 121352Moscow RUSSIARUSSIAMarch 6,19951SEMIORTHOGONAL DECOMPOSITIONS FOR ALGEBRAIC V ARIETIESAbstractA criterion for a functor between derived categories of coherent sheaves to befull and faithful is given.A semiorthogonal decomposition for the derived cate-gory of coherent sheaves on the intersection of two even dimensional quadrics isobtained.The behaviour of derived categories with respect to birational trans-formations is investigated.A theorem about reconstruction of a variety from thederived category of coherent sheaves is proved.Contents0Introduction.2 1Full and faithful functors.4 2Intersection of two even dimensional quadrics.20 3Birational transformations.314Reconstruction of a variety from the derived category of coherent sheaves.480Introduction.This paper is devoted to study of the derived categories of coherent sheaves on smooth algebraic varieties.Of special interest for us is the case when there exists a functor D b coh(M)−→D b coh(X)which is full and faithful.It appears that some geometrically important constructions for moduli spaces of (semistable)coherent sheaves on varieties can be interpreted as instances of this situa-tion.Conversely,we are convinced that any example of such a functor is geometrically meaningful.2If a functorΦ:D b coh(M)−→D b coh(X)is full and faithful,then it induces a semiorthogonal decomposition(see definition in ch.2)of D b coh(X)with the2–step chain D b coh(M)⊥,D b coh(M) ,where D b coh(M)⊥is the right orthogonal to D b coh(M) in D b coh(X).Decomposing summands of this chain,one can obtain a semiorthogonal decomposi-tion with arbitrary number of steps.Full exceptional sequences existing on some Fano varieties(see[Ko])provide with examples of such decompositions.For this case,every step of the chain is equivalent to the derived category of vector spaces or,in other words,sheaves over the point.This leads to the idea that the derived category of coherent sheaves might be reasonable to consider as an incarnation of the motive of a variety,while semiorthogonal decompositions are a tool for simplification of a motive similar to spliting by projectors in the Grothendieck motive theory.Main result of ch.1is a criterion for fully faithfulness.Roughly speaking,it claims that for a functor D b coh(M)−→D b coh(X)to be full and faithful it is sufficient to satisfy this property on the full subcategory of the one dimensional skyscraper sheaves and its translations.Let us mention that D b coh(M)⊥might be zero.In this case we obtain an equiv-alence of derived categories D b coh(M)∼−→D b coh(X).Examples of such equivalences have been considered by Mukai in[Mu1],[Mu2](see ch.1).In ch.3we prove such equivalences for someflop birational transformations.Ch.2is devoted to description of a semiorthogonal decomposition for D b coh(X), when X is the smooth intersection of two even dimensional quadrics.It appears that if we consider the hyperelliptic curve C which is a double covering of the projective line parametrizing the pencil of quadrics,with ramification in the points corresponding to degenerate quadrics,then D b coh(C)is embedded in D b coh(X)as a full subcategory. The orthogonal to D b coh(C)in D b coh(X)is decomposed in an exceptional sequence (of linear bundles).This allows to identify moduli spaces of semistable bundles(of arbitrary rank)on the curve with moduli spaces of complexes of coherent sheaves on the intersection of quadrics.For rank2bundles such identification is well known(see [DR])and was used for computation of cohomologies of moduli spaces[Bar]and for3verification of the Verlinde formula.In ch.3we investigate the behaviour of D b coh(X)under birational transformations. We prove that for a couple of varieties X and X+related by someflips the category D b coh(X+)has a natural full and faithful embedding in D b coh(X).This suggests the idea that the minimal model program of the birational geometry can be considered as a‘minimization’for the derived category of coherent sheaves in a given birational class.We also explore some cases offlops.Considered examples allow us to state a conjecture that the derived categories of coherent sheaves on varieties connected by a flop are equivalent.Examples of varieties having equivalent derived categories appeal to the question: to which extent a variety is determined by its derived category?In ch.4we prove a reconstruction theorem,which claims that if X is a smooth algebraic variety with ample either canonical or anticanonical sheaf,then another algebraic variety X′having equivalent the derived category of coherent sheaves D b coh(X)≃D b coh(X′)should be biregulary isomorphic to X.As a by-product we obtain a description for the group of auto-equivalences of D b coh(X)provided X has ample either canonical or anticanonical class.We are grateful to Max–Planck–Institute for hospitality and stimulating atmo-sphere.Our special thanks go to S.Kuleshov for help during preparation of this paper. The work was partially supported by International Science Foundation Grant M3E000 and Russian Fundamental Research Grant.1Full and faithful functors.For a smooth algebraic variety X over an algebraically closedfield k of charac-teristic0by D b coh(X)(resp.,D b Qcoh(X))we denote the bounded derived category of coherent(resp.,quasicoherent)sheaves over X.Notations like f∗,f∗,⊗,Hom,H om etc.are reserved for derived functors between derived categories,whereas R i f∗,Hom i, etc.(resp.,L i f∗)denote i–th(resp.,(-i)–th)cohomology of a complex obtained by applying f∗,Hom etc.(resp.,f∗);[n]denotes the translation by n functor in a4triangulated category.Let X and M be smooth algebraic varieties of dimension n and m respec-tively,and E an object of D b coh(X×M).With E one can associate a couple of functorsΦE:D b coh(M)−→D b coh(X),ΨE:D b coh(X)−→D b coh(M).Denote by p andπthe projections of M×X to M and X respectively.M×Xπ−→Xp↓MThenΦE andΨE are defined by the formulas:ΦE(·):=π∗(E⊗p∗(·)),ΨE(·):=p∗(E⊗π∗(·)).The main goal of this chapter is the proof of the followingTheorem1.1Let M and X be smooth algebraic varieties andE∈D b coh(M×X).ThenΦE is full and faithful functor,if and only if the following orthogonality conditions are verified:i)Hom i X(ΦE(O t1),ΦE(O t2))=0for every i and t1=t2.ii)Hom0X(ΦE(O t),ΦE(O t))=k,Hom i X(ΦE(O t),ΦE(O t))=0,for i/∈[0,dimM].Here t,t1,t2are points of M,O ticorresponding skyscraper sheaves.Let us mention that if some full subcategory C⊂D generates D as a triangulated category then for an exact functor D−→D′to be full and faithful it is sufficient to be full on C.Unfortunately,the class of skyscraper sheaves does not generate5D b coh(M)as a triangulated category if dimM>0.At the level of the Grothendieck group K0(M)they generate only the lowest term of the topologicalfiltration.The proof of the theorem is preceded by a series of assertions concerning functors between and objects from the derived categories of complexes of coherent sheaves on smooth varieties.For any object E from D b coh(X)we denote by E∨the dual object:E∨:=H om(E,O X).Lemma1.2The left adjoint functor toΦE isΨE∨⊗π∗ω[n]:=p∗(E∨⊗π∗ωX⊗π∗(·))[n].XProof is given by a series of natural isomorphisms,which come from the adjoint property of functors and Serre duality:Hom(A,π∗(E⊗p∗B))∼=Hom(π∗A,E⊗p∗B)∼=Hom(p∗B,π∗A⊗E∨⊗ωX×M[n+m])∗∼=Hom(B,p∗(π∗(A⊗ωX[n])⊗E∨)⊗ωM[m])∗∼=Hom(p∗(π∗(A⊗ωX[n])⊗E∨),B).The next lemma differs from analogous in[H]in what concerns base change(we consider arbitrary g instead offlat one in[H])and morphism f(we consider only smooth morphism instead of arbitrary one in[H]).Lemma1.3Let f:X→Y be a smooth morphism of relative dimension r of smooth projective varieties and g:Y′→Y a base change,with Y′being a smooth variety.Define X′as the cartesian product X′=X×Y Y′.X′=X×Y Y′g′−→Xf′↓f↓Y′g−→Y6Then there is a natural isomorphism of functors:g ∗f ∗(·)≃f ′∗g ′∗(·).Proof.First,note that the right adjoint functors to g ∗f ∗and f ′∗g ′∗are,respectively,f !g ∗and g ′∗f ′!,where f !denote the right adjoint functor to f ∗.We are going to prove that f !g ∗and g ′∗f ′!are isomorphic.Serre duality gives a natural isomorphismf !(·)≃f ∗(·)⊗ωX/Y [r ].(1)Hence,f !g ∗(·)≃f ∗g ∗(·)⊗ωX/Y [r ].(2)Analogously,g ′∗f ′!(·)≃g ′∗(f ′∗(·)⊗ωX ′/Y ′[r ])≃g ′∗(f ′∗(·)⊗g ′∗ωX/Y [r ]).The latter isomorphism goes from the fact that for a smooth f differentials are compatible with base change (see[H],III,§1,p.141).Then,by the projection formula one hasg ′∗f ′!(·)≃g ′∗f ′∗(·)⊗ωX/Y [r ].(3)By the theorem of flat base change (see [H],II,§5,prop.5.12)one hasg ′∗f ′∗≃f ∗g ∗.Formulas (2)and (3)imply a functorial isomorphism of g ′∗f ′!(·)and f !g ∗(·).There-fore,g ∗f ∗(·)is isomorphic to f ′∗g ′∗(·).Let X,Y,Z be smooth projective varieties and I,J,K objects of D bcoh (X ×Y ),D b coh (Y ×Z )and D b coh (X ×Z ),respectively.Consider the following diagram of pro-jectionsX Y ZZX X YXY ZY Zp p p ππππ121312232π2121131π133332237and the triple of functorsφI:D b coh(X)−→D b coh(Y),ψJ:D b coh(Y)−→D b coh(Z),χK:D b coh(X)−→D b coh(Z),defined by the formulasφI=π212∗(I⊗π112∗(·)),ψJ=π323∗(J⊗π223∗(·)),χK=π313∗(K⊗π113∗(·)).The next proposition from[Mu1]is an analog for derived categories of the compo-sition law for correspondences(see[Ma]).Proposition1.4The composition functor forφI andψJ is isomorphic toχK withK=p13∗(p23∗J⊗p12∗I).Proof.It goes from the following sequence of natural isomorphisms,which uses the projection formula and a base change theorem from[H]:ψJ◦φI(·)∼=π323∗(J⊗π223∗(π212∗(I⊗π112∗(·))))∼=π323∗(J⊗p23∗(p12∗(I⊗π112∗(·))))∼=π323∗p23∗(p23∗J⊗p12∗(I⊗π112∗(·)))∼=π313∗p13∗(p23∗J⊗p12∗I⊗p12∗π112∗(·))∼=π313∗p13∗(p23∗J⊗p12∗I⊗p13∗π113∗(·))∼=π313∗(p13∗(p23∗J⊗p12∗I)⊗π113∗(·)).Proposition1.5Let j:Y֒→X be a smooth irreducible subvariety of codimension d of a smooth algebraic variety X,and K a non-zero object of D b coh(X)satisfying following conditions:a)i∗x K=0,for any closed point x i x֒→X\Y,8b)L i i ∗x K =0,when i /∈[0,d ],for any closed point x i x֒→Y .Theni)K is a pure sheaf (i.e.quasiisomorphic to its zero cohomology sheaf),ii)the support of K is Y .Proof.Let H q be the q–th cohomology sheaf of K .Then,for any point x i x֒→Xthere is spectral sequence with the E 2–term consisting of L p i ∗x (H q )and convergingto cohomology sheaves of i ∗(K ):E −p,q 2=L p i ∗x (H q )⇒Lp −q i ∗x (K )Recall that L i f ∗denotes the (–i)–th cohomology of f ∗in accordance with notations of the analogous left derived functors between abelian categories.If H q max is a non–zero sheaf with maximal q ,then L 0i ∗x Hq maxis intact by differentials while going to E ∞.By assumptions of the proposition L q i ∗x K =0,for q >0and for any point x ∈X .This implies q max ≤0.Considering the sheaf H q with maximal q among those having the support out-side Y ,one obtains by the same reasoning that all H q actually have their support in Y .Let H q min be the non–zero sheaf with minimal q .The spectral sequence is depicted in the following diagram:........................... . . . . . .. . . . .....q mind 2-q max 00000000.....000d 2d 3d 300Consider any component C ⊂Y of the support of H q min .If c is the codimensionof C in X ,then L c i ∗x 0(H q min)=0for a general closed point x 0∈C .It could have been killed in the spectral sequence only by L p i ∗x (H q )with p ≥c +2.But9for any sheaf F the closed subscheme S m(F)of points of cohomological dimension ≥m(see[G])S m(F)= x∈X L p i∗x(F)=0,for some p≥mhas codimension≥m.Therefore,S m(H)with m≥c+2cannot cover C,i.e.there exists a point x0∈C,such that L c i∗x(H q min)survives at infinity in thespectral sequence,hence L c−q min i∗x(K)=0.Then,by assumption b)of the proposition it follows that c−q min≤d.Since C belongs to Y,c≥d,hence q min≥0.In other words,q min=q max and K has the only non–trivial cohomology sheaf H0.This proves i).Now consider L i=L i j∗K.There is a spectral sequence for composition of i∗x and j∗:E−p,−q2=L p i∗x(L q)⇒L p+q i∗x(K).Let L q0be a non–zero sheaf with maximal q.Since the support of K belongs to Y,q0≥d.Again consider a component of the support for L q0.The same reasoning as above shows that if this component is of codimension b,then for somepoint x0in it,L b i∗x(L q0)survives in E∞of the latter spectral sequence.By the assumptions of the proposition we have q0+b≤d.This implies q0=d and b=0. This means that the support of L d is the whole Y.It follows that the support of K coincides with Y.The proposition is proved.Proof of the Theorem1.1.First,let us mention that ifΦE is full and faithful functor,then conditions i)and ii)are verified for obvious reasons.Indeed,it is well known fact that extension groups between skyscraper sheaves in D b coh(M)have the following form:i)Hom i X(O t1,O t2)=0for every i and t1=t2;ii)Hom i X(O t,O t)=Λi T M,t,for i∈[0,dimM],Hom i X(O t,O t)=0,for i/∈[0,dimM].Here t,t1,t2are points of M,T M,t the tangent vector space to M at t,andΛi the i–th exterior power.10Fully faithfulness of ΦE implies that the same relations are valid for imagesΦE (O t )in D b coh (X ).In what follows we prove the inverse statement.Consider composition of ΦE with its left adjoint functor Φ∗E .We are going to prove that the canonical natural transformation α:Φ∗E ◦ΦE →id is an isomorphism of functors.This is equivalent to fully faithfulness of ΦE .Indeed,for any pair ofobjects A,B ∈D b coh (M )the natural homomorphismHom(A ,B )−→Hom(ΦE A ,ΦE B )∼=Hom(Φ∗E ΦE A ,B ),is induced by α.By lemma1.2we haveΦ∗E ∼=ΨE ∨⊗π∗ωX [n ].From proposition 1.4the object K of D b coh (M ×M ),which determines Φ∗E ◦ΦE ,isK =q 13∗(q 23∗(E ∨⊗π∗ωX )⊗q 12∗E )[n ],(4)where the morphisms q 13,q 23,q 12and πare taken from the following diagramM X M q 1X X MX MM M M Mq q 12233πWe need to prove that K is quasiisomorphic to O ∆=∆∗O M ,where ∆:M −→M ×M is the diagonal embedding,because O ∆gives the identity func-tor on D b coh (M ).Let us consider a commutative diagramXj t 1t 2−→M ×X ×M f ↓q 13↓Spec k i t 1t 2−→M ×M11Here i t 1t 2is the embedding of a geometric point (t 1t 2)in M ×M ,and f :X →Spec k the corresponding fibre of q 13over this point.This diagram is useful for computing the fibres of K over points of M ×M .Indeed,by lemma 1.3i ∗t 1t 2K =i ∗t 1t 2q 13∗(q 23∗(E ∨⊗π∗ωX )⊗q 12∗E )[n ]==f ∗j ∗t 1t 2(q 23∗(E ∨⊗π∗ωX )⊗q 12∗E )[n ]=f ∗(j ∗t 1t 2q 23∗(E ∨⊗π∗ωX )⊗j ∗t 1t 2q 12∗E )[n ].(5)From the commutative diagramM X M M q 1X2Xj j t t 11t 2where j t 1is the embedding x →(t 1,x ),and from the definition of ΦE one obtains:j ∗t 1t 2q 12∗E =j ∗t 1E =ΦE (O t 1).(6)Analogously,j ∗t 1t 2q 12∗(E ∨⊗π∗ωX )=ΦE (O t 2)∨⊗ωX .(7)Formulas (5),(6),(7)imply isomorphisms:i ∗t 1t 2K =f ∗(ΦE (O t 1)⊗ΦE (O t 2)∨⊗ωX )[n ]==f ∗(H om (ΦE (O t 2),ΦE (O t 1))⊗ωX )[n ]=Hom(ΦE (O t 1),ΦE (O t 2))∗.(8)The last equality comes from Serre duality on X .Apply proposition 1.5to the diagonal embedding of M in M ×M .By formula(8)and assumptions of the theorem,the object K satisfies the hypothesis of the proposition.Therefore,K is a pure sheaf with the support at the diagonal ∆M .The natural transformation αgives rise to a sheaf homomorphism K →O ∆.It is an epimorphism,because otherwise its image would not generate the stalk of O ∆12at some point(t,t)at the diagonal.But this would imply thatΦE(O∆)has no endomorphisms(that is,the trivial object)in contradiction with assumptions of the theorem.Let F be the kernel of this morphism,i.e.there is an exact sequence of coherent sheaves on M×M:0−→F−→K−→O∆−→0(9)We have to prove that F is trivial.Considering the pull back of the short exact sequence to any point from M×M we obtain a long exact sequence showing that the sheaf F satisfies hypothesis of proposition1.5.It follows from the proposition that the support of F coincides with the diagonal∆M.It is sufficient to prove that the restriction of F to the diagonal is zero.Let us consider for this the commutative diagram:M×X−→M×X×Mp↓↓M∆−→M×Mwhere vertical morphisms are natural projections.Applying lemma1.3to the object (q23∗(E∨⊗π∗ωX)⊗q12∗E)[n]from D b coh(M×X×M)and formula(4)we obtain a formula for the derived functors of the restriction–to–diagonal functor for K:L i∆∗(K)=R n−i p∗(E⊗E∨⊗π∗ωX).Therefore,by the relative version of Serre duality and hypothesis of the theorem∆∗K=O∆,L1∆∗(K)=R1p∗(E⊗E∨)∨.Unfortunately,it is not sufficient to know that the restriction of K to the diagonal is O∆,because K might not be the push forward along∆of a sheaf on M(being,‘situated’on some infinitesimal neighborhood of∆(M)).Furthermore,L1∆∗(O∆)=Ω1M,this means that the long exact sequence,obtained from(9)by tensoring with O∆looks as follows:···−→R1p∗(E⊗E∨)∨β−→Ω1M−→L0∆∗F−→O∆∼−→O∆−→0.13Since the support of F coincides with∆(M),so does the support of L0∆∗F, i.e.L0∆∗F is not a torsion sheaf.Therefore,if L0∆∗F is not zero,then this exact sequence shows thatβ∗:T M−→R1p∗(E⊗E∨)has a non-trivial kernel.Remark.If one considerΦE(O t)as a system of objects from D b coh(X) parametrized by M,then the restriction ofβ∗to any point t from M is,actually, the homomorphism from the deformation theoryT M,t−→Hom1X(ΦE(O t),ΦE(O t)).Therefore,a vectorfield from the kernel ofβ∗gives a direction,which the objects do not change along with.This is in contradiction with the orthogonality assumptions of the theorem.Unfortunately,integrating such an algebraic vectorfield one might obtain non-algebraic curves.For this reason our further strategy is going tofind only a formal one–parameter deformation at one point t0in M,along which E has a formal connexion(analog of trivialization),and then to bring this in contradiction with the property ofΦE(O t)to0 having the support in point t0,which is a consequence of the orthogonality condition.Consider a point t0in M,U an open neighborhood of t0and a non-zero at t0local sectionξ∈H0(U,T M U),which belongs to the kernel ofβ∗.This vector fieldξdefines a formal1–dimensional subschemeΓof the formal neighborhoodˆU of t0in M.The defining ideal of the subscheme consists of the function onˆU having trivial all iterated derivatives alongξat point t0(the zero derivative being the value of a function at t0):I= f∈H0(ˆU,O) ξk(f)|t o=0,for any k≥0 .It follows that the restriction ofβ∗to the tangent bundle TΓ,t ofΓat t0is trivial.Denote EΓthe restriction of E toΓ×X.One has14Hom1Γ×X(p∗TΓ,E∨Γ⊗EΓ)∼=Hom1Γ(TΓ,p∗(E∨Γ⊗EΓ))∼=Hom0Γ(TΓ,R1p∗(E∨Γ⊗EΓ)),(10)since TΓis free(of rank1)onΓ.Let us consider thefirst infinitesimal neighborhood∆1Γof the diagonal∆Γ:Γ×X−→Γ×Γ×X.Pulling EΓback toΓ×Γ×X along thefirst coordinate, then restricting to∆1Γand then pushing forward along the second coordinate,one obtains the object J1(EΓ)∈D b coh(Γ×X)of‘first jets’of EΓ.It is included in an exact triangle:−→EΓ⊗p∗Ω1Γ[1].(11) EΓ⊗p∗Ω1Γ−→J1(EΓ)−→EΓat EHere at E is the so called Atiyah class of E.It can be considered as an element of Hom1Γ×X(p∗TΓ,E∨Γ⊗EΓ).Under identification from(10)at E comes into the restriction ofβ∗toΓ,which is the trivial element of Hom0Γ(TΓ,R1p∗(E∨Γ⊗EΓ)) by the choice ofΓ.We consider EΓas an element of the derived category of quasicoherent sheaves on X.It is naturally endowed with an additional homomorphism A→End X EΓ,where A is an algebra of functions onΓ(isomorphic to k[[t]]).Such a homomorphism we call by A–module structure on EΓ.An A–module structure on EΓinduces A–module structures on EΓ⊗p∗Ω1Γand J1(EΓ),so that morphisms from(11)are compatible with them.Like for usual vector bundles there exists a natural homomorphism in D b Qcoh(X):EΓµ−→J1(EΓ),which is a differential operator of thefirst order with respect to the A–module struc-tures.Triviality of at E implies existence of a morphismJ1(EΓ)ν−→EΓ⊗p∗Ω1Γ,which is a section of thefirst morphism from(11).The composition∇=ν◦µdefines a morphism of quasicoherent sheaves onΓ×X∇:EΓ−→EΓ⊗p∗Ω1Γ,15which is a connexion on EΓalong thefibres of the projection pΓ:Γ×X−→Γin the sense that if t∈A is a function on our formal schemeΓ,then the following equality for morphisms from EΓto EΓ⊗p∗Ω1Γis valid:∇◦t−t◦∇=dt,(12)here t is identified with the corresponding morphism from EΓto EΓand dt denotes the operator of tensor multiplication by dt.SinceΓis a one-dimensional subscheme,Ω1Γis a one-dimensional free A–module. Hence,for the reason of simplicity we can identify EΓwith EΓ⊗p∗Ω1Γby means of tensoring with dt,where t∈A is a formal parameter on the schemeΓ.Then, formula(12)gives the coordinate-impulse relation between∇and t:[∇,t]=1.(13)Lemma1.6Under the above identification of EΓwith EΓ⊗p∗Ω1Γthe morphism ∇◦t is invertible in End X EΓProof.From(13)one has:[∇,t k]=kt k−1.This gives a formula for the inverse to∇◦t:(∇◦t)−1=∞k=0(−1)k t k◦∇kProposition 1.7i)The composition λof ρ×id A with the multiplication morphism E Γ×A −→E Γ:λ:E 0×A ρ×idA −→E Γ×A −→E Γis an isomorphism,in other words it yields trivialization of E Γ.ii)E 0is quasiisomorphic to a complex of coherent sheaves on X .Proof.Let us consider the cone C of λ:E 0×A λ−→E Γ−→C.Restricting this exact triangle to the fibre X 0of p Γover the closed point of Γ(which is,of course,naturally identified with X ),one obtains an exact triangle :E 0λ0−→E Γ X 0−→C X 0.Vanishing of C X 0implies vanishing of C ,hence,for proving i)we need to showthat the left morphism λ0of this triangle is isomorphism.Multiplication by t gives an exact triangle of sheaves on Γ×X :0−→O Γ×X t −→O Γ×X −→O X 0−→0It lifts to an exact triangle:E Γt −→E Γ−→E Γ X 0−→E Γ[1].Consider an octahedral diagram of exact triangles[BBD]:E E E E Gt t λ00ΓΓE ΓX 0ΓBy lemma 4.3∇◦t is an isomorphism.Hence,G is zero object and λ0is an isomorphism.Since E X 0is the restriction of complex of coherent sheaves to X 0,17E0is coherent over X0.Since C X0=G[1]is zero,so is C.Therefore,λis isomorphism.) In order tofinish the proof of theorem1.1let us look at the image L=Φ∗E◦ΦE(O t0 of O tunder the functorΦ∗E◦ΦE:D b coh(M)−→D b coh(M).Recall that by lemma1.2[n].Φ∗E=ΨE∨⊗π∗ωXThe trivialization of E alongΓfrom proposition1.7gives us a similar trivial-ization of E∨⊗π∗ωX.By the definition ofΨthis implies trivialization alongΓof any object from the image ofΦ∗E.Since we know thatΦ∗E◦ΦE is determined by sheaf K,having the diagonal∆(M)as its support,the image L of a skyscraper is a non–zero object from D b coh(M)having t0as the support.sheaf O tThis means that L annihilates by some power I k of the maximal ideal I⊂A. Such an object has a trivialization only if it is zero.Thisfinishes the proof of theorem 1.1.The simplest example of a full and faithful functor D b coh(M)−→D b coh(X)rises in the case when M is a point.In this situation we have the only object E∈D b coh(X), which is an exceptional one:Hom0X(E,E)=k,Hom i X(E,E)=0,for i=0It gives a functor from the derived category of vector spaces over k to D b coh(X).Mukai in[Mu1]and[Mu2]considered two important examples of fully faithful functors between geometric categories.First one is the so called Fourier–Mukai transform.It gives equivalenceD b coh(A)−→D b coh(ˆA)for any abelian variety A and its dualˆA.We briefly recall his construction.18Let A be an abelian variety of dimension g,ˆA its dual abelian variety and P the normalized Poincare bundle on A׈A.AsˆA is a moduli space of invertible sheaves on A,P is a linear vector bundle,and normalization means that both P A׈0 and P 0׈A are trivial.Theorem 1.8([Mu1]).The functorsΦP:D b coh(A)→D b coh(ˆA)andΨP: D b coh(ˆA)→D b coh(A)are equivalences of triangulated categories andΨP◦ΦP∼=(−1A)∗[g],)∗[−g],ΦP◦ΨP∼=(−1ˆAhere(−1A)∗is the auto-equivalence of D b coh(A)induced by the automorphism of multiplication by−1on A.Proof.(see[Mu1]).In the case of a principally polarized abelian variety(A,L),where L is a polar-ization,the dualˆA is identified with A.ThenΦP can be regarded as an auto-equivalence of D b coh(A).ΦP in couple with the functor of tensoring by L generates the action of the Artin braid group B3on three strands.The other example of Mukai is a K3–surface S,while M is a moduli space of stable vector bundles.Specifically,for a smooth K3–surface S one consider the Mukai lattice M(S), which is the image of the Chern homomorphism K0(S)−→H∗(S,C)from the Grothendieck group K0(S)to full cohomology group H∗(S,C).There is the Euler bilinear form on M(S),which for vectors v and v′presented by some sheaves F and F′is defined by the formula:χ(v,v′)= (−1)i dimExt i(F,F′).Since the canonical class is trivial,by Serre duality this form is symmetric.Let v be an isotropic indivisible by integer vector with respect toχ.The coarse moduli space of stable bundles on S,corresponding to v,is again a smooth K3–surface S′.There is a rational correspondence between S and S′.If S′is afine moduli space,then we have the universal vector bundle E on S×S′.19Theorem1.9[Mu2].FunctorΦE:D b coh(S)−→D b coh(S′)is an equivalence of triangulated categories.In the both examples of equivalences the canonical class of varieties(either of abelian one or of a K3–surface)is trivial.In chapter3we construct another example of equivalence between geometric categories usingflops.The centre of such transfor-mation is in a sense trivial with respect to the canonical class.An explanation for this phenomenon is given in chapter4.2Intersection of two even dimensional quadrics.In this chapter we show how theorem1.1helps to construct a semiorthogonal decom-position of the derived category of coherent sheaves on the intersection of two even dimensional quadrics,with one summand being the derived category on a hyperelliptic curve and with the others being generated by single exceptional objects.This result can be considered as a categorical explanation for the description,due to Desale and Ramanan,of moduli spaces of rank2vector bundles on a hyperelliptic curve as a base of a family of projective subspaces belonging to the intersection of two even dimensional quadrics[DR].Our construction gives analogous description for any moduli spaces of bundles on the curve by means of families of complexes of coherent sheaves on the intersection locus.Wefirst recall some definitions and facts concerning exceptional sequences,admis-sible subcategories,Serre functors and semiorthogonal decompositions[Bo],[BK].Let B be a full subcategory of an additive category.The right orthogonal to B is the full subcategory B⊥⊂A consisting of the objects C such that Hom(B,C)=0 for all B∈B.The left orthogonal⊥B is defined analogously.If B is a triangulated subcategory of a triangulated category A,then⊥B and B⊥are also triangulated subcategories.Definition2.1Let B be a strictly full triangulated subcategory of a triangulated category A.We say that B is right admissible(resp.,left admissible)if for each X∈A there is an exact triangle B→X→C,where B∈B and C∈B⊥(resp.,20。

小学下册英语第2单元测验卷(含答案)英语试题一、综合题(本题有100小题，每小题1分，共100分.每小题不选、错误，均不给分)1.The capital of Japan is __________.2.Iron reacts with oxygen to form _______.3.The teacher is _____ (kind/strict) to us.4. A shooting star is actually a _______ that burns up in the atmosphere.5.The chemical symbol for francium is ______.6.My ______ loves to explore new technologies.7.I can use it to ______ (动词) new games. Sometimes, I pretend it is a ______ (角色).8.My dad loves __________ (历史) and shares stories with us.9.The ________ is a famous painting by Leonardo da Vinci.10.The Earth’s shape is not a perfect sphere; it is an ______.11.The _____ (种子) will grow into a new plant.12.The __________ is a famous beach destination in Florida. (迈阿密)13.The penguin is a flightless ______ (鸟) that swims well.14.I enjoy ______ with my friends at the mall. (hanging out)15.The __________ (洞穴) is dark and mysterious.16.I see a ___ (cloud/sky) above.17.The rabbit is ___ (nibbling) on some grass.18.My favorite food is _______.19.I can ________ my toys.20.The country known for its pyramids is ________ (埃及).21.The children are _____ in the classroom. (quiet)22._____ (环境) plays a big role in plant health.23. A __________ is a region known for its cultural heritage.24.The _______ (小狐狸) is quick and clever.25.Chemical engineering involves applying principles of chemistry to design processes for producing _____.26.I like to _____ (捡) shells.27.The chemical symbol for chlorine is __________.28.My grandparents love to ____.29.We need to ___ (clean) our room.30.On weekends, we often visit the _________ (玩具店) to look for new _________ (玩具).31.The chemical formula for ethanol is _____.32.The __________ is a zone of contact between two different rock types.33.Hydraulic systems use fluids to transmit ______.34.What is the name of the longest river in the world?A. AmazonB. NileC. MississippiD. Yangtze答案:B35.My favorite _________ (玩具) teaches me about science.36.We are learning about ___. (plants, eats, sleeps)37.The kitten plays with a _________. (球)38.What is the name of the process plants use to make food from sunlight?A. RespirationB. PhotosynthesisC. FermentationD. Decomposition答案:B39.I see a _____ (狮子) at the zoo.40.The _____ (花期) varies among different plants.41.The __________ (历史的图景) paints a broad picture.42. A ____(community newsletter) informs residents of events and resources.43.Mars has the largest volcano in the ______.44.The city of Honiara is the capital of _______.45.biogeography) studies the distribution of species. The ____46._____ (种植) vegetables is rewarding and fun.47.What is the opposite of "hot"?A. WarmB. CoolC. ColdD. Scorching答案: C48.My friend is a _____ (摄影师) who captures moments.49. A cat's whiskers help it sense ______ (环境).50.The chemical formula for copper(I) oxide is _____.51.Mulching helps to retain ______ in the soil. (覆盖物有助于保持土壤中的水分。

Presented at:2nd Annual IEEE International Conference on ImageProcessing.Washington,DC.October,1995.THE STEERABLE PYRAMID:A FLEXIBLE ARCHITECTURE FOR MULTI-SCALE DERIVATIVE COMPUTATION Eero P Simoncelli William T FreemanGRASP Laboratory,Room335C 3401Walnut St,Rm.335C Philadelphia,PA19104-6228Mitsubishi Electric Research Laboratories201BroadwayCambridge,MA02139ABSTRACTWe describe an architecture for efficient and accuratelinear decomposition of an image into scale and orien-tation subbands.The basis functions of this decomposi-tion are directional derivative operators of any desiredorder.We describe the construction and implementa-tion of the transform.1Differential algorithms are used in a wide vari-ety of image processing problems.For example,gradient measurements are used as afirst stage ofmany edge detection,depth-from-stereo,and op-ticalflow algorithms.Higher-order derivativeshave also been found useful in these applications.Extraction of these derivative quantities may beviewed as a decomposition of a signal via termsof a local Taylor series expansions[1].Another widespread tool in signal and image pro-cessing is multi-scale decomposition.Apart fromthe advantages of decomposing signals into in-formation at different scales,the typical recursiveform of these algorithms leads to large improve-ments in computational efficiency.Many authors have combined multi-scale decom-positions with differential measurements(eg.,[2,3]).In these cases,a multi-scale pyramid isconstructed,and then differential operators(typ-ically,differences of neighboring pixels)are ap-plied to the subbands of the pyramid.Since boththe pyramid decomposition and the derivativeoperation are linear and shift-invariant,we maycombine them into a single operation.The advan-tages of doing so are that the resulting derivativesmay be more accurate(see[4]).In this paper,wepropose a simple,efficient decomposition archi-tecture for combining these two operations.The decomposition is the latest incarnation of2In the wavelet literature,such a transform is known as atight frame[8]Laplacian Pyramid Steerable Pyramidself-inverting(tight frame)no yesovercompleteness4343aliasing in subbands perhaps norotated orientation bands no yesTable1:Properties of the Steerable Pyramid relative to two other well-known multi-scale representations.i y iB(-)L 1(-)2U L 0(H 0()Figure 3:Idealized depiction of filters satisfying the constraints of the block diagram in figure 2.Plots show Fourier spectra over the range 0.3.IMPLEMENTATIONWe have designed filters using weighted least squares techniques in the Fourier domain to ap-proximately fit the constraints detailed above.The resulting filters are fairly compact (typically 99taps)and accurate (reconstruction error on the order of 45dB).Such filters may be designed for different values of ,depending on the appli-cation.For example,a design with a single bandat each scale (1)serves as a (self-inverting)replacement for the Laplacian pyramid.A designwith two bands (2)will compute multi-scale image gradients,which may be used for computa-tions of local orientation,stereo disparity or opti-cal flow.Higher values of correspond to higher order terms in a multi-scale Taylor series.Figure 4illustrates a 3-level steerable pyramid de-composition of a disk image,with1.Shown are the bandpass images and the final lowpass image (the initial highpass image is not shown).As noted above,this pyramid may be used in applications where the Laplacian pyramid has been found useful,such as in image coding.The advantage is that the steerable pyramid is self-inverting,and thus the errors introduce by quan-tization of the subbands will not appear as out-of-band distortions upon reconstruction.Figure 5illustrates a 3-level steerablepyramiddecomposition with3.The filters are Figure 4:A 3-level 1(non-oriented)steer-able pyramid.Shown are the bandpass images and the final lowpass image.directional second derivatives oriented at23023.Such a decomposition can be used for orientation analysis,edge detection,etc.We have explored the use of this decomposition in a number of applications,including image en-hancement,orientation decomposition and junc-tion identification,texture blending,depth-from-stereo,and optical flow.Space limitations prevent full description of these applications here;some previous results are described in [5,6].Figure5:A3-level3(second derivative) steerable pyramid.Shown are the three band-pass images at each scale and thefinal lowpass image.4.REFERENCES[1]J.J.Koenderink and A.J.van Doorn.Rep-resentation of local geometry in the visual system.Biol.Cybern.,55:367–375,1987. [2]B D Lucas and T Kanade.An iterative imageregistration technique with an application to stereo vision.In Proc.Seventh IJCAI,pages 674–679,Vancouver,1981.[3]Peter Burt.Pyramid methods in image pro-cessing.In Proceedings of the First Interna-tional Conference on Image Processing,Austin, November1994.plenary presentation. [4]Eero P Simoncelli.Design of multi-dimensional derivativefilters.In First In-ternational Conference on Image Processing, Austin,Texas,November1994.[5]W T Freeman and E H Adelson.The designand use of steerablefilters.IEEE Pat.Anal.Mach.Intell.,13(9):891–906,1991.[6]Eero P Simoncelli,William T Freeman,Ed-ward H Adelson,and David J Heeger.Shiftable multi-scale transforms.IEEE Trans.Information Theory,38(2):587–607,March 1992.Special Issue on Wavelets.[7]H.Greenspan,S.Belongie,R.Goodman,P.Perona,S.Rakshit,and C.H.Anderson.Overcomplete steerable pyramidfilters and rotation invariance.In Proceedings,CVPR, pages222–228,1994.[8]I Daubechies.Ten lectures on wavelets.InRegional Conference:Society for Industrial and Applied Mathematics,Philadelphia,PA,1992.[9]Eero P Simoncelli and Edward H Adel-son.Non-separable extensions of quadraturemirrorfilters to multiple dimensions.Pro-ceedings of the IEEE:Special Issue on Multi-dimensional Signal Processing,April1990.Also available as MIT Media Laboratory Vi-sion and Modeling Technical Report#119.[10]H Knutsson and G H Granlund.Textureanalysis using two-dimensional quadraturefilters.In IEEE Computer Society Workshop onComputer Architecture for Pattern Analysis andImage Database Management,pages206–213, 1983.。

a rXiv:q uant-ph/981282v218A pr2QUANTUM ENTANGLEMENTS AND ENTANGLED MUTUAL ENTROPY VIACHESLAV P BELAVKIN AND MASANORI OHYA Abstract.The mathematical structure of quantum entanglement is studied and classified from the point of view of quantum compound states.We show that the classical-quantum correspondences such as encodings can be treated as diagonal (d-)entanglements.The mutual entropy of the d-compound and entangled states lead to two different types of entropies for a given quantum state:the von Neumann entropy,which is achieved as the supremum of the information over all d-entanglements,and the dimensional entropy,which is achieved at the standard entanglement,the true quantum entanglement,co-inciding with a d-entanglement only in the case of pure marginal states.The q-capacity of a quantum noiseless channel,defined as the supremum over all entanglements,is given by the logarithm of the dimensionality of the input algebra.It doubles the classical capacity,achieved as the supremum over all d-entanglements (encodings),which is bounded by the logarithm of the dimen-sionality of a maximal Abelian subalgebra.1.Introduction Recently,the specifically quantum correlations,called in quantum physics entan-glements,are used to study quantum information processes,in particular,quantum computation,quantum teleportation,quantum cryptography [19,21,22].There have been mathematical studeis of the entanglements in [20,17,18],in which the entangled state is defined by a state not written as a form k λk ρk ⊗σk with any states ρk and σk .However it is obvious that there exist several correlated states written as separable forms above.Such correlated,or entangled states have been also discussed in several contexts in quantum probability such as quantum mea-surement and filtering [3,4],quantum compound state[1,14]and lifting [2].In thispaper,we study the mathematical structure of quantum entangled states to provide a finer classification of quantum sates,and we discuss the informational degree of entanglement and entangled quantum mutual entropy.We show that the entangled states can be treated as generalized compound states,the nonseparable states of quantum compound systems which are not repre-setable by convex combinations of the product states.The compound states,called o-entangled,are defined by orthogonal decompositions of their marginal states.This2VIACHESLA V P BELA VKIN AND MASANORI OHYAis a particular case of so called separable state of a compound system,the convex combination of the product states which we call c-entangled.The o-entangled com-pound states are most informative among c-entangled states in the sense that the maximum of mutual entropy over all c-entanglements to the quantum system A is achieved on the extreme o-entangled states as the von Neumann entropy S(̺)of a given normal state̺on A.Thus the maximum of mutual entropy over all classical couplings,described by c-entanglements of(quantum)probe systems B to the system A,is bounded by ln rank A,the logarithm of the rank of the vonNeumann algebra A,defined as the dimensionality of the maximal Abelian sub-algebra A◦⊆A.Due to dim A≤(rank A)2,it is achieved on the normal tracial ρ=(rank A)−1I only in the case offinite dimensional A.More general than o-entangled states,the d-entangled states,are defined asc-entangled states by orthogonal decomposition of only one marginal state on the probe algebra B.They can give bigger mutual entropy for a quantum noisy channel than the o-entangled state which gains the same information as d-entangled extremestates in the case of a deterministic channel.We prove that the truly(strongest)entangled states are most informative in thesense that the maximum of mutual entropy over all entanglements to the quantum system A is achieved on the quasi-compound state,given by an extreme entangle-ment of the probe system B=A with coinciding marginals,called standard for agiven̺.The standard entangled state is o-entangled only in the case of Abelian A or pure marginal state̺.The gained information for such extreme q-compound state defines another type of entropy,the quasi-entropy S(̺)which is bigger than the von Neumann entropy S(̺)in the case of non-Abelian A(and mixed̺.)The maximum of mutual entropy over all quantum couplings,described by true quan-tum entanglements of probe systems B to the system A is bounded by ln dim A,the logarithm of the dimensionality of the von Neumann algebra A,which is achieved on a normal tracialρin the case offinite dimensional A.Thus the q-entropy S(̺), which can be called the dimensional entropy,is the true quantum entropy,in con-trast to the von Neumann entropy S(̺),which is semi-classical entropy as it can be achieved as a supremum over all couplings with the classical probe systems B.These entropies coincide in the classical case of Abelian A when rank A=dim A.In the case of non-Abelianfinite-dimensional A the q-capacity C q=ln dim A is achieved as the supremum of mutual entropy over all q-encodings(correspondences),described by entanglements.It is strictly bigger then the classical capacity C=ln rank A of the identity channel,which is achieved as the supremum over usual encodings, described by the classical-quantum correspondences A◦→A.In this short paper we consider the case of a simple algebra A=L(H)for whichsome results are rather obvious and given without proofs.The proofs are given in the complete paper[5]for a more general case of decomposable algebra A to include the classical discrete systems as a particular quantum case,and will be published elsewhere.pound States and EntanglementsLet H denote the(separable)Hilbert space of a quantum system,and A=L(H) be the algebra of all linear bounded operators on H.A bounded linear functional ̺:A→C is called a state on A if it is positive(i.e.,̺(A)≥0for any positive operator A in A)and normalized̺(I)=1for the identity operator I in A.AQUANTUM ENTANGLEMENTS AND ENTANGLED MUTUAL ENTROPY3normal state can be expressed as(1)̺(A)=tr Gκ†Aκ=tr Aρ,A∈A.In(2.1),G is another separable Hilbert space,κis a linear Hilbert-Schmidt operator from G to H andκ†is the adjoint operator ofκfrom H to G.Thisκis called the amplitude operator,and it is called just the amplitude if G is one dimensional space C,corresponding to the pure state̺(A)=κ†Aκfor aκ∈H withκ†κ= κ 2=1, in which caseκ†is the adjoint functional from H to C.Moreover the density operatorρin(2.1)isκκ†uniquely defined as a positive trace class operator P A∈A .Thus the predual space A∗can be identified with the Banach space T(H)of all trace class operators in H(the density operators P A∈A∗,P B∈B∗of the states ̺,ςon different algebras A,B will be usually denoted by different lettersρ,σcorresponding to their Greek variations̺,ς.)In general,G is not one dimensional,the dimensionality dim G must be not less than rankρ,the dimensionality of the range ranρ⊆H of the density operatorρ.We shall equip it with an isometric involution J=J†,J2=I,having the properties of complex conjugation on G,J λjζj= ¯λj Jζj,∀λj∈C,ζj∈Gwith respect to which Jσ=σJ for the positive and so self-adjoint operatorσ=κ†κ=σ†on G.The latter can also be expressed as the symmetricity property ˜ς=ςof the stateς(B)=tr Bσgiven by the real and so symmetric density operator ¯σ=σ=˜σon G with respect to the complex conjugation¯B=JBJ and the tilda operation(G-transponation)˜B=JB†J on the algebra B=L(G).For example,G can be realized as a subspace of l2(N)of complex sequences N∋n→ζ(n)∈C,with n|ζ(n)|2<+∞in the diagonal representation σ=[µ(n)δm n].The involution J can be identified with the complex conjugation Cζ(n)=¯ζ(n),i.e.,C:ζ= n|n ζ(n)→Cζ= n|n ¯ζ(n)in the standard basis{|n }⊂G of l2(N).In this caseκ= κn n|is given by orthogonal eigen-amplitudesκn∈H,κ†mκn=0,m=n,normalized to the eigen-valuesλ(n)=κ†nκn=µ(n)of the density operatorρsuch thatρ= κnκ†n is a Schatten decomposition,i.e.the spectral decomposition ofρinto one-dimensional orthogonal projectors.In any other basis the operator J is defined then by J= U†CU,where U is the corresponding unitary transformation.One can also identify G with H by Uκn=λ(n)1/2|n such that the operatorρis real and symmetric, JρJ=ρ=Jρ†J in G=H with respect to the involution J defined in H by Jκn=κn.Here U is an isometric operator H→l2(N)diagonalizing the operator ρ:UρU†= |n λ(n) n|.The amplitude operatorκ=ρ1/2corresponding to B=A,σ=ρis called standard.Given the amplitude operatorκ,one can define not only the states̺ ρ=κκ† and ς σ=κ†κ on the algebras A=L(H)and B=L(G)but also a pure entanglement state̟on the algebra B⊗A of all bounded operators on the tensor product Hilbert space G⊗H by̟(B⊗A)=tr G˜Bκ†Aκ=tr H Aκ˜Bκ†.4VIACHESLA V P BELA VKIN AND MASANORI OHYAIndeed,thus defined ̟is uniquely extended by linearity to a normal state on the algebra B ⊗A generated by all linear combinations C = λj B j ⊗A j due to̟(I ⊗I )=tr κ†κ=1and ̟ C †C = i,k ¯λi λk tr G ˜B k ˜B †i κ†A †iA k κ= i,k ¯λi λk tr G ˜B †i κ†A †i A k κ˜B k =tr G χ†χ≥0,where χ= j A j κ˜Bj .This state is pure on L (G ⊗H )as it is given by an amplitude ϑ∈G ⊗H defined as(ζ⊗η)†ϑ=η†κJζ,∀ζ∈G ,η∈H ,and it has the states ̺and ςas the marginals of ̟:̟(I ⊗A )=tr H Aρ,̟(B ⊗I )=tr G Bσ.(2)As follows from the next theorem for the case F =C ,any pure state ̟(B ⊗A )=ϑ†(B ⊗A )ϑ,B ∈B ,A ∈A given on L (G ⊗H )by an amplitude ϑ∈G ⊗H with ϑ†ϑ=1,can be achieved by a unique entanglement of its marginal states ςand ̺.Theorem 2.1.Let ̟:B ⊗A →C be a compound state̟(B ⊗A )=tr F υ†(B ⊗A )υ,(3)defined by an amplitude operator υ:F →G ⊗H on a separable Hilbert space F into the tensor product Hilbert space G ⊗H with tr υ†υ=1.Then this state can be achieved as an entanglement̟(B ⊗A )=tr G ˜Bκ†(I ⊗A )κ=tr F⊗H (I ⊗A )κ˜Bκ†(4)of the states (2)with σ=κ†κand ρ=tr F κκ†,where κis an amplitude operator G →F ⊗H .The entangling operator κis uniquely defined by ˜κU =υup to a unitary transformation U of the minimal domain F =dom υ.Note that the entangled state (4)is written as̟(B ⊗A )=tr G ˜Bπ(A )=tr H Aπ∗ ˜B ,(5)where π(A )=κ†(I ⊗A )κ,bounded by A σ∈B ∗for any A ∈L (H ),is in the predual space B ∗⊂B of all trace-class operators in G ,and π∗(B )=tr F κBκ†,bounded by B ρ∈A ∗,is in A ∗⊂A .The map πis the Steinspring form [9]of the general completely positive map A →B ∗,written in the eigen-basis {|k }⊂F of the density operator υ†υas π(A )= m,n|m κ†m (I ⊗A )κn n |,A ∈A (6)while the dual operation π∗is the Kraus form [10]of the general completely positive map A →A ∗,given in this basis as π∗(B )= n,mn |B |m tr F κn κ†m =tr G ˜Bω.(7)QUANTUM ENTANGLEMENTS AND ENTANGLED MUTUAL ENTROPY5 It corresponds to the general form(8)ω= m,n|n m|⊗tr Fκnκ†mof the density operatorω=υυ†for the entangled state̟(B⊗A)=tr(B⊗A)ωin this basis,characterized by the weak orthogonality property(9)tr Fψ(m)†ψ(n)=µ(n)δm nin terms of the amplitude operatorsψ(n)=(I⊗ n|)˜κ=˜κn.Definition2.1.The dual mapπ∗:B→A∗to a completely positive mapπ:A→B∗,normalized as tr Gπ(I)=1,is called the quantum entanglement of the state ς=π(I)on B to the state̺=π∗(I)on A.The entanglement by(10)π◦∗(A)=ρ1/2Aρ1/2=π◦(A)of the stateς=̺on the algebra B=A is called standard for the system(A,̺).The standard entanglement defines the standard compound state̟0(B⊗A)=tr H˜Bρ1/2Aρ1/2=tr H Aρ1/2˜Bρ1/2on the algebra A⊗A,which is pure,given by the amplitudeϑ0associated with̟0 is˜κ0,whereκ0=ρ1/2.Example2.1.In quantum physics the entangled states are usually obtained by a unitary transformation U of an initial disentangled state,described by the density operatorσ0⊗ρ0⊗τ0on the tensor product Hilbert space G⊗H⊗K,that is,̟(B⊗A)=tr U†(B⊗A⊗I)U(σ0⊗ρ0⊗τ0).In the simple case,when K=C,τ0=1,the joint amplitude operatorυis defined on the tensor product F=G⊗H0with H0=ranρ0asυ=U1(σ0⊗ρ0)1/2.The entangling operatorκ,describing the entangled state̟,is constructed as it was done in the proof of Theorem2.1by transponation of the operatorυU†,where U is arbitrary isometric operator F→G⊗H0.The dynamical procedure of such entanglement in terms of the completely positive mapπ∗:A→B∗is the subject of Belavkin quantumfiltering theory[8].The quantumfiltering dilation theorem[8] proves that any entanglementπcan be obtained the unitary entanglement as the result of quantumfiltering by tracing out some degrees of freedom of a quantum environment,described by the density operatorτ0on the Hilbert space K,even in the continuous time case.3.C-and D-Entanglements and EncodingsThe compound states play the role of joint input-output probability measures in classical information channels,and can be pure in quantum case even if the marginal states are mixed.The pure compound states achieved by an entanglement of mixed input and output states exhibit new,non-classical type of correlations which are responsible for the EPR type paradoxes in the interpretation of quantum theory. The mixed compound states on B⊗A which are given as the convex combinations ̟= nςn⊗̺nµ(n),µ(n)≥0, nµ(n)=16VIACHESLA V P BELA VKIN AND MASANORI OHYAof tensor products of pure or mixed normalized states̺n∈A∗,ςn∈B∗as in classical case,do not exhibit such paradoxical behavior,and are usually considered as the proper candidates for the input-output states in the communication chan-nels.Such separable compound states are achieved by c-entanglements,the convex combinations of the primitive entanglements B→tr G Bωn,given by the density operatorsωn=σn⊗ρn of the product states̟n=ςn⊗̺n:(11)π∗(B)= nρn tr G Bσnµ(n),A compound state of this sort was introduced by Ohya[1,15]in order to define the quantum mutual entropy expressing the amount of information transmitted from an input quantum system to an output quantum system through a quantum channel,using a Schatten decompositionσ= nσnµ(n),σn=|n n|of the input density operatorσ.It corresponds to a particular,diagonal type(12)π(A)= n|n κ†n(I⊗A)κn n|of the entangling map(6)in an eigen-basis{|n }∈G of the density operatorσ, and is discussed in this section.Let us consider afinite or infinite input system indexed by the natural numbers n∈N.The associated space G⊆l2(N)is the Hilbert space of the input system described by a quantum projection-valued measure n→|n n|on N,given an orthogonal partition of unity I= |n n|∈B of thefinite or infinite dimensional input Hilbert space G.Each input pure state,identified with the one-dimensional density operator|n n|∈B corresponding to the elementary symbol n∈N,defines the elementary output state̺n on A.If the elementary states̺n are pure,they are described by output amplitudesηn∈H satisfyingη†nηn=1=trρn,where ρn=ηnη†n are the corresponding output one-dimensional density operators.If these amplitudes are non-orthogonalη†mηn=δm n,they cannot be identified with the input amplitudes|n .The elementary joint input-output states are given by the density operators |n n|⊗ρn in G⊗H.Their mixtures(13)ω= nµ(n)|n n|⊗ρn,define the compound states on B⊗A,given by the quantum correspondences n→|n n|with the probabilitiesµ(n).Here we note that the quantum correspondence is described by a classical-quantum channel,and the general d-compound state for a quantum-quantum channel in quantum communication can be obtained in this way due to the orthogonality of the decomposition(13),corresponding to the orthogonality of the Schatten decompositionσ= n|n µ(n) n|forσ=tr Hω.The comparison of the general compound state(8)with(13)suggests that the quantum correspondences are described as the diagonal entanglements(14)π∗(B)= nµ(n) n|B|n ρn,They are dual to the orthogonal decompositions(12):π(A)= nµ(n)|n η†n Aηn n|= n|n η(n)†Aη(n) n|,QUANTUM ENTANGLEMENTS AND ENTANGLED MUTUAL ENTROPY7 whereη(n)=µ(n)1/2ηn.These are the entanglements with the stronger orthogo-nality(15)ψ(m)ψ(n)†=µ(n)δm n,for the amplitude operatorsψ(n):F→H of the decomposition of the amplitude operatorυ= n|n ⊗ψ(n)in comparison with the orthogonality(9).The orthog-onality(15)can be achieved in the following manner:Take in(6)κn=|n ⊗η(n) with m|n =δm n so thatκ†m(I⊗A)κn=µ(n)η†n Aηnδm nfor any A∈A.Then the strong orthogonality condition(15)is fulfilled by the amplitude operatorsψ(n)=η(n) n|=˜κn,andκ†κ= nµ(n)|n n|=σ,κκ†= nη(n)η(n)†=ρ.It corresponds to the amplitude operator for the compound state(13)of the form (16)υ= n|n ⊗ψ(n)U,where U is arbitrary unitary operator from F onto G,i.e.υis unitary equivalent to the diagonal amplitude operatorκ= n|n n|⊗η(n)on F=G into G⊗H.Thus,we have proved the following theorem in the case of pure output statesρn=ηnη†n.Theorem3.1.Letπbe the operator(13),defining a d-compound state of the form (17)̟(B⊗A)= n n|B|n tr F nψ†n Aψnµ(n)Then it corresponds to the entanglement by the orthogonal decomposition(12)map-ping the algebra A into a diagonal subalgebra of B.Note that(2.9)defines the general form of a positive map on A with values in the simultaneously diagonal trace-class operators in A.Definition 3.1.The completely positive convex combination(11)is called c-entanglement,and is called d-entanglement,or quantum encoding if it has the diag-onal form(14)on B.The d-entanglement is called o-entanglement and compound state is called o-compound if all density operatorsρn are orthogonal:ρmρn=ρnρm for all m and n.Note that due to the commutativity of the operators B⊗I with I⊗A on G⊗H, one can treat the correspondences as the nondemolition measurements[4]in B with respect to A.So,the compound state is the state prepared for such measurements on the input G.It coincides with the mixture of the states,corresponding to those after the measurement without reading the sent message.The set of all d-entanglements corresponding to a given Schatten decomposition of the input stateσon B is obviously convex with the extreme points given by the pure output statesρn8VIACHESLA V P BELA VKIN AND MASANORI OHYAon A,corresponding to a not necessarily orthogonal decompositionsρ= nρ(n) into one-dimensional density operatorsρ(n)=µ(n)ρn.The Schatten decompositionsρ= nλ(n)ρn correspond to the extreme d-entanglements,ρn=ηnη†n,µ(n)=λ(n),characterized by orthogonalityρmρn=0, m=n.They form a convex set of d-entanglements with mixed commutingρn for each Schatten decomposition ofρ.The orthogonal d-entanglements were used in[7] to construct a particular type of Accardi’s transitional expectations[6]and to define the entropy in a quantum dynamical system via such transitional expectations.The established structure of the general q-compound states suggests also the general formΦ∗(B,̺0)=tr FX†(B⊗ρ0)X=tr G ˜B⊗I Y(I⊗ρ0)Y†1of transitional expectationsΦ∗:B×A◦∗→A∗,describing the entanglementsπ∗=Φ∗(̺0)of the statesς=π(I)to̺=π∗(I)for each initial state̺0∈A◦∗with the density operatorρ0∈A◦⊆L(H0)byπ∗(B)=tr Fκ(B⊗I)κ†,whereκ=X†(I⊗ρ0)1/2.It is given by an entangling transition operator X:F⊗H→G⊗H0, which is defined by a transitional amplitude operator Y:H0⊗F→G⊗H up to a unitary operator U in F as(ζ⊗η0)†X(Uξ⊗η)=(η0⊗Jξ)†Y†(Jζ⊗η).The dual mapΦ:A→B∗⊗A◦is obviously normal and completely positive, (18)Φ(A)=X(I⊗A)X†∈B∗⊗A◦,∀A∈A,with tr GΦ(I)=I◦,and is calledfiltering map with the output statesΦ(I)(I⊗ρ0)ς=tr Hin the theory of CPflows[8]over A=A◦.The operators Y normalized as tr F Y†Y=I◦describe A-valued q-compound statesE(B⊗A)=tr F Y†(B⊗A)Y=tr G ˜B⊗I Φ(A),defined as the normal completely positive maps B⊗A→A◦with E(I⊗I)=I◦.If the A-valued compound state has the diagonal form given by the orthogonal decomposition(19)Φ(A)= n|n tr FΨ(n)†AΨ(n) n|,corresponding to Y= n|n ⊗Ψ(n),whereΨ(n):H0⊗F→H,it is achieved by the d-transitional expectationsΦ∗(B,̺0)= n n|B|n Ψ(n)(ρ0⊗I)Ψ(n)†.The d-transitional expectations correspond to the instruments[11]of the dynamical theory of quantum measurements.The elementaryfilters1Θn(A)=QUANTUM ENTANGLEMENTS AND ENTANGLED MUTUAL ENTROPY9 define posterior states̺n=̺0Θn on A for quantum nondemolition measurements in B,which are called indirect if the corresponding density operatorsρn are non-orthogonal.They describe the posterior states with orthogonalρn=Ψn(ρ0⊗I)Ψ†n,Ψn=Ψ(n)/µ(n)1/2for allρ0iffΨ(n)†Ψ(n)=δm n M(n).4.Quantum Entropy via EntanglementsAs it was shown in the previous section,the diagonal entanglements describe the classical-quantum encodingsκ:B→A∗,i.e.correspondences of classical symbols to quantum,in general not orthogonal and pure,states.As we have seen in contrast to the classical case,not every entanglement can be achieved in this way.The general entangled states̟are described by the density operators ω=υυ†of the form(8)which are not necessarily block-diagonal in the eigen-representation of the density operatorσ,and they cannot be achieved even by a more general c-entanglement(11).Such nonseparable entangled states are called in[15]the quasicompound(q-compound)states,so we can call also the quantum nonseparable correspondences the quasi-encodings(q-encodings)in contrast to the d-correspondences,described by the diagonal entanglements.As we shall prove in this section,the most informative for a quantum system (A,̺)is the standard entanglementπ◦∗=π0of the probe system(B◦,ς0)=(A,̺), described in(10).The other extreme cases of the self-dual input entanglementsπ∗(A)= nρ(n)1/2Aρ(n)1/2=π(A),are the pure c-entanglements,given by the decompositionsρ= ρ(n)into pure statesρ(n)=ηnη†nµ(n).We shall see that these c-entanglements,corresponding to the separable states(20)ω= nηnη†n⊗ηnη†nµ(n),are in general less informative then the pure d-entanglements,given in an orthonor-mal basis{η◦n}⊂H byπ◦(A)= nη◦nη†n Aηnη◦†nµ(n)=π◦∗(A).Now,let us consider the entangled mutual entropy and quantum entropies of states by means of the above three types of compound states.To define the quantum mutual entropy,we need the relative entropy[12,13,23]of the compound state ̟with respect to a reference stateϕon the algebra A⊗B.It is defined by the density operatorsω,φ∈B⊗A of these states as(21)S(̟,ϕ)=trω(lnω−lnφ).It has a positive value S(̟,ϕ)∈[0,∞]if the states are equally normalized,say (as usually)trω=1=trφ,and it can befinite only if the state̟is absolutely continuous with respect to the reference stateϕ,i.e.iff̟(E)=0for the maximal null-orthoprojector Eφ=0.10VIACHESLA V P BELA VKIN AND MASANORI OHYAThe mutual entropy Iω(A,B)of a compound state̟achieved by an entangle-mentπ∗:B→A∗with the marginalsς(B)=̟(B⊗I)=tr G Bσ,̺(A)=̟(I⊗A)=tr H Aρis defined as the relative entropy(21)with respect to the product stateϕ=ς⊗̺:(22)I A,B(̟)=trω(lnω−ln(σ⊗I)−ln(I⊗ρ)).Here the operatorωis uniquely defined by the entanglementπ∗as its density in (7),or the G-transposed to the operator˜ωinπ(A)=κ†(I⊗A)κ=tr H A˜ω.This quantity describes an information gain in a quantum system(A,̺)via an entanglementπ∗of another system(B,ς).It is naturally treated as a measure of the strength of an entanglement,having zero value only for completely disentangled states,corresponding to̟=ς⊗̺.The following proposition follows from the monotonicity property[24,16] (23)̟=K∗̟0,ϕ=K∗ϕ0⇒S(̟,ϕ)≤S(̟0,ϕ0).of the general relative entropy on a von Neuman algebra M with respect to the predual K∗to any normal completely positive unital map K:M→M◦. Proposition4.1.Letπ◦∗:B◦→A∗be an entanglementπ◦∗of a stateς0=π◦(I) on a discrete decomposable algebra B◦⊆L(G0)to the state̺=π◦∗(I)on A,and π∗=π◦∗K be an entanglement defined as the composition with a normal completely positive unital map K:B→B◦.Then I A,B(̟)≤I A,B◦(̟0),where̟,̟0 are the compound states achieved byπ◦∗,π∗respectively.In particular,for any c-entanglementπ∗to(A,ς)there exists a not less informative d-entanglementπ◦∗=κwith an Abelian B◦,and the standard entanglementπ0(A)=ρ1/2Aρ1/2ofς0=̺on B◦=A is the maximal one in this sense.Note that any extreme d-entanglementπ◦∗(B)= n n|B|n ρ◦nµ(n),B∈B◦,withρ= nρ◦nµ(n)decomposed into pure normalized statesρ◦n=ηnη†n,is maxi-mal among all c-entanglements in the sense I A,B(̟0)≥I A,B(̟).This is because trρ◦n lnρ◦n=0,and therefore the information gainI A,B(̟)= nµ(n)trρn(lnρn−lnρ).with afixedπ∗(I)=ρachieves its supremum−tr Hρlnρat any such extreme d-entanglementπ◦∗.Thus the supremum of the information gain(22)over all c-entanglements to the system(A,̺)is the von Neumann entropy(24)S A(̺)=−tr Hρlnρ.It is achieved on any extremeπ◦∗,for example given by the maximal Abelian subal-gebra B◦⊆A,with the measureµ=λ,corresponding to a Schatten decomposition ρ= nη◦nη◦†nλ(n),η◦†mη◦n=δm n.The maximal value ln rank A of the von Neumann entropy is defined by the dimensionality rank A=dim B◦of the maximal Abelian subalgebra of the decomposable algebra A,i.e.by dim H.QUANTUM ENTANGLEMENTS AND ENTANGLED MUTUAL ENTROPY11Definition4.1.The maximal mutual entropyS A(̺)=supπ∗(I)=ρI A,B(̟)=I A,B◦(̟0),(25)achieved on B◦=A by the standard q-entanglementπ◦∗(A)=ρ1/2Aρ1/2for afixed state̺(A)=tr H Aρ,is called q-entropy of the state̺.The differencesS B|A(̟)= S B(ς)−I A,B(̟)S B|A(̟)=S B(ς)−I A,B(̟)are respectively called the q-conditional entropy on B with respect to A and the degree of disentanglement for the compound state̟. Obviously, S B|A(̟)is positive in contrast to the disentanglement S B|A(̟), having the positive maximal value S B|A(̟)=S B(ς)in the case̟=ς⊗̺of complete disentanglement,but which can achieve also a negative valueinf π∗(I)=ρD B|A(̟)=S A(ς)− S A(̺)=trρlnρ(26)for the entangled states as the following theorem states.Obviously S A(̺)= S A(̺) if the algebra A is completely decomposable,i.e.Abelian,and the maximal value ln rank A of S A(̺)can be written as ln dim A in this case.The disentanglement S B|A(̟)is always positive in this case,as well as in the case of Abelian B when S B|A(̟)= S B|A(̟).Theorem4.2.The q-entropy for the simple algebra A=L(H)is given by the formulaS A(̺)=−2tr Hρlnρ=2S A(ρ),(27)It is positive, S A(̺)∈[0,∞],and if A isfinite dimensional,it is bounded,with the maximal value S A(̺◦)=ln dim A which is achieved on the tracialρ◦=(dim H)−1I, where dim A=(dim H)2.5.Quantum Channel and its Q-CapacityLet H0be a Hilbert space describing a quantum input system and H describe its output Hilbert space.A quantum channel is an affine operation sending each input state defined on H0to an output state defined on H such that the mixtures of states are preserved.A deterministic quantum channel is given by a linear isometry Y:H0→H with Y†Y=I◦(I◦is the identify operator in H0)such that each input state vectorη∈H0, η =1is transmitted into an output state vector Yη∈H, Yη =1.The orthogonal mixturesρ0= nµ(n)ρ◦n of the pure input statesρ◦n=η◦nη◦†n are sent into the orthogonal mixturesρ= nµ(n)ρn of the corresponding pure statesρn=Yρ◦n Y†.A noisy quantum channel sends pure input states̺0into mixed ones̺=Λ∗(̺0) given by the dualΛ∗to a normal completely positive unital mapΛ:A→A0,Λ(A)=tr F1Y†AY,A∈Awhere Y is a linear operator from H0⊗F+to H with tr F+Y†Y=I◦,and F+is a separable Hilbert space of quantum noise in the channel.Each input mixed state12VIACHESLA V P BELA VKIN AND MASANORI OHYA̺0on A ◦⊆L (H 0)is transmitted into an output state ̺=̺0Λgiven by the density operator Λ∗(ρ0)=Y ρ0⊗I + Y †∈A ∗for each density operator ρ0∈A ◦∗,where I+is the identity operator in F +.With-out loss of generality we can assume that the input algebra A ◦is the smallest decomposable algebra,generated by the range Λ(A )of the given map Λ.The input entanglements κ:B →A ◦∗described as normal CP maps with κ(I )=̺0,define the quantum correspondences (q-encodings)of probe systems (B ,ς),ς=κ∗(I ),to (A ◦,̺0).As it was proven in the previous section,the most informative is the standard entanglement κ=π◦∗,at least in the case of the trivial channel Λ=I.This extreme input q-entanglement π◦(A ◦)=ρ1/20A ◦ρ1/20=π◦∗(A ◦),A ◦∈A ◦,corresponding to the choice (B ,ς)=(A ◦,̺0),defines the following density operator ω=(I ⊗Λ)∗ ω◦q ,ω◦q =ϑ0ϑ†0(28)of the input-output compound state ̟◦q Λon A ◦⊗A .It is given by the amplitudeϑ0∈H ⊗20defined as ˜ϑ0=ρ1/20.The other extreme cases of the self-dual input entanglements,the pure c-entanglements corresponding to (20),can be less infor-mative then the d-entanglements,given by the decompositions ρ0= ρ0(n )into pure states ρ0(n )=ηn η†n µ(n ).They define the density operators ω=(I ⊗Λ)∗(ω◦d ),ω◦d = n η◦n η◦†n ⊗ηn η†n µ0(n ),(29)of the A ◦⊗A -compound state ̟◦d Λ,which are known as the Ohya compound states ̟◦o Λ[1]in the caseρ0(n )=η◦n η◦†n λ0(n ),η◦†m η◦n =δm n ,of orthogonality of the density operators ρ0(n )normalized to the eigen-values λ0(n )of ρ0.They are described by the input-output density operators ω=(I ⊗Λ)∗(ω◦o ),ω◦o = nη◦n η◦†n ⊗η◦n η◦†n λ0(n ),(30)coinciding with (28)in the case of Abelian A ◦.These input-output compound states ̟are achieved by compositions λ=π◦Λ,describing the entanglements λ∗of the extreme probe system (B ◦,ς0)=(A ◦,̺0)to the output (A ,̺)of the channel.If K :B →B ◦is a normal completely positive unital mapK (B )=tr F −X †BX,B ∈B ,where X is a bounded operator F −⊗G 0→G with tr F −X †X =I ◦,the compositions κ=π◦∗K,π∗=Λ∗κare the entanglements of the probe system (B ,ς)to the channel input (A ◦,̺0)and to the output (A ,̺)via this channel.The state ς=ς0K is given by K ∗(σ0)=X I −⊗σ0 X †∈B ∗for each density operator σ0∈B ◦∗,where I −is the identity operator in F −.Theresulting entanglement π∗=λ∗K defines the compound state ̟=̟0(K ⊗Λ)on B ⊗A with̟0(B ◦⊗A ◦)=tr ˜B ◦π◦(A ◦)=tr υ†0(B ◦⊗A ◦)υ0.。

July 24,200813:6WSPC/244-AADA 00004Advances in Adaptive Data Analysis 1Vol.1,No.1(2008)1–41c World Scientific Publishing Company 3ENSEMBLE EMPIRICAL MODE DECOMPOSITION:A NOISE ASSISTED DATA ANALYSIS METHOD 5ZHAOHUA WU ∗and NORDEN E.HUANG †∗Center for Ocean–Land–Atmosphere Studies 74041Powder Mill Road,Suite 302Calverton,MD 20705,USA 9†Research Center for Adaptive Data Analysis National Central University 11300Jhongda Road,Chungli,Taiwan 32001A new Ensemble Empirical Mode Decomposition (EEMD)is presented.This new 13approach consists of sifting an ensemble of white noise-added signal and treats the mean as the final true result.Finite,not infinitesimal,amplitude white noise is necessary to 15force the ensemble to exhaust all possible solutions in the sifting process,thus mak-ing the different scale signals to collate in the proper intrinsic mode functions (IMF)17dictated by the dyadic filter banks.As the EMD is a time–space analysis method,the white noise is averaged out with sufficient number of trials;the only persistent part 19that survives the averaging process is the signal,which is then treated as the true and more physical meaningful answer.The effect of the added white noise is to provide a 21uniform reference frame in the time–frequency space;therefore,the added noise collates the portion of the signal of comparable scale in one IMF.With this ensemble mean,one 23can separate scales naturally without any a priori subjective criterion selection as in the intermittence test for the original EMD algorithm.This new approach utilizes the 25full advantage of the statistical characteristics of white noise to perturb the signal in its true solution neighborhood,and to cancel itself out after serving its purpose;therefore,it 27represents a substantial improvement over the original EMD and is a truly noise-assisted data analysis (NADA)method.29Keywords :1.Introduction 31Empirical Mode Decomposition (EMD)has been proposed recently 1,2as an adap-tive time–frequency data analysis method.It has proven to be quite versatile in 33a broad range of applications for extracting signals from data generated in noisy nonlinear and nonstationary processes (see,for example,Refs.3and 4).As useful 35as EMD proved to be,it still leaves some annoying difficulties unresolved.One of the major drawbacks of the original EMD is the frequent appearance 37of mode mixing,which is defined as a single Intrinsic Mode Function (IMF)either consisting of signals of widely disparate scales,or a signal of a similar scale residing39in different IMF components.Mode mixing is a consequence of signal intermittency.1July24,200813:6WSPC/244-AADA000042Z.Wu&N.E.HuangAs discussed by Huang et al.,1,2the intermittence could not only cause serious 1aliasing in the time–frequency distribution,but also make the physical meaningof individual IMF unclear.To alleviate this drawback,Huang et al.2proposed the 3intermittence test,which can indeed ameliorate some of the difficulties.However,the approach itself has its own problems:First,the intermittence test is based on 5a subjectively selected scale.With this subjective intervention,the EMD ceases tobe totally adaptive.Secondly,the subjective selection of scales works if there are 7clearly separable and definable timescales in the data.In case the scales are notclearly separable but mixed over a range continuously,as in the case of the majority 9of natural or man-made signals,the intermittence test algorithm with subjectivelydefined timescales often does not work very well.11To overcome the scale separation problem without introducing a subjective intermittence test,a new noise-assisted data analysis(NADA)method is proposed, 13the Ensemble EMD(EEMD),which defines the true IMF components as the meanof an ensemble of trials,each consisting of the signal plus a white noise offinite 15amplitude.With this ensemble approach,we can clearly separate the scale nat-urally without any a priori subjective criterion selection.This new approach is 17based on the insight gleaned from recent studies of the statistical properties ofwhite noise,5,6which showed that the EMD is effectively an adaptive dyadicfilter 19bank a when applied to white noise.More critically,the new approach is inspired bythe noise-added analyses initiated by Flandrin et al.7and Gledhill.8Their results 21demonstrated that noise could help data analysis in the EMD.The principle of the EEMD is simple:the added white noise would populate 23the whole time–frequency space uniformly with the constituting components ofdifferent scales.When signal is added to this uniformly distributed white back-25ground,the bits of signal of different scales are automatically projected onto properscales of reference established by the white noise in the background.Of course, 27each individual trial may produce very noisy results,for each of the noise-addeddecompositions consists of the signal and the added white noise.Since the noise in 29each trial is different in separate trials,it is canceled out in the ensemble mean ofenough trials.The ensemble mean is treated as the true answer,for,in the end, 31the only persistent part is the signal as more and more trials are added in theensemble.33The critical concept advanced here is based on the following observations:1.A collection of white noise cancels each other out in a time-space ensemble mean;35therefore,only the signal can survive and persist in thefinal noise-added signalensemble mean.37a A dyadicfilter bank is a collection of band-passfilters that have a constant band-pass shape(e.g.a Gaussian distribution)but with neighboringfilters covering half or double of the frequencyrange of any singlefilter in the bank.The frequency ranges of thefilters can be overlapped.Forexample,a simple dyadicfilter bank can includefilters covering frequency windows such as50to120Hz,100to240Hz,200to480Hz,etc.July24,200813:6WSPC/244-AADA00004Ensemble Empirical Mode Decomposition32.Finite,not infinitesimal,amplitude white noise is necessary to force the ensemble1to exhaust all possible solutions;thefinite magnitude noise makes the differentscale signals reside in the corresponding IMF,dictated by the dyadicfilter banks, 3and render the resulting ensemble mean more meaningful.3.The true and physically meaningful answer to the EMD is not the one without5noise;it is designated to be the ensemble mean of a large number of trialsconsisting of the noise-added signal.7This EEMD proposed here has utilized all these important statistical character-istics of noise.We will show that the EEMD utilizes the scale separation principle 9of the EMD,and enables the EMD method to be a truly dyadicfilter bank forany data.By addingfinite noise,the EEMD eliminates mode mixing in all cases 11automatically.Therefore,the EEMD represents a major improvement of the EMDmethod.13In the following sections,a systematic exploration of the relation between noise and signal in data will be presented.Studies of Flandrin et al.5and Wu and Huang6 15have revealed that the EMD serves as a dyadicfilter for various types of noise.Thisimplies that a signal of a similar scale in a noisy data set could possibly be contained 17in one IMF component.It will be shown that adding noise withfinite rather thaninfinitesimal amplitude to data indeed creates such a noisy data set;therefore, 19the added noise,havingfilled all the scale space uniformly,can help to eliminatethe annoying mode mixing problemfirst noticed by Huang et al.2Based on these 21results,we will propose formally the concepts of NADA and noise-assisted signalextraction(NASE),and will develop a method called the EEMD,which is based 23on the original EMD method,to make NADA and NASE possible.The paper is arranged as follows.Section2will summarize previous attempts of 25using noise as a tool in data analysis.Section3will introduce the EEMD method,illustrate more details of the drawbacks associated with mode mixing,present con-27cepts of NADA and of NASE,and introduce the EEMD in detail.Section4willdisplay the usefulness and capability of the EEMD through examples.Section5 29will further discuss the related issues to the EEMD,its drawbacks,and their corre-sponding solutions.A summary and discussion will be presented in thefinal section 31of the main text.Two appendices will discuss some related issues of EMD algorithmand a Matlab EMD/EEMD software for research community to use.332.A Brief Survey of Noise Assisted Data AnalysisThe word“noise”can be traced etymologically back to its Latin root of“nausea,”35meaning“seasickness.”Only in Middle English and Old French does it start to gainthe meaning of“noisy strife and quarrel,”indicating something not at all desirable.37Today,the definition of noise varies in different circumstances.In science and engi-neering,noise is defined as disturbance,especially a random and persistent kind 39that obscures or reduces the clarity of a signal.In natural phenomena,noise couldJuly24,200813:6WSPC/244-AADA000044Z.Wu&N.E.Huangbe induced by the process itself,such as local and intermittent instabilities,irresolv-1able subgrid phenomena,or some concurrent processes in the environment in whichthe investigations are conducted.It could also be generated by the sensors and 3recording systems when observations are made.When efforts are made to under-stand data,important differences must be considered between the clean signals that 5are the direct results of the underlying fundamental physical processes of our inter-est(“the truth”)and the noise induced by various other processes that somehow 7must be removed.In general,all data are amalgamations of signal and noise,i.e.x(t)=s(t)+n(t),(1) 9in which x(t)is the recorded data,and s(t)and n(t)are the true signal andnoise,respectively.Because noise is ubiquitous and represents a highly undesirable 11and dreaded part of any data,many data analysis methods were designed specifi-cally to remove the noise and extract the true signals in data,although often not 13successful.Since separating the signal and the noise in data is necessary,three important 15issues should be addressed:(1)The dependence of the results on the analysis meth-ods used and assumptions made on the data.(For example,a linear regression of 17data implicitly assumes the underlying physics of the data to be linear,while aspectrum analysis of data implies the process is stationary.)(2)The noise level to 19be tolerated in the extracted“signals,”for no analysis method is perfect,and inalmost all cases the extracted“signals”still contain some noise.(3)The portion 21of real signal obliterated or deformed through the analysis processing as part ofthe noise.(For example,Fourierfiltering can remove harmonics through low-pass 23filtering and thus deform the waveform of the fundamentals.)All these problems cause misinterpretation of data,and the latter two issues are 25specifically related to the existence and removal of noise.As noise is ubiquitous,steps must be taken to insure that any meaningful result from the analysis should 27not be contaminated by noise.To avoid possible illusion,the null hypothesis testagainst noise is often used with the known noise characteristics associated with the 29analysis method.6,9,7Although most data analysis techniques are designed specifi-cally to remove noise,there are,however,cases when noise is added in order to help 31data analysis,to assist the detection of weak signals,and to delineate the under-lying processes.The intention here is to provide a brief survey of the beneficial 33utilization of noise in data analysis.The earliest known utilization of noise in aiding data analysis was due to Press 35and Tukey10known as pre-whitening,where white noise was added toflatten thenarrow spectral peaks in order to get a better spectral estimation.Since then, 37pre-whitening has become a very common technique in data analysis.For exam-ple,Fuenzalida and Rosenbluth11added noise to process climate data;Link and 39Buckley,12and Zala et al.13used noise to improve acoustic signal;Strickland andIl Hahn14used wavelet and added noise to detect objects in general;and Trucco15 41used noise to help design specialfilters for detecting embedded objects on the oceanJuly24,200813:6WSPC/244-AADA00004Ensemble Empirical Mode Decomposition5floor experimentally.Some general problems associated with this approach can be 1found in the works by Priestley,16Kao et al.,17Politis,18and Douglas et al.19 Another category of popular use of noise in data analysis is more related to the 3analysis method than to help extracting the signal from the data.Adding noiseto data helps to understand the sensitivity of an analysis method to noise and 5the robustness of the results obtained.This approach is used widely;for example,Cichocki and Amari20added noise to various data to test the robustness of the 7independent component analysis(ICA)algorithm,and De Lathauwer et al.21usednoise to identify error in ICA.9Adding noise to the input to specifically designed nonlinear detectors could also be beneficial to detecting weak periodic or quasi-periodic signals based on a physical 11process called stochastic resonance.The study of stochastic resonance was pioneeredby Benzi and his colleagues in the early1980s.The details of the development of 13the theory of stochastic resonance and its applications can be found in a lengthyreview paper by Gammaitoni et al.22It should be noted here that most of the 15past applications(including those mentioned earlier)have not used the cancellationeffects associated with an ensemble of noise-added cases to improve their results.17Specific to analysis using EMD,Huang et al.23added infinitesimal magnitude noise to earthquake data in an attempt to prevent the low frequency mode from 19expanding into the quiescent region.But they failed to realize fully the implicationsof the added noise in the EMD method.The true advances related to the EMD 21method had to wait until the two pioneering works by Gledhill8and Flandrin et al.7 Flandrin et al.7used added noise to overcome one of the difficulties of the 23original EMD method.As the EMD is solely based on the existence of extrema(either in amplitude or in curvature),the method ceases to work if the data lacks 25the necessary extrema.An extreme example is in the decomposition of a Diracpulse(delta function),where there is only one extrema in the whole data set.To 27overcome the difficulty,Flandrin et al.7suggested adding noise with infinitesimalamplitude to the Dirac pulse so as to make the EMD algorithm operable.Since 29the decomposition results are sensitive to the added noise,Flandrin et al.7ran anensemble of5000decompositions,with different versions of noise,all of infinitesimal 31amplitude.Though they used the mean as thefinal decomposition of the Diracpulse,they defined the true answer as33E{d[n]+εr k[n]},(2)d[n]=lime→0+in which,[n]represents n th data point,d[n]is the Dirac function,r k[n]is a random 35number,εis the infinitesimal parameter,and E{}is the expected value.Flandrin’snovel use of the added noise has made the EMD algorithm operable for a data set 37that could not be previously analyzed.Another novel use of noise in data analysis is by Gledhill,8who used noise to 39test the robustness of the EMD algorithm.Although an ensemble of noise was used,he never used the cancellation principle to define the ensemble mean as the true 41answer.Based on his discovery(that noise could cause the EMD to produce slightlyJuly24,200813:6WSPC/244-AADA000046Z.Wu&N.E.Huangdifferent outcomes),he assumed that the result from the clean data without noise 1was the true answer and thus designated it as the reference.He then defined thediscrepancy,∆,as3∆=mj=1t(cr j(t)−cn j(t))21/2,(3)where cr j and cn j are the j th component of the IMF without and with noise added, 5and m is the total number of IMFs generated from the data.In his extensive study of the detailed distribution of the noise-caused“discrepancy,”he concluded that 7the EMD algorithm is reasonably stable for small perturbations.This conclusion is in slight conflict with his observations that the perturbed answer with infinitesimal 9noise showed a bimodal distribution of the discrepancy.Gledhill had also pushed the noise-added analysis in another direction:He had 11proposed to use an ensemble mean of noise-added analysis to form a“Composite Hilbert spectrum.”As the spectrum is non-negative,the added noise could not 13cancel out.He then proposed to keep a noise-only spectrum and subtract it from the full noise-added spectrum at the end.This non-cancellation of noise in the 15spectrum,however,forced Gledhill8to limit the noise used to be of small magnitude, so that he could be sure that there would not be too much interaction between the 17noise-added and the original clean signal,and that the contribution of the noise to thefinal energy density in the spectrum would be negligible.19Although noise of infinitesimal amplitude used by Gledhill8has improved the confidence limit of thefinal spectrum,Gledhill explored neither fully the cancella-21tion property of the noise nor the power offinite perturbation to explore all possible solutions.Furthermore,it is well known that whenever there is intermittence,the 23signal without noise can produce IMFs with mode mixing.There is no justification to assume that the result without added noise is the truth or the reference sig-25nal.These reservations notwithstanding,all these studies by Flandrin et al.7and Gledhill8had still greatly advanced the understanding of the effects of noise in the 27EMD method,though the crucial effects of noise had yet to be clearly articulated and fully explored.29In the following,the new noise-added EMD approach will be explained,in which the cancellation principle will be fully utilized,even withfinite amplitude noise.Also 31emphasized is thefinding that the true solution of the EMD method should be the ensemble mean rather than the clean data.This full presentation of the new method 33will be the subject of the next section.3.Ensemble Empirical Mode Decomposition353.1.The empirical mode decompositionThis section starts with a brief review of the original EMD method.The detailed 37method can be found in the works of Huang et al.1and Huang et al.2Different to almost all previous methods of data analysis,the EMD method is adaptive,with 39July24,200813:6WSPC/244-AADA00004Ensemble Empirical Mode Decomposition7 the basis of the decomposition based on and derived from the data.In the EMD 1approach,the data X(t)is decomposed in terms of IMFs,c j,i.e.x(t)=nj=1c j+r n,(4)3where r n is the residue of data x(t),after n number of IMFs are extracted.IMFs are simple oscillatory functions with varying amplitude and frequency,and hence 5have the following properties:1.Throughout the whole length of a single IMF,the number of extrema and the 7number of zero-crossings must either be equal or differ at most by one(althoughthese numbers could differ significantly for the original data set);92.At any data location,the mean value of the envelope defined by the local maximaand the envelope defined by the local minima is zero.11In practice,the EMD is implemented through a sifting process that uses only local extrema.From any data r j−1,say,the procedure is as follows:(1)identify all 13the local extrema(the combination of both maxima and minima)and connect all these local maxima(minima)with a cubic spline as the upper(lower)envelope; 15(2)obtain thefirst component h by taking the difference between the data and thelocal mean of the two envelopes;and(3)Treat h as the data and repeat steps1and 172as many times as is required until the envelopes are symmetric with respect to zero mean under certain criteria.Thefinal h is designated as c j.A complete sifting 19process stops when the residue,r n,becomes a monotonic function from which no more IMFs can be extracted.21Based on this simple description of EMD,Flandrin et al.5and Wu and Huang6 have shown that,if the data consisted of white noise which has scales populated 23uniformly through the whole timescale or time–frequency space,the EMD behaves as a dyadicfilter bank:the Fourier spectra of various IMFs collapse to a single 25shape along the axis of logarithm of period or frequency.Then the total number of IMFs of a data set is close to log2N with N the number of total data points. 27When the data is not pure noise,some scales could be missing;therefore,the total number of the IMFs might be fewer than log2N.Additionally,the intermittency 29of signals in certain scale would also cause mode mixing.3.2.Mode mixing problem31“Mode mixing”is defined as any IMF consisting of oscillations of dramatically dis-parate scales,mostly caused by intermittency of the driving mechanisms.When 33mode mixing occurs,an IMF can cease to have physical meaning by itself,suggest-ing falsely that there may be different physical processes represented in a mode. 35Even though thefinal time–frequency projection could rectify the mixed mode to some degree,the alias at each transition from one scale to another would irrecov-37erably damage the clean separation of scales.Such a drawback wasfirst illustratedJuly24,200813:6WSPC/244-AADA000048Z.Wu&N.E.Huangby Huang et al.2in which the modeled data was a mixture of intermittent high-1frequency oscillations riding on a continuous low-frequency sinusoidal signal.Analmost identical example used by Huang et al.2is presented here in detail as an 3illustration.The data and its sifting process are illustrated in Fig.1.The data has its funda-5mental part as a low-frequency sinusoidal wave with unit amplitude.At the threemiddle crests of the low-frequency wave,high-frequency intermittent oscillations 7with an amplitude of0.1are riding on the fundamental,as panel(a)of Fig.1shows.The sifting process starts with identifying the maxima(minima)in the 9data.In this case,15local maxima are identified,with thefirst and the last comingfrom the fundamental,and the other13caused mainly by intermittent oscillations 11(panel(b)).As a result,the upper envelope resembles neither the upper envelope ofthe fundamental(which is aflat line at one)nor the upper one of the intermittent 13oscillations(which is supposed to be the fundamental outside intermittent areas).Rather,the envelope is a mixture of the envelopes of the fundamental and of the 15(a)(b)(c)(d)Fig.1.The veryfirst step of the sifting process.Panel(a)is the input;panel(b)identifies localmaxima(gray dots);panel(c)plots the upper envelope(upper gray dashed line)and low envelope(lower gray dashed line)and their mean(bold gray line);and panel(d)is the difference betweenthe input and the mean of the envelopes.July24,200813:6WSPC/244-AADA00004Ensemble Empirical Mode Decomposition9Fig.2.The intrinsic mode functions of the input displayed in Fig.1(a).intermittent signals that lead to a severely distorted envelope mean(the thick grey 1line in panel(c)).Consequently,the initial guess of thefirst IMF(panel(d))is themixture of both the low frequency fundamental and the high-frequency intermittent 3waves,as shown in Fig.2.An annoying implication of such scale mixing is related to unstableness and lack 5of the uniqueness of decomposition using the EMD.With stoppage criterion givenand end-point approach prescribed in the EMD,the application of the EMD to 7any real data results in a unique set of IMFs,just as when the data is processedby other data decomposition methods.This uniqueness is here referred to as“the 9mathematical uniqueness,”and satisfaction to the mathematical uniqueness is theminimal requirement for any decomposition method.The issue that is emphasized 11here is what we refer to as“the physical uniqueness.”Since real data almost alwayscontains a certain amount of random noise or intermittences that are not known 13to us,an important issue,therefore,is whether the decomposition is sensitive tonoise.If the decomposition is insensitive to added noise of small butfinite ampli-15tude and bears little quantitative and no qualitative change,the decomposition isgenerally considered stable and satisfies the physical uniqueness;and otherwise, 17the decomposition is unstable and does not satisfy the physical uniqueness.Theresult from decomposition that does not satisfy the physical uniqueness may not be 19reliable and may not be suitable for physical interpretation.For many traditionaldata decomposition methods with prescribed base functions,the uniqueness of the 21July24,200813:6WSPC/244-AADA0000410Z.Wu&N.E.Huangsecond kind is automatically satisfied.Unfortunately,the EMD in general does not 1satisfy this requirement due to the fact that decomposition is solely based on thedistribution of extrema.3To alleviate this drawback,Huang et al.2proposed an intermittence test that subjectively extracts the oscillations with periods significantly smaller than a pre-5selected value during the sifting process.The method works quite well for thisexample.However,for complicated data with scales variable and continuously dis-7tributed,no single criterion of intermittence test can be selected.Furthermore,themost troublesome aspect of this subjectively pre-selected criterion is that it lacks 9physical justifications and renders the EMD nonadaptive.Additionally,mode mix-ing is also the main reason that renders the EMD algorithm unstable:Any small 11perturbation may result in a new set of IMFs as reported by Gledhill.8Obviously,the intermittence prevents EMD from extracting any signal with similar scales.13To solve these problems,the EEMD is proposed,which will be described in thefollowing sections.153.3.Ensemble empirical mode decompositionAs given in Eq.(1),all data are amalgamations of signal and noise.To improve the 17accuracy of measurements,the ensemble mean is a powerful approach,where dataare collected by separate observations,each of which contains different noise.To 19generalize this ensemble idea,noise is introduced to the single data set,x(t),as ifseparate observations were indeed being made as an analog to a physical experiment 21that could be repeated many times.The added white noise is treated as the possiblerandom noise that would be encountered in the measurement process.Under such 23conditions,the i th“artificial”observation will bex i(t)=x(t)+w i(t).(5) 25In the case of only one observation,one of the multiple-observation ensembles is mimicked by adding not arbitrary but different copies of white noise,w i(t),to 27that single observation as given in Eq.(5).Although adding noise may result insmaller signal-to-noise ratio,the added white noise will provide a uniform reference 29scale distribution to facilitate EMD;therefore,the low signal–noise ratio does notaffect the decomposition method but actually enhances it to avoid the mode mixing.31Based on this argument,an additional step is taken by arguing that adding whitenoise may help to extract the true signals in the data,a method that is termed 33EEMD,a truly NADA method.Before looking at the details of the new EEMD,a review of a few properties of 35the original EMD is presented:(1)the EMD is an adaptive data analysis method that is based on local charac-37teristics of the data,and hence,it catches nonlinear,nonstationary oscillationsmore effectively;39。

Haverford College Mathematics Undergraduate Senior ThesisMinkowski Sum Decompositions of Convex PolygonsRobert SeaterHaverford CollegeHaverford,PA19041rseater@May1,2002AbstractMinkowski sums provide a certain way of adding polytopes together and producing a new polytope. In this paper,we give an introduction to convex polytopes and address the question of decomposing polygons and polytopes into Minkowski summands.That is,given a polytope,how can we write it as a Minkowski sum of other polytopes?We prove a theorem that allows us to use edge sets of polygons to calculate their Minkowski sum. Using this theorem,we show some other nice facts and provide an algorithm forfinding Minkowski decompositions.We examine the set of all such decompositions of a given polygon,and show that it is itself a convex polytope.Provided with this paper is a Mathematica notebook that allows the user to examine and experiment with Minkowski sums.It is a nice way to get an intuition for the background and theorems in this paper, as well as supplying empirical evidence for the conjectures introduced towards the end of the paper. Keywords:Minkowski Vector Sum Summand,Decomposition Polytope,Decomposable Indecomposable Reducible Irreducible,Convex Polygon Polytope Hull Combination,RMS DePo,Sliced Edge Set Edgeset Edge-Set,Stamping Algorithm,Mathematica Notebook Program Package Algorithm,Weight-Vector Edge-Vector Edge-Summand Weight MatrixContents1Introduction3 2Background in Convex Polytopes32.1Convex Polytopes (3)2.2Minkowski Sums (6)2.3The Stamping Algorithm (8)2.4Scaled Multiples of Polytopes (12)2.5Decompositions of Polytopes (13)2.6Hyperplanes,Supporting Hyperplanes,and Faces (13)2.7Edge Sets (15)3Minkowski Sums of Faces163.1Faces of Sums (18)4Relating Minkowski Summation to Edge Sets194.1Edge Sets of Equivalent Polygons (19)4.2Edge Sets and Decompositions (20)5Decomposition Algorithm215.1Description of the Algorithm (22)5.2Correctness of the Algorithm (23)6Indecomposability30 7Symmetries31 8Finiteness and Decomposition348.1Infinite Aspects (34)8.2Some Notation for Decompositions and Summands (35)8.3The Decomposition Polytope (37)8.4The Set of All Summands (38)8.5Summary and Connections (40)9Conclusion and Future Work40 10An Introduction to Time Complexity43 11The Mathematica Notebook:Usage Guide and Analysis4311.1Functions and Syntax (44)11.2Type Conversion Functions (44)11.3Internal Workings of RMS(Recursive Minkowski Sum) (45)11.4Complexity Analysis of RMS (47)11.5Alternate Methods for Computing Minkowski Sums (47)11.6The DePo Function(Decomposition Polytope) (48)12Bounds on Lattice Volume4812.1Background (48)12.2Lattice Polygons (48)12.3General Polygons (51)13Acknowledgments521IntroductionWhenever there is a means of combining mathematical objects,there arises the questions of reversing the process.That is,given the result,could we have found the objects were combined to produce it?Is the decomposition unique?If not,what can we say about the set of all decompositions of a given object?Minkowski summation provides a very salient means of combining a set of polytopes and producing a new polytope.One would like to be able to take any given a polytope andfind all ways to express it as the Minkowski sum of other polytope.This process is particularly intriguing,since it turns out that the set of all such decompositions of a polygon is itself a polytope.We hope to provide the reader with the background necessary to understand and work with this“decomposition polytope”and appreciate its intricacies.The problem of decomposing polytopes wasfirst addressed by Gale in1954in[Gal54].He stated, without proof,some basic properties of what he called“irreducible polytopes”.Grunbaum later formalized the language and basic results in his definitive treatment of convex sets in[Gru67].Meyer proved more advanced results about Minkowski sums in[Mey74]and provided a more precise understanding of when one polytope is in the decomposition of another.In this paper,we focus our attention on the set of all decompositions of a given polytope.Section1introduces the paper and gives a high level summary of the content.Section2gives a thorough introduction to convex polytopes,including basic terminology and fundamental theorems of thefield.Sec-tion3introduces a theorem describing the relation between faces of a polytope and faces of its Minkowski summands.Section4introduces a very useful theorem for manipulating polygons,which gives a direct relation between the edge sets of a polygon and the edge sets of its Minkowski summands.Section5uses the tools introduced in previous section to prove an algorithm forfinding a Minkowski decomposition of any polygon.Section6identified the indecomposable polygons.Section7correlates symmetries within a set of polygons to symmetries of their Minkowski sum.Section8discusses and identified thefinite aspects of Minkowski sum decompositions of polygons.Section9concludes the paper and discusses directions of future work.Section12is a supplemental section with related,but not directly relevant,results.We gives tight bounds for the number of lattice points in a polytope as a function of the lattice points of its summands.Another important part of this paper is the accompanying Mathematica notebook.This set of tools allows users to examine and experiment with Minkowski sums in order and get a better intuition for how they behave.It allows the user to efficiently perform Minkowski sums,as well as generating the decomposition polytope of any polygon.It is a nice way to get an intuition for the background and theorems in this paper, and generate additional examples where needed.Section10introduces some background in time complexity, and Section11describes the use of this tool,as well as proving its correctness and efficiency.2Background in Convex PolytopesThis section provides an overview of and introduction to convex polytopes,Minkowski sums,and related terminology and lemmas.Subsection2.1introduces the formal definition of a convex poplytope and proves some fundamental properties such as their convexity.Subsection2.2introduces the notion of a Minkowski sum,and provides some simple examples.Subsection2.3contains an algorithm for generating Minkowski sums without using the formal theorem.That algorithm is crucial to getting an intuition for Minkowski sums,since it allows us to quickly and accurately produce examples.Subsection2.5introduces the notion of decomposing a polytope into Minkowski summands.Subsection2.6gives us a thorough understanding of what a face is,in terms of supporting hyperplanes.Subsection2.7presents the idea of the edge set of a polygon,which will be linked to Minkowski summation later on in Section4.2.1Convex PolytopesHere we describe and define the notion of a convex polytope using the convex hull definition.There are other,equivalent,definitions of polytopes but we will not have need for them.() =() =Conv ConvFigure 1:Here are two simple examples of taking the convex hull of a set ofpoint.Conv () =Figure 2:A less trivial example of a convex hull of points in R 2.Definition 2.1The convex hull of a set of vectors V ={v 1,...,v k }in R n is given by conv (V )={x ∈R n |∃λ1,...,λk ∈R ≥0for which x =ki =1λi v i and k i =1λi =1}where R ≥0denotes the non-negative real numbers.Each element of conv (V )is called a convex combination of V .[Ewa96,Gru67]That is,the convex hull of V is the set of all convex combinations of V .Illustrations of some sample convex hulls can be found in Figures 1and 2.Definition 2.2P is a convex polytope if and only if there exist vectors V =v 1,...,v k such that P =conv (V ).[Ewa96]Example 2.1To get some intuition for what convex hulls look like,consider the case where k =2.That is,we are taking the convex hull of just two points in R n .conv ({v 1,v 2})={x ∈R n |∃λ1,λ2∈R ≥0for which x =λ1v 1+λ2v 2and λ1+λ2=1}which is equivalent to sayingconv ({v 1,v 2})={x ∈R n |x =λv 1+(1−λ)v 2forλin R with 0≤λ≤1}which is simply the parametric definition of a line segment with endpoints at v 1and v 2.That is,the convex hull of two points is just a line segment with those endpoints.Definition 2.3A polygon is a polytope in R 2.That is,a polygon is the convex hull of a finite number of points in R 2.Remark:A polygon has the same number of edges as vertices,as long as it is not just a singe point.This can be proven by by induction on the number of vertices,but is unenlightening and not necessary to thisExample2.2Triangles,quadrilaterals,and line segments are all polygons.Figures1and2show some polygons presented as convex hulls.We will now prove a lemma which is implied by the choice of terminology;convex hulls are convex. This result follows rather easily from the definitions of convexity and convex hull,but takes quite of bit of writing to work out rigorously.Careful proofs of fundamental properties of polytopes are vital to a solid understanding of later results.Definition2.4A set S⊂R n is convex if and only only if for any two points x,y∈S,the line segment xy is contained in S.[Str89]Lemma2.1The convex hull of a set of points is convex.Proof:Let x and y be points in a the set P⊂R n,such thatP=conv(v1,v2,...,v k)x=a1v1+a2v2+...+a k v ky=b1v1+b2v2+...+b k v ksuch thata i,b i∈R≥0,for1≤i≤kka i=1a=1kb i=1b=1Now consider the line segment l which connects x and y.l=conv(x,y)Any point z on l can be described by the equationz=λx+(1−λ)yfor0≤λ≤1.We can rewrite that equation by substituting in our previous definitions of x and y.z=λ(a1v1+a2v2+...+a k v k)+(1−λ)(b1v1+b2v2+...+b k v k)Examining the coefficients,wefind thatλa1+λa2+...+λa k+(1−λ)b1+(1−λ)b2+...+(1−λ)b k=λ(a1+a2+...+a k)+(1−λ)(b1+b2+...+b k)=λ(1)+(1−λ)(1)=1which means that z is in the convex hull of v1,...,v k,which is just P.Since z∈P for any z on l,l⊂P and P is convex.Remark:Under our definitions,all polytopes are convex polytopes.We will often repeat the fact that our polytopes are convex for the sake of clarity,but in this paper all polytopes and polygons are convex unless explicity stated otherwise.Remark:As we observed earlier,the convex hull of a pair of points is a line segment.For our purposes,we will think of line segments as degenerate rectangles.That is,they are rectangles with zero width but which still have2edges.This representation is shown in Figure3,and will become important in Section2.7whenA line segment seen as a degenerate rectangle.A line segment seen as theconvex hull of two points.width zeroFigure 3:A line segment can be seen as a degenerate rectangle.2.2Minkowski SumsNow we will describe a means by which we can “add”together two polytopes.That is,how we can take two polytopes and produce a third that behaves in a way that we would intuitively expect a sum to behave (commutativity,associativity,etc.).This notion of being able to add together subsets of R n builds the foundation upon which the rest of the paper is based.Definition 2.5For any two sets P,Q ⊂R n ,the Minkowski Sum of P and Q is defined to beP +Q ={p +q |p ∈P,q ∈Q }[Gru67]Minkowski summation is sometimes called vector summation in older texts.Lemma 2.2For any two subsets of R n ,V ={v 1,...,v k }and U ={u 1,...,u m },conv (V )+conv (U )=conv (U +V )That is,Proof:Let P,Q ⊂R n be polytopes defined by P =conv (V )and Q =conv (U )for some sets V ={v 1,...,v k }and U ={u 1,...,u m }.We can write the sum asP +Q ={p +q |p ∈P,q ∈Q }For some scalar coefficients a 1,...,a k ∈R and b 1,...,b k ∈R ,we then haveconv (V )+conv (U )={a +b |a ∈convV,b ∈conv (U )}={(a 1v 1+...+a k v k )+(b 1u 1+...+b k u m )}={(a 1v 1+...+a k v k +b 1u 1+...+b k u m )}={ k i =1 m j =1(a i m +b j k )(v i +u j )}={x |x ∈conv ({(v i +u j )for 0≤i ≤k and 0≤j ≤m })}={x |x ∈conv (V +U )}And so we see that the set of all convex polytopes is closed under Minkowski summation.That is,theExample2.3If Q is any polytope and P is a single point polytope,then P+Q is a just a translation of Q by the vector P.Performing the Minkowski sum in this case means adding the only point in P to each element of Q,hence shifting each point in Q by the vector equivalent of P.The shape of Q remains the same.Remark:In this thesis,we work with the shape of the polytopes,not their position in space.Since any translation can be written as a Minkowski sum with a single point polytope,we will ignore translations of polytopes unless otherwise stated.When we refer to a polygon P,we are really referring to an arbitrary translation of P.Example2.4Let P be any polytope,and let Q be a line segment.To visualize the Minkowski sum P+Q, recall that adding P to any one of the points in Q is just a translation of P.Thus adding P to each of the points in Q will place multiple(overlapping)translated copies of P.Lemma2.3For any two convex polytopes P and Q,P+Q=(P+q)q∈QThis lemma is nothing more than a rephrasing of the previous definition of the Minkowski sum,but it will be useful to have in mind in Section2.3when we prove the Stamping Algorithm(Algorithm2.1).We will now prove some other nice facts about Minkowski sums,and show that theyfit our intuition for how addition“should”behave.Lemma2.4Minkowski summation is associative.That is,for any polytopes P,Q,and R,we have(P+Q)+R=P+(Q+R)Proof:This lemma follows directly(and almost trivially)from Definition2.5and the associativity of“+”over R.(P+Q)+R=P+{q+r|q∈Q,r∈R}={p+(q+r)|p∈P,q∈Q,r∈R}={(p+q)+r|p∈P,q∈Q,r∈R}={p+q|p∈P,q∈Q}+R=P+(Q+R)Lemma2.5Minkowski summation is commutative.That is,for any polytopes P,Q,and R,we haveP+Q=Q+PProof:This lemma follows easily from Definition2.5and the commutativity of“+”over R.P+Q={p+q|p∈P,q∈Q}={q+p|p∈P,q∈Q}=Q+PIntuitively,both associativity and commutativity are inherited from addition over the reals.Remark:It is impossible for any paper to discuss Minkowski sums without at least touching upon the study of zonotopes.More stamps A few stamps Final Shape P+Q The outlinegets filled in.Initial polygonsTemplateStamp P QHandleFigure 4:A demonstration of the stamping algorithm.Definition 2.6A zonotope is a Minkowski sum of line segments.Example 2.5A line segment is a trivial zonotope.A hexagon is a less trivial example,and can be seen in Figure 13.Zonotopes have many interesting properties and invariants,most of which are outside the scope of this paper.However interested readers will find discussions of Zonotopes in almost any text on convex polytopes.Some good starting points are the relevant sections of [Ewa96],[Zie95],[McM71],and [She74].In the context of this paper,zonotopes will just be useful examples and not any different from other polytopes.2.3The Stamping AlgorithmHere we provide a geometric algorithm for calculating the Minkowski sum of two polytopes.This algorithm will be useful for quickly producing examples as well as providing an intuition for what is going on.It is a rigorous expansion of the algorithm briefly sketched by Ziegler in [Zie95].Algorithm 2.1Given two convex polytopes P,Q ,we can calculate the Minkowski sum P +S as follows:(1)Choose one of the polygons to be the template .Without loss of generality,choose P .(2)The other polytope,Q ,will be the stamp .(3)Choose a point to be the handle of the stamp .Note that this handle does not have to be on the stamp .(4)Pick up the stamp by the handle ,and place a copy of the stamp down for every possible placement ofthe handle within the template .If we choose the handle to be the origin,then the resulting set of points will be the exact Minkowski sum P +Q .If we choose any other point as a handle,then we will still get the same shaped result,but will differ by a translation.In this thesis,we are concerned with shape (not translation),so we usually pick a handle that is more convenient than the origin (such as a vertex of the stamp).Example 2.6A demonstration of the stamping algorithm is given in Figure 4.Figure 5demonstrates that reversing the choice of stamp and template does not change the result of the algorithm.Figures 6and 7show a similar demonstration that the handle choice is irrelevant.Remark:Since Minkowski summation is associative (Theorem 2.4),an algorithm which allows us to calcu-late a 2-part sum will also let us calculate a sum with any number of summands.Some examples will give intuition for the algorithm and for how Minkowski sums behave.Example 2.7Let P be an equilateral triangle and Q be a single point polygon.Their sum,P +Q ,is shown in Figure 8.This demonstrates how adding a single point to a polytope translates the polytope,but does not change its shape.Since we are only concerned with shapes of polytopes in this thesis,we consider single-point additionsA few stamps More stamps The outline gets filled in.Final Shape P+Q Different choicesP QTemplate StampHandleFigure 5:Choosing the stamp and template differently does not affect theoutcome.TemplateStamp P QA different handleHandleA few stamps More stamps The outline gets filled in.Final Shape P+Q Figure 6:Choosing a different handle does not affect theoutcome.A few stamps More stamps The outline gets filled in.Final Shape P+Q P QHandleTemplateStamp A handle outside of the stamp.Figure 7:Choosing a handle outside of the stamp isacceptable.Q P P+Q=+Figure 8:Example of a Minkowski sum acting as a translation.+=P QP+QFigure9:Example of a Minkowski sum acting as ascaling.+=QPP+QFigure10:Example of a Minkowski sum.Example2.8Let P be an equilateral triangle,and Q be a copy of P.Their sum,P+Q,is shown in Figure9.This demonstrates how adding a polytope to itself produces a scaled version of that polytope.See Lemma2.7for a proof of this fact.Example2.9Let P be an equilateral triangle,and Q be the same triangle but put up-side-down.Their sum, P+Q,is the regular hexagon shown in Figure10.This example demonstrates that rotating the summands greatly influences the resulting polytope.We explore some similar results in Section7.Example2.10Let P be an equilateral triangle,and Q be a vertical line segment.Their sum,P+Q,is the “house”shape shown in Figure11.Example2.11Let P be a right triangle,and Q be the same triangle butflipped about the y-axis.Their sum,P+Q,is the“house”shape shown in Figure12.Notice that the Minkowski sums in Examples2.10and2.11are the same,even though the summands are different.This phenomena of different set of polytopes summing to the same polytope is themotivationQPP+Q=+Figure11:Example of a Minkowski sum.P+Q=+P Q Figure 12:Example of a way to get the same Minkowski sum as in Example 11but with differentsummands.=P + Q + R++Q P R Figure 13:A different set of polygons that sum to a hexagon.Since these summands are all line segments,we know that regular hexagons are zonotopes.for this paper.This non-uniqueness is such a vital result that we will show another example of it.We will see this idea again in Section 2.5.Example 2.12Let P ,Q ,and R be non-parallel line segments in R 2.Their sum,P +Q +R is a hexagon.Furthermore,when properly chosen,they are exactly the same hexagon as the one pictured in Figure 10,as can be seen in Figure 13.Now that we have gained some intuition for the stamping algorithm,we turn to a formal proof of its correctly.Theorem 2.1The stamping algorithm applied to two polytopes P and Q produces their sum,P +Q .Proof:Recall Lemma 2.3,which states thatP +Q =q ∈Q (P +q )The stamping algorithm exactly performs the union described in that Lemma.In this interpretation,P is the stamp and Q as the template.Assume we choose 0,the origin,to be the handle of P .This will get us that P +q equals the image of P when the handle is placed at q .Each term of the union,P +q ,corresponds to the act of creating an image of P with the handle of P placed at q .Performing the union on those terms corresponds to taking the union of all the images.Choosing an arbitrary handle,h ∈R n ,is equivalent to adding the point h to P +Q .Doing so is just a translation and thus can be ignored.Thus we can choose any handle we want,and the stamping algorithm will still generate a result with the same shape and size as the true Minkowski sum.Remark:Recall from Lemma 2.2that conv (U +V )=conv (U )+conv (V ).Thus,if we choose a vertex as a handle,we can just stamp the handle onto each vertex of the template and take the convex hull of the result.This method is reflected in the examples of this section,and its running time complexity is analyzed2.4Scaled Multiples of PolytopesIn this section we present the notion of a scaled polytope and verify some elementary notions about them. That is,we will specify what we really mean when we write something like“2P for a polytope P”.We verify that the notationally obvious statement“P+P=2P”really is true under our particular meaning of “+”and“2P”.Some readers may wish to simply accept that statement as true and move on to the more important sections of the paper.Definition2.7For any polytope P⊂R n,we can talk about scaled multiples of P,written kP,for any scalar k∈R.Quite simply,kP={kp|p∈P}[Gru67]Example2.13For k=0,the scaled polytope kP is a single point polytope(the origin, 0)independent of P.Lemma2.6Scaled multiples of polytopes are themselves polytopes,as the name suggests.Proof:Let P be a polytope.By definition,P=conv(V)for some set of vectors V={v1,...,v k}.Thus we can write2P as2P={x∈R n|x=2p,p=(a1v1+...+a k v k)∈conv(V)}={x∈R n|x=2(a1v1+...+a k v k)}={x∈R n|x=(a1v1+...+a k v k)+(a1v1+...+a k v k)}={x∈R n|x=p+p∈P+P}={x∈R n|x∈P+P}=P+Pfor some scalar coefficients a1,...,a k∈R.Remark:Once we have introduced scalar multiples of polytopes,we are obligated tofind out if they behave the way scalar multiples do in other domains.That is,is it true that P+P=2P,as is the case for R and R n?Notation:By“2P”,we mean the dilation of P by a factor of2.That is,2P={p∈R n|p2∈P}Lemma2.7If P⊂R n is a polytope,then P+P=2P.Proof:We will prove that2P=P+P by showing that both2P⊂P+P and P+P⊂2P hold.Consider a arbitrary point x∈P.By definitionx+x∈P+P2x∈P+Pand thus2P⊂P+P.Now consider a pointx+y∈P+Pfor x,y∈P.Let s be the line segments=conv(x,y)∈PP P P + P = 2P+=Figure 14:An illustration that P +P =2P .Since P is convex,s ⊂P and midpoint of s is contained in P .x +y 2∈P from which it follows that x +y2+x +y2∈P +P2x +x 2∈Px +y ∈P +Pand thus P +P ⊂2P .Example 2.14An illustration of Lemma 2.7can be found in Figure 14.Remark:Since Minkowski summation is associative (as we saw in Lemma 2.4),Lemma 2.7implies the more general result that k i =1P =kP .2.5Decompositions of PolytopesDefinition 2.8A decomposition of a convex polytope P is a a set of convex polytopes S ={s 1,...,s l }such that k i =1=P .The act of decomposing a polytope refers to finding all such sets which sum to P .Remark:The sums shown in Examples 11and 12and in Examples 10and 13demonstrate that Minkowski sum decompositions are not always unique.Definition 2.9A polytope P is indecomposable if and only if,for any decomposition P =Q +R ,the polytopes Q and R are always either scaled versions of P or single points.Remark:In Section 6,we prove that the indecomposable polygons are triangles,line segments,and single points.In Section 5we provide an algorithm for finding a decomposition of any polygon into triangles and line segments.2.6Hyperplanes,Supporting Hyperplanes,and FacesIn this subsection we present the formal definition of a hyperplane in R n and the closely related notion of a face of a polytope.They are all standard definitions and equivalent ones can be found in almost any textDefinition2.10A hyperplane in R n,H,is a subset of R n such thatH={x∈R n|<x,u>=α}for somefixed vector u∈R n and somefixed valueα∈R n.Here,u is the normal vector of H,αis the constant term of H,and<•,•>represents the standard dot product.[McM71]This is just a plane in R3or a line in R2,but generalized to R n.A hyperplane provides us with a natural way to divide up R n into two“halves”;one“above”H and the other“below”H.Definition2.11A hyperplane H in R n implicitly defines two half spaces of R n,called H+and H−.H+={x∈R n|<x,u>≥α}H−={x∈R n|<x,u>≤α}[McM71,Gru67]Notice that the inequalities are not strict.For this paper,we will define both half spaces to include H, since doing so will make later proofs and definitions cleaner.Remark:We can now observe two elementary facts about half spacesH+∩H−=HH+∪H−=R nDefinition2.12A hyperplane H is a said to be a supporting hyperplane of a polytope P in R n if and only if H∩P=∅and either P⊂H+or P⊂H−.[McM71]Without loss of generality,we will always assume that P lies in H+.We will refer to this simplification as the positive support assumption.Definition2.13For any convex polytope P,F⊂P is a face of P if and only if there is some supporting hyperplane of P for which F=P∩H.By convention,P and∅are improper faces of P.[Ewa96,Zie95]Intuitively,this notion of a face is simply a formal,generalized definition of what we normally think of as “faces”of polytopes in R2and R3.A polygon’s vertices and edges are faces.A polyhedra’s vertices,edges, and surfaces are all faces.The supporting hyperplane for any face is a hyperplane which has been pushed up against that face as far as it can go.Definition2.14The vertices of a polytope P are the zero dimensional faces of P.The edges of P are the one dimensional faces of P.Notation:The length of an edge E is denoted|E|.Example2.15Revisiting the running example of the“house polygon”,some sample supporting hyperplanes and their corresponding faces are shown in Figure15.Remark:For any hyperplane H and any polytope P,there exist unique hyperplanes I and J parallel to H such that I supports P with P⊂I+and J supports P with P⊂J−.That observation motivates the following definition.Definition2.15Let H be a hyperplane in R n and F be a face of a polytope P⊂R n.We say that H positively supports F up to translation if and only if there exists a vector x∈R n such that H∩P+x=F+x and P+x⊂H+.Remark:For any hyperplane H and any polytope P,both in R n,H positively supports exactly one faceH1H2Figure15:Some examples of supporting hyperplanes of the“housepolygon”.edgeset( ),Figure16:The edge set of a line segment contains two edges,since a line segment is treated as a degenerate rectangle.2.7Edge SetsHere we introduce some definitions to formalize the notion of the edges of a polygon.Notice that in this section we are only working in R2and thus are dealing with polygons rather than general polytopes.Definition2.16An edge-vector e of a polygon P is the vector parallel to some edge E of P with magnitude |E|.The direction of e is always chosen so that it points counterclockwise around P.The notion of notion of an edge-vector allows us to have the edges of P“Remember”their orientation in P.Remark:If a polygon P has two parallel edges of equal length,the corresponding edge-vectors are still distinquishable by their direction.Definition2.17Given a polygon P=conv(V)with V={v1,...,v k},the edge set of a polygon P is the set of all the edge-vectors of P.Notation:Let P be a polygon.The set of all edges of P is denoted edges(P).The set of all edge-vectors of P is denoted edgeset(P).Example2.16A single point polygon has an empty edge set.Example2.17Recall that a polygon which is a line segment can be treated as a degenerate rectangle;its edge set contains two edge-vectors which are the same line segment but opposite orientations.This example。

98Chapter 2.Solution of Linear Algebraic EquationsSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press. P rograms Copyright (C) 1988-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-readable files (including this one) to any server c omputer, is strictly prohibited. To order Numerical Recipes books, d iskettes, or CDROMs visit website or call 1-800-872-7423 (North America only), o r send email to trade@ (outside North America).x[i]=sum/p[i];}}A typical use of choldc and cholsl is in the inversion of covariancematrices describing the fit of data to a model;see,e.g.,§15.6.In this,and many other applications,one often needs L −1.The lower triangle of this matrix can be efficiently found from the output of choldc :for (i=1;i<=n;i++){a[i][i]=1.0/p[i];for (j=i+1;j<=n;j++){sum=0.0;for (k=i;k<j;k++)sum -=a[j][k]*a[k][i];a[j][i]=sum/p[j];}}CITED REFERENCES AND FURTHER READING:Wilkinson,J.H.,and Reinsch,C.1971,Linear Algebra ,vol.II of Handbook for Automatic Com-putation (New York:Springer-Verlag),Chapter I/1.Gill,P .E.,Murray,W.,and Wright,M.H.1991,Numerical Linear Algebra and Optimization ,vol.1(Redwood City,CA:Addison-Wesley),§4.9.2.Dahlquist,G.,and Bjorck,A.1974,Numerical Methods (Englewood Cliffs,NJ:Prentice-Hall),§5.3.5.Golub,G.H.,and Van Loan,C.F .1989,Matrix Computations ,2nd ed.(Baltimore:Johns HopkinsUniversity Press),§4.2.2.10QR DecompositionThere is another matrix factorization that is sometimes very useful,the so-called QR decomposition ,A =Q ·R(2.10.1)Here R is upper triangular,while Q is orthogonal,that is,Q T ·Q =1(2.10.2)where Q T is the transpose matrix of Q .Although the decomposition exists for a general rectangular matrix,we shall restrict our treatment to the case when all the matrices are square,with dimensions N ×N .Like the other matrix factorizations we have met (LU ,SVD,Cholesky),QR decompo-sition can be used to solve systems of linear equations.To solveA ·x =b(2.10.3)first form Q T ·b and then solveR ·x =Q T ·b(2.10.4)by backsubstitution.Since QR decomposition involves about twice as many operations as LU decomposition,it is not used for typical systems of linear equations.However,we will meet special cases where QR is the method of choice.2.10QR Decomposition 99Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press. P rograms Copyright (C) 1988-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-readable files (including this one) to any server c omputer, is strictly prohibited. To order Numerical Recipes books, d iskettes, or CDROMs visit website or call 1-800-872-7423 (North America only), o r send email to trade@ (outside North America).The standard algorithm for the QR decomposition involves successive Householder transformations (to be discussed later in §11.2).We write a Householder matrix in the form 1−u ⊗u /c where c =12u ·u .An appropriate Householder matrix applied to a given matrix can zero all elements in a column of the matrix situated below a chosen element.Thus we arrange for the first Householder matrix Q 1to zero all elements in the first column of A below the first element.Similarly Q 2zeroes all elements in the second column below the second element,and so on up to Q n −1.ThusR =Q n −1···Q 1·A(2.10.5)Since the Householder matrices are orthogonal,Q =(Q n −1···Q 1)−1=Q 1···Q n −1(2.10.6)In most applications we don’t need to form Q explicitly;we instead store it in the factored form (2.10.6).Pivoting is not usually necessary unless the matrix A is very close to singular.A general QR algorithm for rectangular matrices including pivoting is given in [1].For square matrices,an implementation is the following:#include <math.h>#include "nrutil.h"void qrdcmp(float **a,int n,float *c,float *d,int *sing)Constructs the QR decomposition of a[1..n][1..n].The upper triangular matrix R is re-turned in the upper triangle of a ,except for the diagonal elements of R which are returned in d[1..n].The orthogonal matrix Q is represented as a product of n −1Householder matrices Q 1...Q n −1,where Q j =1−u j ⊗u j /c j .The i th component of u j is zero for i =1,...,j −1while the nonzero components are returned in a[i][j]for i =j,...,n .sing returns as true (1)if singularity is encountered during the decomposition,but the decomposition is still completed in this case;otherwise it returns false (0).{int i,j,k;float scale,sigma,sum,tau;*sing=0;for (k=1;k<n;k++){scale=0.0;for (i=k;i<=n;i++)scale=FMAX(scale,fabs(a[i][k]));if (scale ==0.0){Singular case.*sing=1;c[k]=d[k]=0.0;}else {Form Q k and Q k ·A .for (i=k;i<=n;i++)a[i][k]/=scale;for (sum=0.0,i=k;i<=n;i++)sum +=SQR(a[i][k]);sigma=SIGN(sqrt(sum),a[k][k]);a[k][k]+=sigma;c[k]=sigma*a[k][k];d[k]=-scale*sigma;for (j=k+1;j<=n;j++){for (sum=0.0,i=k;i<=n;i++)sum +=a[i][k]*a[i][j];tau=sum/c[k];for (i=k;i<=n;i++)a[i][j]-=tau*a[i][k];}}}d[n]=a[n][n];if (d[n]==0.0)*sing=1;}The next routine,qrsolv ,is used to solve linear systems.In many applications only the part (2.10.4)of the algorithm is needed,so we separate it off into its own routine rsolv .100Chapter 2.Solution of Linear Algebraic EquationsSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press. P rograms Copyright (C) 1988-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-readable files (including this one) to any server c omputer, is strictly prohibited. To order Numerical Recipes books, d iskettes, or CDROMs visit website or call 1-800-872-7423 (North America only), o r send email to trade@ (outside North America).void qrsolv(float **a,int n,float c[],float d[],float b[])Solves the set of n linear equations A ·x =b .a[1..n][1..n],c[1..n],and d[1..n]are input as the output of the routine qrdcmp and are not modified.b[1..n]is input as the right-hand side vector,and is overwritten with the solution vector on output.{void rsolv(float **a,int n,float d[],float b[]);int i,j;float sum,tau;for (j=1;j<n;j++){Form Q T ·b .for (sum=0.0,i=j;i<=n;i++)sum +=a[i][j]*b[i];tau=sum/c[j];for (i=j;i<=n;i++)b[i]-=tau*a[i][j];}rsolv(a,n,d,b);Solve R ·x =Q T ·b .}void rsolv(float **a,int n,float d[],float b[])Solves the set of n linear equations R ·x =b ,where R is an upper triangular matrix stored in a and d .a[1..n][1..n]and d[1..n]are input as the output of the routine qrdcmp and are not modified.b[1..n]is input as the right-hand side vector,and is overwritten with the solution vector on output.{int i,j;float sum;b[n]/=d[n];for (i=n-1;i>=1;i--){for (sum=0.0,j=i+1;j<=n;j++)sum +=a[i][j]*b[j];b[i]=(b[i]-sum)/d[i];}}See [2]for details on how to use QR decomposition for constructing orthogonal bases,and for solving least-squares problems.(We prefer to use SVD,§2.6,for these purposes,because of its greater diagnostic capability in pathological cases.)Updating a QR decompositionSome numerical algorithms involve solving a successionof linear systems each of which differs only slightly from its predecessor.Instead of doing O (N 3)operations each time to solve the equations from scratch,one can often update a matrix factorization in O (N 2)operations and use the new factorization to solve the next set of linear equations.The LU decomposition is complicated to update because of pivoting.However,QR turns out to be quite simple for a very common kind of update,A →A +s ⊗t(2.10.7)(compare equation 2.7.1).In practice it is more convenient to work with the equivalent form A =Q ·R→A =Q ·R =Q ·(R +u ⊗v )(2.10.8)One can go back and forth between equations (2.10.7)and (2.10.8)using the fact that Q is orthogonal,givingt =v and eithers =Q ·u oru =Q T ·s(2.10.9)The algorithm [2]has two phases.In the first we apply N −1Jacobi rotations (§11.1)to reduce R +u ⊗v to upper Hessenberg form.Another N −1Jacobi rotations transform this upper Hessenberg matrix to the new upper triangular matrix R .The matrix Q is simply the product of Q with the 2(N −1)Jacobi rotations.In applications we usually want Q T ,and the algorithm can easily be rearranged to work with this matrix instead of with Q .2.10QR Decomposition101Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press. P rograms Copyright (C) 1988-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-readable files (including this one) to any server c omputer, is strictly prohibited. To order Numerical Recipes books, d iskettes, or CDROMs visit website or call 1-800-872-7423 (North America only), o r send email to trade@ (outside North America).#include <math.h>#include "nrutil.h"void qrupdt(float **r,float **qt,int n,float u[],float v[])Given the QR decomposition of some n ×n matrix,calculates the QR decomposition of the matrix Q ·(R +u ⊗v ).The quantities are dimensioned as r[1..n][1..n],qt[1..n][1..n],u[1..n],and v[1..n].Note that Q T is input and returned in qt .{void rotate(float **r,float **qt,int n,int i,float a,float b);int i,j,k;for (k=n;k>=1;k--){Find largest k such that u[k]=0.if (u[k])break;}if (k <1)k=1;for (i=k-1;i>=1;i--){Transform R +u ⊗v to upper Hessenberg.rotate(r,qt,n,i,u[i],-u[i+1]);if (u[i]==0.0)u[i]=fabs(u[i+1]);else if (fabs(u[i])>fabs(u[i+1]))u[i]=fabs(u[i])*sqrt(1.0+SQR(u[i+1]/u[i]));else u[i]=fabs(u[i+1])*sqrt(1.0+SQR(u[i]/u[i+1]));}for (j=1;j<=n;j++)r[1][j]+=u[1]*v[j];for (i=1;i<k;i++)Transform upper Hessenberg matrix to upper tri-angular.rotate(r,qt,n,i,r[i][i],-r[i+1][i]);}#include <math.h>#include "nrutil.h"void rotate(float **r,float **qt,int n,int i,float a,float b)Given matrices r[1..n][1..n]and qt[1..n][1..n],carry out a Jacobi rotation on rows i and i +1of each matrix.a and b are the parameters of the rotation:cos θ=a/√a 2+b 2,sin θ=b/√a 2+b 2.{int j;float c,fact,s,w,y;if (a ==0.0){Avoid unnecessary overflow or underflow.c=0.0;s=(b >=0.0?1.0:-1.0);}else if (fabs(a)>fabs(b)){fact=b/a;c=SIGN(1.0/sqrt(1.0+(fact*fact)),a);s=fact*c;}else {fact=a/b;s=SIGN(1.0/sqrt(1.0+(fact*fact)),b);c=fact*s;}for (j=i;j<=n;j++){Premultiply r by Jacobi rotation.y=r[i][j];w=r[i+1][j];r[i][j]=c*y-s*w;r[i+1][j]=s*y+c*w;}for (j=1;j<=n;j++){Premultiply qt by Jacobi rotation.y=qt[i][j];w=qt[i+1][j];qt[i][j]=c*y-s*w;qt[i+1][j]=s*y+c*w;}}102Chapter 2.Solution of Linear Algebraic EquationsSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press. P rograms Copyright (C) 1988-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-readable files (including this one) to any server c omputer, is strictly prohibited. To order Numerical Recipes books, d iskettes, or CDROMs visit website or call 1-800-872-7423 (North America only), o r send email to trade@ (outside North America).We will make use of QR decomposition,and its updating,in §9.7.CITED REFERENCES AND FURTHER READING:Wilkinson,J.H.,and Reinsch,C.1971,Linear Algebra ,vol.II of Handbook for Automatic Com-putation (New York:Springer-Verlag),Chapter I/8.[1]Golub,G.H.,and Van Loan,C.F .1989,Matrix Computations ,2nd ed.(Baltimore:Johns HopkinsUniversity Press),§§5.2,5.3,12.6.[2]2.11Is Matrix Inversion an N 3Process?We close this chapter with a little entertainment,a bit of algorithmic prestidig-itation which probes more deeply into the subject of matrix inversion.We start with a seemingly simple question:How many individual multiplications does it take to perform the matrix multiplication of two 2×2matrices,a 11a 12a 21a 22·b 11b 12b 21b 22= c 11c 12c 21c 22(2.11.1)Eight,right?Here they are written explicitly:c 11=a 11×b 11+a 12×b 21c 12=a 11×b 12+a 12×b 22c 21=a 21×b 11+a 22×b 21c 22=a 21×b 12+a 22×b 22(2.11.2)Do you think that one can write formulas for the c ’s that involve only seven multiplications?(Try it yourself,before reading on.)Such a set of formulas was,in fact,discovered by Strassen [1].The formulas are:Q 1≡(a 11+a 22)×(b 11+b 22)Q 2≡(a 21+a 22)×b 11Q 3≡a 11×(b 12−b 22)Q 4≡a 22×(−b 11+b 21)Q 5≡(a 11+a 12)×b 22Q 6≡(−a 11+a 21)×(b 11+b 12)Q 7≡(a 12−a 22)×(b 21+b 22)(2.11.3)。