Diagonalisation Of Para-hermitian Matrix : Is It Always .

Diagonalisation of Para-hermitian Matrix :is it always possible ?Sylvie IcartLaboratoire I3SUniversité Côte d’Azur – Université Nice Sophia AntipolisS. IcartSMD181 / 21

PEVD : eigen vectors/eigen valuesAn example of application : blind equalizationSome useful definitions on Laurent polynomialsSmith form over the ring of Laurent polynomial matricesProperties of para-hermitian and para-unitary matricesOrder vs degree of a polynomial matrixExample of a non diagonalisable PH matrixand then . . .S. IcartSMD182 / 21

Polynomial Eigenvalue DecompositionLet M(z) be a Laurent polynomial matrix M(z) Cn n [z, z 1 ] :M(z) pXM k z k , M k Cn n , m, p Z, m pk mPEVD [McWhirter] :Given M(z) Cn n [z, z 1 ], find λ(z) C[z, z 1 ] , v (z) Cn [z, z 1 ] s.t.M(z)v (z) λ(z)v (z), zHere, the ”eigenvalues” are (Laurent) polynomial.Eigenvalue ofPa polynomial matrix [Lancaster] :kroots of det( mk 0 λ M k ) 0, so λ C.PEVD for para-hermitian matrices and ”orthonormal” eigenvectors(analog : each hermitian matrix can be diagonalized by an unitary matrix)S. IcartSMD183 / 21

Blind EqualizationProblem settingn sources p p(k)ŝn(k)Blind equalization : channel and sources are unknownFind approximation ŝi of sources siHypotheseswhite i.i.d. sourcesnumber of sources number of observationsconvolutive mixture, FIR channel : C (z) Cn n [z 1 ]Non unique solution : up to (z)Pwith (z) diag {z i } and P permutationS. IcartSMD184 / 21

