Block-Jacobi methods with Newton-steps and non-unitary joint matrix diagonalization

28/10/2015
Publication GSI2015
OAI : oai:www.see.asso.fr:11784:14321

Résumé

In this work, we consider block-Jacobi methods with Newton steps in each subspace search and prove their local quadratic convergence to a local minimum with non-degenerate Hessian under some orthogonality assumptions on the search directions. Moreover, such a method is exemplified for non-unitary joint matrix diagonalization, where we present a block-Jacobi-type method on the oblique manifold with guaranteed local quadratic convergence.

Block-Jacobi methods with Newton-steps and non-unitary joint matrix diagonalization

Collection

application/pdf Block-Jacobi methods with Newton-steps and non-unitary joint matrix diagonalization Martin Kleinsteuber, Hao Shen

Média

Voir la vidéo

Métriques

202
4
302.68 Ko
 application/pdf
bitcache://916a443e33b9a75cf6be16ceee7f7f9cfc9b8eeb

Licence

Creative Commons Attribution-ShareAlike 4.0 International

Sponsors

Organisateurs

logo_see.gif
logocampusparissaclay.png

Sponsors

entropy1-01.png
springer-logo.png
lncs_logo.png
Séminaire Léon Brillouin Logo
logothales.jpg
smai.png
logo_cnrs_2.jpg
gdr-isis.png
logo_gdr-mia.png
logo_x.jpeg
logo-lix.png
logorioniledefrance.jpg
isc-pif_logo.png
logo_telecom_paristech.png
csdcunitwinlogo.jpg
<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/11784/14321</identifier><creators><creator><creatorName>Martin Kleinsteuber</creatorName></creator><creator><creatorName>Hao Shen</creatorName></creator></creators><titles>
            <title>Block-Jacobi methods with Newton-steps and non-unitary joint matrix diagonalization</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2015</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><subjects><subject>Jacobi algorithms</subject><subject>Local convergence properties</subject><subject>Manifold optimization</subject><subject>Signal separation</subject></subjects><dates>
	    <date dateType="Created">Sun 8 Nov 2015</date>
	    <date dateType="Updated">Wed 31 Aug 2016</date>
            <date dateType="Submitted">Fri 20 Apr 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">916a443e33b9a75cf6be16ceee7f7f9cfc9b8eeb</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>24714</version>
        <descriptions>
            <description descriptionType="Abstract">
In this work, we consider block-Jacobi methods with Newton steps in each subspace search and prove their local quadratic convergence to a local minimum with non-degenerate Hessian under some orthogonality assumptions on the search directions. Moreover, such a method is exemplified for non-unitary joint matrix diagonalization, where we present a block-Jacobi-type method on the oblique manifold with guaranteed local quadratic convergence.

</description>
        </descriptions>
    </resource>
.

