A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices

28/08/2013
OAI : oai:www.see.asso.fr:2552:5067
DOI :

Résumé

A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices

Métriques

105
12
789.83 Ko
 application/pdf
bitcache://8303fc45cd61ffdd1653c2d3363c7b99b221a477

Licence

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

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

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

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/2552/5067</identifier><creators><creator><creatorName>Martin Kleinsteuber</creatorName></creator></creators><titles>
            <title>A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 5 Oct 2013</date>
	    <date dateType="Updated">Mon 25 Jul 2016</date>
            <date dateType="Submitted">Fri 10 Aug 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">8303fc45cd61ffdd1653c2d3363c7b99b221a477</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>25090</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Fachgebiet Geometrische Optimierung und Maschinelles Lernen A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices Martin Kleinsteuber joint work with Hao Shen Research Group for Geometric Optimization and Machine Learning www.gol.ei.tum.de August 29, 2013 Slide 1/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Outline Mixing model and problem statement Separating with second order information The geometric setting for NUJD Uniqueness result for complex NUJD Conclusion Slide 2/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The complex linear BSS Model Mixing model: w(t) = As(t), A ∈ Gl(m). s(t) = [s1(t), . . . , sm(t)]T : m-dimensional complex signal w(t): observed signals Mixing matrix A ∈ Gl(m) (set of all invertible complex (m × m)-matrices) Task: Recover s(t) given w(t) only, via the demixing model y(t) = XH w(t) Demixing matrix X ∈ Gl(m) Slide 3/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The complex linear BSS Model Mixing model: w(t) = As(t), A ∈ Gl(m). s(t) = [s1(t), . . . , sm(t)]T : m-dimensional complex signal w(t): observed signals Mixing matrix A ∈ Gl(m) (set of all invertible complex (m × m)-matrices) Task: Recover s(t) given w(t) only, via the demixing model y(t) = XH w(t) Demixing matrix X ∈ Gl(m) Slide 3/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Second-Order Statistics Based ICA Approaches Idea Use the uncorrelation assumption of the source signals to estimate the mixing matrix. Covariance of observations: Cw (t) := E[w(t)wH (t)] = A E[s(t)sH (t)] =:Cs(t) AH , Cs(t) is diagonal for non-stationary signals: Cw (ti) = Cw (tj) estimate A by simultaneously diagonalizing a set of covariance matrices Slide 4/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Second-Order Statistics Based ICA Approaches Idea Use the uncorrelation assumption of the source signals to estimate the mixing matrix. Covariance of observations: Cw (t) := E[w(t)wH (t)] = A E[s(t)sH (t)] =:Cs(t) AH , Cs(t) is diagonal for non-stationary signals: Cw (ti) = Cw (tj) estimate A by simultaneously diagonalizing a set of covariance matrices Slide 4/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Second-Order Statistics Based ICA Approaches Pseudo-Covariance of observations: Rw (t) := E[w(t)wT (t)] = ARs(t)AT . Rs(t) is diagonal for non-stationary signals: Rw (ti) = Rw (tj) estimate A by simultaneously diagonalizing a set of Pseudo-covariance matrices Slide 5/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Second-Order Statistics Based ICA Approaches Pseudo-Covariance of observations: Rw (t) := E[w(t)wT (t)] = ARs(t)AT . Rs(t) is diagonal for non-stationary signals: Rw (ti) = Rw (tj) estimate A by simultaneously diagonalizing a set of Pseudo-covariance matrices Slide 5/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Second-Order Statistics Based ICA Approaches Time-delayed (pseudo-)correlation Sw (t, τ) := E[w(t)w† (t + τ)] = ASs(t, τ)A† . Ss(t, τ) is diagonal, † = T, H Sw are not Hermitian or Symmetric in general estimate A by simultaneously diagonalizing a set of time-delayed (pseudo-)correlation estimate A by combining all the second order information Slide 6/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Second-Order Statistics Based ICA Approaches Time-delayed (pseudo-)correlation Sw (t, τ) := E[w(t)w† (t + τ)] = ASs(t, τ)A† . Ss(t, τ) is diagonal, † = T, H Sw are not Hermitian or Symmetric in general estimate A by simultaneously diagonalizing a set of time-delayed (pseudo-)correlation estimate A by combining all the second order information Slide 6/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Second-Order Statistics Based ICA Approaches Time-delayed (pseudo-)correlation Sw (t, τ) := E[w(t)w† (t + τ)] = ASs(t, τ)A† . Ss(t, τ) is diagonal, † = T, H Sw are not Hermitian or Symmetric in general estimate A by simultaneously diagonalizing a set of time-delayed (pseudo-)correlation estimate A by combining all the second order information Slide 6/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The SUT-algorithm [Eriksson, Koivunen 2004] Particular task Diagonalize Cw (t) and Rw (t) simultaneously via XH Cw (t)X, and XH Rw (t)X∗ Pseudo-Code: 1. Diagonalize C = UΦUH via SVD 2. Compute R = Φ−1/2UHRU∗Φ−1/2 3. Diagonalize R = VΨVT via Takagi factorization 4. Output X = UΦ−1/2V Slide 7/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The SUT-algorithm [Eriksson, Koivunen 2004] Particular task Diagonalize Cw (t) and Rw (t) simultaneously via XH Cw (t)X, and XH Rw (t)X∗ Pseudo-Code: 1. Diagonalize C = UΦUH via SVD 2. Compute R = Φ−1/2UHRU∗Φ−1/2 3. Diagonalize R = VΨVT via Takagi factorization 4. Output X = UΦ−1/2V Slide 7/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Non-unitary joint diagonalization Problem Given a set of complex symmetric (Pseudo-covariance-) matrices {Ri}i=1,...,n, find X ∈ Gl(m) such that XTRiX are all diagonal. Permutation and scale ambiguity of solutions X is solution ⇐⇒ XDΠ is solution D diagonal, Π Permutation Optimization methods like to have isolated solutions, what to do? Slide 8/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The geometric setting for NUJD let D := {D | D ∈ Gl(m) is diagonal} equivalence classes X := {XD ∈ Gl(m) | D ∈ D } complex oblique projective (COP) manifold Op := { X | X ∈ Gl(m) } Slide 9/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The geometric setting for NUJD Let f : Gl(m) → R be a function that measures simultaneous diagonality. e.g. reconstruction error X → n i=1 1 4 Ri − X−T ddiag(XT Ri X)X−1 2 F then f(X) = f(XD) naturally induces a function ˆf on Op Idea Optimize ˆf on the COP manifold. lower dimensional search space chance to have non-degenerated minima Slide 10/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The geometric setting for NUJD Let f : Gl(m) → R be a function that measures simultaneous diagonality. e.g. reconstruction error X → n i=1 1 4 Ri − X−T ddiag(XT Ri X)X−1 2 F then f(X) = f(XD) naturally induces a function ˆf on Op Idea Optimize ˆf on the COP manifold. lower dimensional search space chance to have non-degenerated minima Slide 10/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The geometric setting for NUJD Op is open and dense Riemannian submanifold of product of CPm−1 tangent spaces, geodesics, parallell transport coincide locally remains to consider CPm−1 = Sm/S1 with Sm := {x ∈ Cm | xH x = 1} [Absil et al. Optimization Algorithms on Matrix Manifolds, Princeton Press, 2008] No representation of CPm−1 in Cm. Use rank-1 projection matrices in Cm×m? Here: Use quotient-space properties. Slide 11/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The geometric setting for NUJD Op is open and dense Riemannian submanifold of product of CPm−1 tangent spaces, geodesics, parallell transport coincide locally remains to consider CPm−1 = Sm/S1 with Sm := {x ∈ Cm | xH x = 1} [Absil et al. Optimization Algorithms on Matrix Manifolds, Princeton Press, 2008] No representation of CPm−1 in Cm. Use rank-1 projection matrices in Cm×m? Here: Use quotient-space properties. Slide 11/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The geometric setting for NUJD identify tangent space at x ∈ CPm−1 with the horizontal lift of the tangent space at x T x CPm−1 = z∈S1 TxzSm = z∈S1 {h ∈ Cm | (hH xz) = 0} = {h ∈ Cm | hH x = 0}. Slide 12/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The geometric setting for NUJD Result A The geodesics in CPm−1 through x are given by γ(t) with γ(t) := et(hxH−xhH) x. Result B The parallel transport from T γ(0) CPm−1 to T γ(t) CPm−1 along the geodesic γ(t) is given by τ(t) := et(hxH−xhH) h. Slide 13/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen The geometric setting for NUJD results transfer straightforwardly to Op (use product manifold structure) All ingredients for a geometric Conjugate Gradient method for minimizing ˆf. Slide 14/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Separation performance AC/DC Off−norm CG Proposed CG 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Amarierror AC/DC: alternating algorithm minimizing the direct fit cost function Off-norm CG: a CG algorithm minimizing the off-norm cost function Slide 15/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Uniqueness result for complex NUJD Well known: Good local convergence properties of CG if minimum has non degenerated Hessian Under what conditions on the source signals is the minimizer isolated on the COP manifold? Equivalently: Under what conditions on the source signals is the diagonalizer unique (up to permutation and diagonal scaling)? Slide 16/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Uniqueness result for complex NUJD Let Dk be the (diagonal) Pseudo-Covariances of the signals. Let di be a complex vector consisting of all diagonal entries of Dk at the i − th position. L PROCESSING MAGAZINE: SPECIAL ISSUE ON SOURCE SEPARATION AND APPLICATIONS d12 0 0 d11 D1 d22 0 0 d21 D2 · · · dK2 0 0 dK1 DK =⇒ [d11, d21, . . . , dK1] =: dT 1 . . . =⇒ [d12, d22, . . . , dK2] =: dT 2 Dk := diag(dk1, dk2) ∈ C2×2 for k = 1, . . . , K. For a fixed diagonal position i, we denote by di := [d1i, . . . , dKi]T ∈ onsisting of the i-th diagonal element of each matrix, respectively. PIEEE Signal Processing Magazine Slide 17/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Uniqueness result for complex NUJD Result (MK, Shen 2013) The simultaneous diagonalizer is unique up to permutation and scaling if and only if |c(di, dj)| = 1, i = j, with c(v, w) := vH w v w if v = 0 and w = 0, 1 otherwise, Slide 18/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Literature Absil et al.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton, NJ (2008). Kleinsteuber, M., Shen, H.: Uniqueness analysis of non-unitary matrix joint diagonalization. IEEE Transactions on Signal Processing 61(7) (2013) 1786–1796. Shen, H., Kleinsteuber, M.: Complex blind source separation via simultaneous strong uncorrelating transform. In: LNCS, Proc. 9th International Conference on Latent Variable Analysis and Signal Separation. Volume 6365., Berlin/Heidelberg, Springer-Verlag (2010) 287–294 Slide 19/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Conclusion Simultaneous diagonalization of matrices based on second order statistics. Complex Oblique Projective Manifold is appropriate geometric setting. Under generic conditions on the sources, the diagonalizer is isolated on the COP manifold. Slide 20/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Conclusion Simultaneous diagonalization of matrices based on second order statistics. Complex Oblique Projective Manifold is appropriate geometric setting. Under generic conditions on the sources, the diagonalizer is isolated on the COP manifold. Slide 20/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Conclusion Simultaneous diagonalization of matrices based on second order statistics. Complex Oblique Projective Manifold is appropriate geometric setting. Under generic conditions on the sources, the diagonalizer is isolated on the COP manifold. Slide 20/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Preprints and Matlab codes available at www.gol.ei.tum.de Slide 21/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber | Fachgebiet Geometrische Optimierung und Maschinelles Lernen Properties of complex signals Second order stationarity: (i) E[s(t)] = E[s(t + τ)] (ii) E[s(t1)s(t2)] = E[s(t1 + τ)s(t2 + τ)] Circularity: s(t) and eiαs(t) have the same probability distribution This implies E[s(t)2 ] = 0 and motivates the circularity coefficient λs(t) := |E[s(t)2 ]| E[|s(t)|2] Slide 22/22 | A Geometric Framework for Non-unitary Joint Diagonalization of Complex Symmetric Matrices | Martin Kleinsteuber |