s(k)M(z)w(k)Let Γw (z) be the Cross Spectral Density of observations :Γw (z) M(z)Γs (z)M H (1)z if Γs (z) I , then Γw (z) M(z)M H ( z1 ), and1) Γw (z)z Γw (z) is a para-hermitian matrixΓHw((even if M(z) Cn n [z 1 ] , Γw (z) Cn n [z, z 1 ])if moreover Γw (z) I (whitened observations), thenM(z)M H (1) Iz M(z) is a para-unitary matrixS. IcartSMD185 / 21

Some useful definitions and properties of polynomialsPolynomials Let C[z] be the ring of polynomialsp(z) nXpi z i with n N, pi Ci 0if pn 6 0, deg(p) n, moreover if pn 1, p is monic.if pn 1 and p0 6 0, p is L-monic (no roots in 0)(analog definitions for p C[z 1 ] )Laurent polynomials Let C[z, z 1 ] be the ring of Laurent polynomials :p(z) nXpi z i with m, n Z, m n, pi Ci mif pm pn 6 0, d(p) n m is the L-degree of p.if p C[z], d(p) deg(p) iff z 0 is not a root of p.S. IcartSMD186 / 21

C[z, z 1 ] is an Euclidean ring, so a Principal Ideal Domain (PID)Units of C[z, z 1 ] : non-zero monomialsp(z) az α , a C , α ZUnicity of gcd : impose the gcd to be L-monic (no roots in 0 neither )Para-conjugation :pe(z) p (1), z C z rmq : if p(z) C[z] then pe(z) C[z 1 ].Para-hermitian polynomial : pe p p(z) dXpi z i , p i pi .i dPara-unitary polynomial : pep 1 p(z) e θ z α , θ R, α Z.S. IcartSMD187 / 21

Laurent polynomial matrix Cn n [z, z 1 ]a L-polynomial with matrix-valued coefficientsM(z) pXM k z k , M k Cn n , m, p Z, m pk mor. a matrix with L-polynomial entriesM(z) (mij (z)) with mij (z) pXmijk z kk mi and j ”space”-indices and k time-indiceorder of M p m if M p and M m are non zeroS. IcartSMD188 / 21

Cn n [z, z 1 ] is the ring of L-polynomial matricesL-unimodular matrices : Units of Cn n [z, z 1 ]det(M(z)) az α , a C , α Zd (det(M(z))) 0 : zeros at 0 or infinitySmith form over Cn n [z, z 1 ] :Let M Cn n [z, z 1 ], L-unimodular U 1 , U 2 Cn n [z, z 1 ]U 1 (z)M(z)U 2 (z) Λ(z)with Λ(z) diagonalS. IcartSMD189 / 21

Invariant polynomials λ1 (z) Λ(z) .λr (z)0 0 0λi unique up to a multiplication by a monomial.λi divides λi 1 .r normal rank of M.To ensure unicity : λi L-monic (monic polynomial and no roots in 0)Invariant polynomials can be computed asλi (z) i (M(z)) i 1 (M(z)) i (M(z)) L-monic gcd of i i minors of M.S. IcartSMD1810 / 21

Examples zA(z) z 0, order(A) 0zSgcd{z, z, z} z, det A(z) z 2 , so A(z) zILSL-gcd{z, z, z} 1, L-gcd{z 2 } 1, so A(z) I . z00LSS 1and B(z) IB(z) , order(B) 1 , B(z) z 1 z0 z2U 1 (z)B(z)U 2 (z) I with 1 11 zU 1 (z) and U 2 (z) (non unique). z 1 z 2 z 10 1S. IcartSMD1811 / 21

Para-conjugation :1fM(z) M H ( ), z C zfthen, on the unit circle : M(z) M H (z).Para-hermitian property :fM(z) M(z)extension of symmetric (M Rn n ) or hermitian (M Cn n ) propertyPara-unitary property :fM(z)M(z) Iextension of unitary propertyS. IcartSMD1812 / 21

Some properties of PH and PU matriceseif H(z) is PH H(z) H(z)dXH(z) H k z k with H k H Hk , kk dthe order of H(z) is even (2d)Peif U is PU U(z)U(z) I of order l, U(z) z m lk 0 U k z k l X UkUH k I k 0lX Uj UH j k 0 k {1, . . . , l} j kS. IcartSMD1813 / 21

L-invariant polynomials propertiesL-unimodular matrix (det(U) az α ) : λi (z) 1, idet U(z) az α det U 1 (z) det Λ(z) det U 2 (z),so det Λ(z) cz β , but λi are L-monic, so λi (z) 1, i.e I ) : λi (z) 1, iPara-unitary matrix (U UQQedet U(z)U(z) 1 cz α ni 1 λi (z)c z α ni 1 λei (z)so λi invertible and as λi L-monic, λi 1.LSPara-unitary matrix L-unimodular matrixe : λi self-inversivePara-hermitian matrix (H H)ei (z) with θi R, mi deg(λi )λi (z) e θi z mi λLSfH but Λ e is not the L-Smith form of HΛHe ΛHfH Cn n [z 1 ] (and ΛH Λ e Cn n [z])because ΛHS. IcartSMD1814 / 21

Order vs DegreeOrder defined for polynomial matrices [Kailath, Vaidyanathan],Degree defined for proper rational matrices : sum of the degrees ofthe denominators of the Smith Mc Millan form, it is the minimumnumber of delays to implement M.Example :11zzH(z) 1zLet N(z) H 2 z 2 H 1 z 1 H 0 , order of H(z) is 21 z 2z2z 2 H(z)polynomial. 10Smith form of N : S(z) 0 z(1 z 2 ) z 2Smith Mc Millan form of H(z) : SM(z) 1S(z)z2 1 z200 1 z z 2zMc Millan degree of H(z) is 2 1 3.S. IcartSMD1815 / 21

Degree of Laurent polynomial matrices (proposition)Let H(z) pXH k z k , m p, H m and H p 6 0.k mDefine the associated causal matrix (polynomial in z 1 ) :H(z) z p H(z)order of H p mL-degree of H : McMillandegree of H.11Example : H(z) H 1 z 1 H 0 H 1 z, order 21 z 1 z 1zz 1 1(previous example), L-degree 3H(z) z H(z) 1z1 z 2S. IcartSMD1816 / 21

PropertyIf U(z) is para-unitary, its order and its L-degree are equal.Proof : based onVaidyanathan’s factorization of a FIR paraunitary matrix : 1 0U(z) R 0 Z (z)R 1 . . . Z (z)R N 1 Z (z)R N0 1 1 0cos θiZ (z) , Ri 10 z sin θi sin θi, N MacMillan degree.cos θiand that, by definition U 0 6 0S. IcartSMD1817 / 21

Diagonalization of a PH matrixProposition :Let H(z) be a PH matrix, does there exist U(z) a PU matrix such that :eU(z)H(z)U(z) Λ(z)with Λ(z) a Laurent polynomial diagonal matrix ?(an hermitian matrix is diagonalizable by a unitary matrix)not always true (see example)if exist, ”eigen vectors” are orthonormal w.r.te(z)v (z) u H (hu(z), v (z)i u1)v (z), z C z Λ(z) can be approximated by a rational matrix, and by truncation, apolynomial matrix [Weiss]S. IcartSMD1818 / 21

Example 11e det H(z) 2z 1 5 2zLet H(z) , H H,1 2z 1 6 2z 10L-Smith form : S(z) 0 1 52 z z 2LSeSuppose U paraunitary s.t. UHU Λ ; S Λ,So, ”eigen values” have to verify :0L-gcd{λ1 , λ2 } 1 and λ1 (z)λ2 (z) c 0 z α det H(z).But λi , if exist, are parahermitian, so (up to a permutation) :λ1 (z) c, c R and λ2 (z) dz β (1 52 z z 2 ).Now, parametrizing H(z)v (z) cv (z), c R leads to a system withoutany solution.eThere exists no polynomial unitary matrix s.t. UHU Λ.(H as order 2 but degree 4)S. IcartSMD1819 / 21

The PEVD has not always an exact solution.There exits approximated solution at least on the unit circle.There exit iterative algorithms (Jacobi type, Extended Givens rotationwith delay).Open problemOn which condition does there exist a polynomial solution ? (degreevs order ) ?Can we write this problem with tensors of order 3 (coefficientrelations of PH and PU matrices) ?S. IcartSMD1820 / 21

Bibliography :J. G. McWhirter et al. An EVD algorithm for Para-Hermitian polynomialmatrices, IEEE T. Signal Processing, 2007T. Kailath : Linear Systems, Prentice Hall, Information and SystemSciences Series, 1980P.P. Vaidyanathan. Multirate Systems and Filter Bank, Prentice Hall, SignalProcessing Series, 1993S. Weiss et al. On the existence and uniqueness of the eigenvaluedecomposition of a parahermitian matrix, T. Signal Processing, 2018S. IcartSMD1821 / 21

Diagonalization of a PH matrix Proposition : Let H(z) be a PH matrix, does there exist U(z) a PU matrix such that : Ue(z)H(z)U(z) (z) with (z) a Laurent polynomial diagonal matrix? (an hermitian matrix is diagonalizable by a unitary matrix) not always true (see example) if exist, "eigen