Fachgebiet Geometrische Optimierung und Maschinelles Lernen Block-Jacobi Methods with Newton-steps and Non-unitary Joint Matrices Diagonalization Martin Kleinsteuber joint work with Hao Shen Research Group for Geometric Optimization and Machine Learning www.gol.ei.tum.de October 30, 2015 Slide 1/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Outline Introduction Block-Jacobi-Type Methods on Manifolds Local Convergence Analysis Non-unitary Joint Matrices Diagonalization Conclusion Slide 2/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Jacobi-type methods for diagonalization EVD of Hermitian Matrix (Jacobi, 1864) many structured EVD problems Jointly diagonalizing Hermitian Matrices - JADE (Cardoso, 1999) Block Jacobi methods for structured EVD Block-Jacobi for ICA (Shen, 2007) Why? no need to compute gradients inherently parallelizable fast (superlinear) convergence Slide 3/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Jacobi-type methods for diagonalization Problem formulation Given matrices Ai, find X ∈ M (matrix manifold) such that XAiX†i are diagonal. (1) †i : transpose, conjugate transpose, inverse,... Approach: Successively minimize (joint) diagonality measure f : M → R along some predefined curves on M Slide 4/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Jacobi-type methods for diagonalization Problem formulation Given matrices Ai, find X ∈ M (matrix manifold) such that XAiX†i are diagonal. (1) †i : transpose, conjugate transpose, inverse,... Approach: Successively minimize (joint) diagonality measure f : M → R along some predefined curves on M Example: M is unitary group and predefined curves are Givens rotations in cyclic ordering Slide 4/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Jacobi-type methods for diagonalization Two issues play a major role: (simple) Jacobi vs. Block-Jacobi: minimize along some predefined subsets on M exact vs. approximate step-wise minimization K. H¨uper 2002: Block Jacobi on manifolds with exact line search Slide 5/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Jacobi-type methods for diagonalization Two issues play a major role: (simple) Jacobi vs. Block-Jacobi: minimize along some predefined subsets on M exact vs. approximate step-wise minimization K. H¨uper 2002: Block Jacobi on manifolds with exact line search In this talk: general setting for block-type methods on manifolds superlinear convergence rate for Newton-step search Slide 5/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Block-Jacobi-Type Methods on Manifolds Ingredients n-dimensional manifold M smooth cost function f : M → R family of smooth local parameterizations µ: Rn × M → M (2) such that µx : Rn → M, v → µ(v, x) is local diffeo and µ(0, x) = x Slide 6/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Block-Jacobi-Type Methods on Manifolds Ingredients n-dimensional manifold M smooth cost function f : M → R family of smooth local parameterizations µ: Rn × M → M (2) such that µx : Rn → M, v → µ(v, x) is local diffeo and µ(0, x) = x Example: φ: Rn × M → TM local trivialization of tangent bundle R : TM → M retraction, then µ = R ◦ φ does the job Slide 6/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Block-Jacobi-Type Methods on Manifolds One Jacobi Sweep (one dimensional, exact search) INPUT: initial point x(0) ∈ M and basis v1, . . . , vn of Rn FOR i = 1, . . . , n DO STEP 1. Compute the local minimum t∗ with smallest absolute value of ϕ: R → R, t → f ◦ µx(i−1) (vi t) (3) STEP 2. Set x(i) := µx(i−1) (vi t∗ ). OUTPUT x(n) Slide 7/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Block-Jacobi-Type Methods on Manifolds M px(i−1) µx(i−1) (vi · R) p x(i) µx(i) (vi+1 · R) p x(i+1) µx(i+1) (vi+2 · R) p x(i+2) W - 1 Figure: Illustration of Jacobi-type method on smooth manifolds. Slide 8/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Block-Jacobi-Type Methods on Manifolds One Jacobi Sweep (one dimensional, approximate Newton search): Replace STEP 1. Compute the local minimum t∗ with smallest absolute value of ϕ: R → R, t → f ◦ µx(i−1) (vit) (4) with a Newton-step ALT. STEP 1. Set t∗ := − d2 d t2 ϕ(t) t=0 −1 d d t ϕ(t) t=0 (5) Slide 9/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Block-Jacobi-Type Methods on Manifolds multidimensional (i.e. ”block”), approximate Newton search: Let < n ”block”-dimension, t ∈ R and V = [v1, . . . , v ] ϕ: R → R, t → f ◦ µx(i−1) (Vt) (6) use Newton step STEP 1*. Set t∗ := −Hϕ(0)−1 ϕ(0) (7) Hϕ(0) Hessian matrix ϕ(0) standard gradient Slide 10/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Block-Jacobi-Type Methods on Manifolds One Jacobi Sweep (multidimensional, approx. Newton) INPUT: initial point x(0) ∈ M and ”direct sum” V1, . . . , Vr of Rn FOR i = 1, . . . , r DO STEP 1*. Set t∗ := −Hϕi (0)−1 ϕi (0), (8) where ϕi : R i → R, t → f ◦ µx(i−1) (Vi t) (9) STEP 2. Set x(i) := µx(i−1) (Vi t∗ ). OUTPUT x(n) Slide 11/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Potential Applications Further examples: Noncircular Complex ICA. Li & Adalı, Noncircular Complex ICA by Generalized Householder Reflections, IEEE-TSP, 2013 Tensor Factorization. Xu & Yin, A Block Coordinate Descent Method for Regularized Multiconvex Optimization with Applications to Nonnegative Tensor Factorization and Completion, SIIMS, 2013 Slide 12/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Local Convergence Analysis Algorithm: Iterate sweeps xk+1 = s(xk ). Theorem Let f be smooth, x∗ local minimum of f, Hessian form Hf (x∗) nondegenerate. If the subspaces Vi := T0µx∗ (Vi) ⊂ Tx∗ M are orthogonal w.r.t. Hf (x∗) Then Block Jacobi with approx. Newton steps is locally quadratically convergent to x∗ , i.e. xk+1 − x∗ ≤ const xk − x∗ 2 (10) for x0 close enough to x∗. Slide 13/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Local Convergence Analysis Proof: One sweep: s: M → M x∗ is a fixed point (stepsize t∗(x∗) = 0 for all steps) Consider one step within one sweep r : M → M, x → µ(Vit∗ (x), x). (11) Let ξ ∈ Tx∗ M, Dr(x)|x=x∗ ξ = D1µ(Vi(Dt∗ (x)|x=x∗ ξ), x∗ ) + D2µ(0, x)|x=x∗ ξ = D1µ(Vi(Dt∗ (x)|x=x∗ ξ), x∗ ) + ξ Slide 14/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Local Convergence Analysis Proof, continued: Recall: t∗ := −Hϕi (0)−1 ϕi (0) product rule Dt∗ (x)|x=x∗ ξ = − DHϕ(0)−1 ξ ϕ(0)|x=x∗ (12) − Hϕ(0)−1 D ϕ(0)|x=x∗ ξ (13) Then, show that if ξi is in the span of Vi = T0µx∗ (Vi) and ξ⊥ i is such that Hf (x∗)[Vi, ξ⊥ i ] = 0 D1µ(Vi(Dt∗ (x)|x=x∗ ξi), x∗ ) = −ξi (14) D1µ(Vi(Dt∗ (x)|x=x∗ ξ⊥ i ), x∗ ) = 0 (15) Hence Dr(x)|x=x∗ is orthogonal projection onto V⊥ i w.r.t. Hessian. Slide 15/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Local Convergence Analysis Proof, continued: Using that r(x∗) = x∗ for each step yields Ds(x∗) = 0. Using a Taylor-type argument yields s(x) − x∗ ≤ const x − x∗ 2 (16) for all x close to x∗. Slide 16/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Local Convergence Analysis Discussion Orthogonality w.r.t. nondegenerate Hessian is sufficient for superlinear convergence Ds(x∗) = 0 is necessary and sufficient. In practice: noise influences the Hessian of cost; orthogonality may get lost Slide 17/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Non-unitary Joint Matrices Diagonalization Task Given matrices Ci, find X with normalized columns such that XT CiX are diagonal. (17) manifold: OB(m) := X ∈Rm×m| ddiag(XTX) = Im, , zero-diagonal matrices off(m) = Z ∈ Rm×m|zii = 0, for i = 1, . . . , m family of local parameterisation µ: off(m) × OB(m)→OB(m), (Z, X)→X(Im +Z) diag 1 X(e1+z1) , . . . , 1 X(em+zm) , Slide 18/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015 Fachgebiet Geometrische Optimierung und Maschinelles Lernen Non-unitary Joint Matrices Diagonalization Cost function: f(X) = 1 4 n i=1 off(XT CiX) 2 F (18) Let X∗ ∈ OB(m) be a joint diagonalizer. Then, with ξ1 = µ(Y, X∗), ξ2 = µ(Z, X∗) the Hessian at X∗ is Hf (X∗ )[ξ1, ξ2] = jwww.gol.ei.tum.de Slide 22/22 | Block-Jacobi Methods with Newton-steps | Martin Kleinsteuber | October 30th, 2015