Horizontal Dimensionality Reduction and Iterated Frame Bundle Development

28/08/2013
Auteurs : Stefan Sommer
OAI : oai:www.see.asso.fr:2552:5084
DOI :

Résumé

Horizontal Dimensionality Reduction and Iterated Frame Bundle Development

Métriques

753
250
2.2 Mo
 application/pdf
bitcache://10643e0ee22f8956558cc387faad194679341701

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/5084</identifier><creators><creator><creatorName>Stefan Sommer</creatorName></creator></creators><titles>
            <title>Horizontal Dimensionality Reduction and Iterated Frame Bundle Development</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Tue 8 Oct 2013</date>
	    <date dateType="Updated">Mon 25 Jul 2016</date>
            <date dateType="Submitted">Fri 25 May 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">10643e0ee22f8956558cc387faad194679341701</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>9892</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Faculty of Science Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Stefan Sommer Department of Computer Science, University of Copenhagen August 30, 2013 Slide 1/14 Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 PGA: analysis relative to the data mean Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 PGA: analysis relative to the data mean data points on non-linear manifold Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 PGA: analysis relative to the data mean intrinsic mean µ Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 PGA: analysis relative to the data mean tangent space TµM Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 PGA: analysis relative to the data mean projection of data point to TµM Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 PGA: analysis relative to the data mean Euclidean PCA in tangent space Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 Dimensionality Reduction in Non-Linear Manifolds • Aim: Find subspaces with coordinates that approximate data in non-linear manifolds • Not learning non-linear subspaces from data in linear Euclidean spaces (ISOMAP, LLE, etc.) • Principal Geodesic Analysis (PGA, Fletcher et al., 2004) • finds geodesic subspaces - geodesics rays originating from a manifold mean µ ∈ M • the non-linear data space is linearized to TµM • Geodesic PCA (GPCA, Huckeman et al., 2010) • finds principal geodesics - geodesics minimizing residual distances that passes principal mean Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 2/14 PGA: analysis relative to the data mean What happens when µ is a poor zero- dimensional descrip- tor? Curvature Skews Centered Analysis Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 3/14 Bimodal distribution on S2 , var. 0.52 . Curvature Skews Centered Analysis Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 3/14 Bimodal distribution on S2 , var. 0.52 . −1.5 −1 −0.5 0 0.5 1 1.5 −1.5 −1 −0.5 0 0.5 1 1.5 PGA, est. var. 1.072 Curvature Skews Centered Analysis Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 3/14 Bimodal distribution on S2 , var. 0.52 . −1.5 −1 −0.5 0 0.5 1 1.5 −1.5 −1 −0.5 0 0.5 1 1.5 PGA, est. var. 1.072 −1.5 −1 −0.5 0 0.5 1 1.5 −1.5 −1 −0.5 0 0.5 1 1.5 HCA, est. var. 0.492 Curvature Skews Centered Analysis Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 3/14 Bimodal distribution on S2 , var. 0.52 . −1.5 −1 −0.5 0 0.5 1 1.5 −1.5 −1 −0.5 0 0.5 1 1.5 PGA, est. var. 1.072 −1.5 −1 −0.5 0 0.5 1 1.5 −1.5 −1 −0.5 0 0.5 1 1.5 HCA, est. var. 0.492 HCA - Horizontal Com- ponent Analysis HCA Properties • data-adapted coordinate system r : RD → M • preserves distances orthogonal to lower order components: x −y = dM(r(x),r(y)) x = (x1 ,...,xd ,0,...,0), y = (x1 ,...,xd ,0,...,0,y ˜d ,0,...,0), 1 ≤ ˜d < d • intrinsic interpretation of covariance: cov(Xd ,X ˜d ) = R2 Xd X ˜d p(Xd ,X ˜d )d(Xd ,X ˜d ) = γd γ˜d ±dM(µ,r(Xd ))dM(r(Xd ),r(X ˜d ))p(r(Xd ,X ˜d ))ds ˜d dsd • orthogonal coordinates/subspaces • coordinate-wise decorrelation with respect to curvature-adapted measure Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 4/14 HCA Properties • data-adapted coordinate system r : RD → M • preserves distances orthogonal to lower order components: x −y = dM(r(x),r(y)) x = (x1 ,...,xd ,0,...,0), y = (x1 ,...,xd ,0,...,0,y ˜d ,0,...,0), 1 ≤ ˜d < d • intrinsic interpretation of covariance: cov(Xd ,X ˜d ) = R2 Xd X ˜d p(Xd ,X ˜d )d(Xd ,X ˜d ) = γd γ˜d ±dM(µ,r(Xd ))dM(r(Xd ),r(X ˜d ))p(r(Xd ,X ˜d ))ds ˜d dsd • orthogonal coordinates/subspaces • coordinate-wise decorrelation with respect to curvature-adapted measure Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 4/14 HCA Properties • data-adapted coordinate system r : RD → M • preserves distances orthogonal to lower order components: x −y = dM(r(x),r(y)) x = (x1 ,...,xd ,0,...,0), y = (x1 ,...,xd ,0,...,0,y ˜d ,0,...,0), 1 ≤ ˜d < d • intrinsic interpretation of covariance: cov(Xd ,X ˜d ) = R2 Xd X ˜d p(Xd ,X ˜d )d(Xd ,X ˜d ) = γd γ˜d ±dM(µ,r(Xd ))dM(r(Xd ),r(X ˜d ))p(r(Xd ,X ˜d ))ds ˜d dsd • orthogonal coordinates/subspaces • coordinate-wise decorrelation with respect to curvature-adapted measure Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 4/14 HCA Properties • data-adapted coordinate system r : RD → M • preserves distances orthogonal to lower order components: x −y = dM(r(x),r(y)) x = (x1 ,...,xd ,0,...,0), y = (x1 ,...,xd ,0,...,0,y ˜d ,0,...,0), 1 ≤ ˜d < d • intrinsic interpretation of covariance: cov(Xd ,X ˜d ) = R2 Xd X ˜d p(Xd ,X ˜d )d(Xd ,X ˜d ) = γd γ˜d ±dM(µ,r(Xd ))dM(r(Xd ),r(X ˜d ))p(r(Xd ,X ˜d ))ds ˜d dsd • orthogonal coordinates/subspaces • coordinate-wise decorrelation with respect to curvature-adapted measure Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 4/14 HCA Properties • data-adapted coordinate system r : RD → M • preserves distances orthogonal to lower order components: x −y = dM(r(x),r(y)) x = (x1 ,...,xd ,0,...,0), y = (x1 ,...,xd ,0,...,0,y ˜d ,0,...,0), 1 ≤ ˜d < d • intrinsic interpretation of covariance: cov(Xd ,X ˜d ) = R2 Xd X ˜d p(Xd ,X ˜d )d(Xd ,X ˜d ) = γd γ˜d ±dM(µ,r(Xd ))dM(r(Xd ),r(X ˜d ))p(r(Xd ,X ˜d ))ds ˜d dsd • orthogonal coordinates/subspaces • coordinate-wise decorrelation with respect to curvature-adapted measure Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 4/14 HCA Properties • data-adapted coordinate system r : RD → M • preserves distances orthogonal to lower order components: x −y = dM(r(x),r(y)) x = (x1 ,...,xd ,0,...,0), y = (x1 ,...,xd ,0,...,0,y ˜d ,0,...,0), 1 ≤ ˜d < d • intrinsic interpretation of covariance: cov(Xd ,X ˜d ) = R2 Xd X ˜d p(Xd ,X ˜d )d(Xd ,X ˜d ) = γd γ˜d ±dM(µ,r(Xd ))dM(r(Xd ),r(X ˜d ))p(r(Xd ,X ˜d ))ds ˜d dsd • orthogonal coordinates/subspaces • coordinate-wise decorrelation with respect to curvature-adapted measure Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 4/14 HCA Properties • data-adapted coordinate system r : RD → M • preserves distances orthogonal to lower order components: x −y = dM(r(x),r(y)) x = (x1 ,...,xd ,0,...,0), y = (x1 ,...,xd ,0,...,0,y ˜d ,0,...,0), 1 ≤ ˜d < d • intrinsic interpretation of covariance: cov(Xd ,X ˜d ) = R2 Xd X ˜d p(Xd ,X ˜d )d(Xd ,X ˜d ) = γd γ˜d ±dM(µ,r(Xd ))dM(r(Xd ),r(X ˜d ))p(r(Xd ,X ˜d ))ds ˜d dsd • orthogonal coordinates/subspaces • coordinate-wise decorrelation with respect to curvature-adapted measure Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 4/14 The Frame Bundle • the manifold and frames (bases) for the tangent spaces TpM • F(M) consists of pairs (p,u), p ∈ M, u frame for TpM • curves in the horizontal part of F(M) correspond to curves in M and parallel transport of frames Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 5/14 The Frame Bundle • the manifold and frames (bases) for the tangent spaces TpM • F(M) consists of pairs (p,u), p ∈ M, u frame for TpM • curves in the horizontal part of F(M) correspond to curves in M and parallel transport of frames Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 5/14 The Frame Bundle • the manifold and frames (bases) for the tangent spaces TpM • F(M) consists of pairs (p,u), p ∈ M, u frame for TpM • curves in the horizontal part of F(M) correspond to curves in M and parallel transport of frames Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 5/14 The Frame Bundle • the manifold and frames (bases) for the tangent spaces TpM • F(M) consists of pairs (p,u), p ∈ M, u frame for TpM • curves in the horizontal part of F(M) correspond to curves in M and parallel transport of frames Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 5/14 The Frame Bundle • the manifold and frames (bases) for the tangent spaces TpM • F(M) consists of pairs (p,u), p ∈ M, u frame for TpM • curves in the horizontal part of F(M) correspond to curves in M and parallel transport of frames Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 5/14 The Frame Bundle • the manifold and frames (bases) for the tangent spaces TpM • F(M) consists of pairs (p,u), p ∈ M, u frame for TpM • curves in the horizontal part of F(M) correspond to curves in M and parallel transport of frames Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 5/14 The Subspaces: Iterated Development • manifolds in general provides no canonical generalization of affine subspaces • SDEs are defined in the frame bundle using development of curves wt = t 0 u−1 s ˙xsds , wt ∈ Rη i.e. pull-back to Euclidean space using parallel transported frames ut • iterated development constructs subspaces of dimension > 1 (geodesic, polynomial, etc.) • geodesic developments (multi-step Fermi coordinates) generalize geodesic subspaces Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 6/14 The Subspaces: Iterated Development • manifolds in general provides no canonical generalization of affine subspaces • SDEs are defined in the frame bundle using development of curves wt = t 0 u−1 s ˙xsds , wt ∈ Rη i.e. pull-back to Euclidean space using parallel transported frames ut • iterated development constructs subspaces of dimension > 1 (geodesic, polynomial, etc.) • geodesic developments (multi-step Fermi coordinates) generalize geodesic subspaces Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 6/14 The Subspaces: Iterated Development • manifolds in general provides no canonical generalization of affine subspaces • SDEs are defined in the frame bundle using development of curves wt = t 0 u−1 s ˙xsds , wt ∈ Rη i.e. pull-back to Euclidean space using parallel transported frames ut • iterated development constructs subspaces of dimension > 1 (geodesic, polynomial, etc.) • geodesic developments (multi-step Fermi coordinates) generalize geodesic subspaces Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 6/14 The Subspaces: Iterated Development • manifolds in general provides no canonical generalization of affine subspaces • SDEs are defined in the frame bundle using development of curves wt = t 0 u−1 s ˙xsds , wt ∈ Rη i.e. pull-back to Euclidean space using parallel transported frames ut • iterated development constructs subspaces of dimension > 1 (geodesic, polynomial, etc.) • geodesic developments (multi-step Fermi coordinates) generalize geodesic subspaces Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 6/14 The Subspaces: Iterated Development • manifolds in general provides no canonical generalization of affine subspaces • SDEs are defined in the frame bundle using development of curves wt = t 0 u−1 s ˙xsds , wt ∈ Rη i.e. pull-back to Euclidean space using parallel transported frames ut • iterated development constructs subspaces of dimension > 1 (geodesic, polynomial, etc.) • geodesic developments (multi-step Fermi coordinates) generalize geodesic subspaces Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 6/14 Iterated Development • V ⊂ Rη linear subspace, V = V1 ⊥ V2, η = dimM • f : V1 → F(M) smooth map (e.g. an immersion) • Df (v1 +tv2) development starting at f(v1) • vector fields W1 ,...,WdimV2 : V → V, columns of W • Euclidean integral curve ˙wt = W(wt )v2 • development Df,W (v1 +tv2) = (xt ,ut ) ∈ F(M) defined by ˙ut = ut ˙wt , xt = πF(M)(ut ) • immersion for small v = v1 +v2 if full V2 rank on W • Wi constant: geodesic development; Wi = Dei p polynomial submanifolds; etc. Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 7/14 Iterated Development • V ⊂ Rη linear subspace, V = V1 ⊥ V2, η = dimM • f : V1 → F(M) smooth map (e.g. an immersion) • Df (v1 +tv2) development starting at f(v1) • vector fields W1 ,...,WdimV2 : V → V, columns of W • Euclidean integral curve ˙wt = W(wt )v2 • development Df,W (v1 +tv2) = (xt ,ut ) ∈ F(M) defined by ˙ut = ut ˙wt , xt = πF(M)(ut ) • immersion for small v = v1 +v2 if full V2 rank on W • Wi constant: geodesic development; Wi = Dei p polynomial submanifolds; etc. Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 7/14 Iterated Development • V ⊂ Rη linear subspace, V = V1 ⊥ V2, η = dimM • f : V1 → F(M) smooth map (e.g. an immersion) • Df (v1 +tv2) development starting at f(v1) • vector fields W1 ,...,WdimV2 : V → V, columns of W • Euclidean integral curve ˙wt = W(wt )v2 • development Df,W (v1 +tv2) = (xt ,ut ) ∈ F(M) defined by ˙ut = ut ˙wt , xt = πF(M)(ut ) • immersion for small v = v1 +v2 if full V2 rank on W • Wi constant: geodesic development; Wi = Dei p polynomial submanifolds; etc. Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 7/14 Iterated Development • V ⊂ Rη linear subspace, V = V1 ⊥ V2, η = dimM • f : V1 → F(M) smooth map (e.g. an immersion) • Df (v1 +tv2) development starting at f(v1) • vector fields W1 ,...,WdimV2 : V → V, columns of W • Euclidean integral curve ˙wt = W(wt )v2 • development Df,W (v1 +tv2) = (xt ,ut ) ∈ F(M) defined by ˙ut = ut ˙wt , xt = πF(M)(ut ) • immersion for small v = v1 +v2 if full V2 rank on W • Wi constant: geodesic development; Wi = Dei p polynomial submanifolds; etc. Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 7/14 Iterated Development • V ⊂ Rη linear subspace, V = V1 ⊥ V2, η = dimM • f : V1 → F(M) smooth map (e.g. an immersion) • Df (v1 +tv2) development starting at f(v1) • vector fields W1 ,...,WdimV2 : V → V, columns of W • Euclidean integral curve ˙wt = W(wt )v2 • development Df,W (v1 +tv2) = (xt ,ut ) ∈ F(M) defined by ˙ut = ut ˙wt , xt = πF(M)(ut ) • immersion for small v = v1 +v2 if full V2 rank on W • Wi constant: geodesic development; Wi = Dei p polynomial submanifolds; etc. Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 7/14 Iterated Development • V ⊂ Rη linear subspace, V = V1 ⊥ V2, η = dimM • f : V1 → F(M) smooth map (e.g. an immersion) • Df (v1 +tv2) development starting at f(v1) • vector fields W1 ,...,WdimV2 : V → V, columns of W • Euclidean integral curve ˙wt = W(wt )v2 • development Df,W (v1 +tv2) = (xt ,ut ) ∈ F(M) defined by ˙ut = ut ˙wt , xt = πF(M)(ut ) • immersion for small v = v1 +v2 if full V2 rank on W • Wi constant: geodesic development; Wi = Dei p polynomial submanifolds; etc. Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 7/14 Iterated Development • V ⊂ Rη linear subspace, V = V1 ⊥ V2, η = dimM • f : V1 → F(M) smooth map (e.g. an immersion) • Df (v1 +tv2) development starting at f(v1) • vector fields W1 ,...,WdimV2 : V → V, columns of W • Euclidean integral curve ˙wt = W(wt )v2 • development Df,W (v1 +tv2) = (xt ,ut ) ∈ F(M) defined by ˙ut = ut ˙wt , xt = πF(M)(ut ) • immersion for small v = v1 +v2 if full V2 rank on W • Wi constant: geodesic development; Wi = Dei p polynomial submanifolds; etc. Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 7/14 Iterated Development • V ⊂ Rη linear subspace, V = V1 ⊥ V2, η = dimM • f : V1 → F(M) smooth map (e.g. an immersion) • Df (v1 +tv2) development starting at f(v1) • vector fields W1 ,...,WdimV2 : V → V, columns of W • Euclidean integral curve ˙wt = W(wt )v2 • development Df,W (v1 +tv2) = (xt ,ut ) ∈ F(M) defined by ˙ut = ut ˙wt , xt = πF(M)(ut ) • immersion for small v = v1 +v2 if full V2 rank on W • Wi constant: geodesic development; Wi = Dei p polynomial submanifolds; etc. Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 7/14 Horizontal Component Analysis • distances measured relative to lower order components • iterative definition of hd given hd−1: data points {xi} • curves: geodesics x hd t (xi ) passing points that are closest to xi on d −1st component hd−1 • projection: πhd (xi ) = argmint dM (x hd t (xi ),xi )2 • transport: derivatives ˙x hd 0 (xi ) connected in hd−1 by parallel transport • orthogonality: x hd t orthogonal to d −1 basis vectors transported horizontally in hd−1 • horizontal component hd : subspace containing curves x hd t (xi ) minimizing reshd−1 (hd ) = N ∑ i=1 dM (xi ,πhd (xi ))2 with d −1th coordinates fixed Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 8/14 Horizontal Component Analysis • distances measured relative to lower order components • iterative definition of hd given hd−1: data points {xi} • curves: geodesics x hd t (xi ) passing points that are closest to xi on d −1st component hd−1 • projection: πhd (xi ) = argmint dM (x hd t (xi ),xi )2 • transport: derivatives ˙x hd 0 (xi ) connected in hd−1 by parallel transport • orthogonality: x hd t orthogonal to d −1 basis vectors transported horizontally in hd−1 • horizontal component hd : subspace containing curves x hd t (xi ) minimizing reshd−1 (hd ) = N ∑ i=1 dM (xi ,πhd (xi ))2 with d −1th coordinates fixed Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 8/14 Horizontal Component Analysis • distances measured relative to lower order components • iterative definition of hd given hd−1: data points {xi} • curves: geodesics x hd t (xi ) passing points that are closest to xi on d −1st component hd−1 • projection: πhd (xi ) = argmint dM (x hd t (xi ),xi )2 • transport: derivatives ˙x hd 0 (xi ) connected in hd−1 by parallel transport • orthogonality: x hd t orthogonal to d −1 basis vectors transported horizontally in hd−1 • horizontal component hd : subspace containing curves x hd t (xi ) minimizing reshd−1 (hd ) = N ∑ i=1 dM (xi ,πhd (xi ))2 with d −1th coordinates fixed Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 8/14 Horizontal Component Analysis • distances measured relative to lower order components • iterative definition of hd given hd−1: data points {xi} • curves: geodesics x hd t (xi ) passing points that are closest to xi on d −1st component hd−1 • projection: πhd (xi ) = argmint dM (x hd t (xi ),xi )2 • transport: derivatives ˙x hd 0 (xi ) connected in hd−1 by parallel transport • orthogonality: x hd t orthogonal to d −1 basis vectors transported horizontally in hd−1 • horizontal component hd : subspace containing curves x hd t (xi ) minimizing reshd−1 (hd ) = N ∑ i=1 dM (xi ,πhd (xi ))2 with d −1th coordinates fixed Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 8/14 Horizontal Component Analysis • distances measured relative to lower order components • iterative definition of hd given hd−1: data points {xi} • curves: geodesics x hd t (xi ) passing points that are closest to xi on d −1st component hd−1 • projection: πhd (xi ) = argmint dM (x hd t (xi ),xi )2 • transport: derivatives ˙x hd 0 (xi ) connected in hd−1 by parallel transport • orthogonality: x hd t orthogonal to d −1 basis vectors transported horizontally in hd−1 • horizontal component hd : subspace containing curves x hd t (xi ) minimizing reshd−1 (hd ) = N ∑ i=1 dM (xi ,πhd (xi ))2 with d −1th coordinates fixed Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 8/14 Horizontal Component Analysis • distances measured relative to lower order components • iterative definition of hd given hd−1: data points {xi} • curves: geodesics x hd t (xi ) passing points that are closest to xi on d −1st component hd−1 • projection: πhd (xi ) = argmint dM (x hd t (xi ),xi )2 • transport: derivatives ˙x hd 0 (xi ) connected in hd−1 by parallel transport • orthogonality: x hd t orthogonal to d −1 basis vectors transported horizontally in hd−1 • horizontal component hd : subspace containing curves x hd t (xi ) minimizing reshd−1 (hd ) = N ∑ i=1 dM (xi ,πhd (xi ))2 with d −1th coordinates fixed Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 8/14 Horizontal Component Analysis • distances measured relative to lower order components • iterative definition of hd given hd−1: data points {xi} • curves: geodesics x hd t (xi ) passing points that are closest to xi on d −1st component hd−1 • projection: πhd (xi ) = argmint dM (x hd t (xi ),xi )2 • transport: derivatives ˙x hd 0 (xi ) connected in hd−1 by parallel transport • orthogonality: x hd t orthogonal to d −1 basis vectors transported horizontally in hd−1 • horizontal component hd : subspace containing curves x hd t (xi ) minimizing reshd−1 (hd ) = N ∑ i=1 dM (xi ,πhd (xi ))2 with d −1th coordinates fixed Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 8/14 Horizontal Component Analysis • distances measured relative to lower order components • iterative definition of hd given hd−1: data points {xi} • curves: geodesics x hd t (xi ) passing points that are closest to xi on d −1st component hd−1 • projection: πhd (xi ) = argmint dM (x hd t (xi ),xi )2 • transport: derivatives ˙x hd 0 (xi ) connected in hd−1 by parallel transport • orthogonality: x hd t orthogonal to d −1 basis vectors transported horizontally in hd−1 • horizontal component hd : subspace containing curves x hd t (xi ) minimizing reshd−1 (hd ) = N ∑ i=1 dM (xi ,πhd (xi ))2 with d −1th coordinates fixed Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 8/14 Horizontal Component Analysis • distances measured relative to lower order components • iterative definition of hd given hd−1: data points {xi} • curves: geodesics x hd t (xi ) passing points that are closest to xi on d −1st component hd−1 • projection: πhd (xi ) = argmint dM (x hd t (xi ),xi )2 • transport: derivatives ˙x hd 0 (xi ) connected in hd−1 by parallel transport • orthogonality: x hd t orthogonal to d −1 basis vectors transported horizontally in hd−1 • horizontal component hd : subspace containing curves x hd t (xi ) minimizing reshd−1 (hd ) = N ∑ i=1 dM (xi ,πhd (xi ))2 with d −1th coordinates fixed Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 8/14 1 find geodesic h1 with d dt h1|t=0 = u1 that 1 minimizes res(h1) = ∑N i=1 dM (xi ,πh1 (xi ))2 2 find u2 ⊥ u1 such that x h2 t (xi) are geodesics • that pass πh1 (xi ) • with derivatives ˙x h2 0 (xi ) equal trans. Ph1 u2 • that minimize resh1 (h2) = ∑N i=1 dM (xi ,πh2 (xi ))2 3 find u3 ⊥ {u1,u2} such that x h3 t (xi) are geodesics • that pass πh2 (xi ) • with derivatives ˙x h3 0 (xi ) par. transp. in h2 • that minimize resh2 (h3) = ∑N i=1 dM (xi ,πh3 (xi ))2 4 and so on . . . Parallel Transport and Local Analysis Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 9/14 Sample on S2 , horz.: uniform, vert.: normal −3 −2 −1 0 1 2 3 −3 −2 −1 0 1 2 3 PGA −3 −2 −1 0 1 2 3 −3 −2 −1 0 1 2 3 HCA Parallel trans- port along first component: Conditional Congruency • data/geometry congruency: data can be approximated by geodesics (Huckemann et al.) • one-dimensional concept • conditional congruency: X ˜d |X1 ,...,Xd is congruent • HCA defines a data-adapted coordinate system that provides a conditionally congruent splitting Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 10/14 Conditional Congruency • data/geometry congruency: data can be approximated by geodesics (Huckemann et al.) • one-dimensional concept • conditional congruency: X ˜d |X1 ,...,Xd is congruent • HCA defines a data-adapted coordinate system that provides a conditionally congruent splitting Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 10/14 Conditional Congruency • data/geometry congruency: data can be approximated by geodesics (Huckemann et al.) • one-dimensional concept • conditional congruency: X ˜d |X1 ,...,Xd is congruent • HCA defines a data-adapted coordinate system that provides a conditionally congruent splitting Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 10/14 Conditional Congruency • data/geometry congruency: data can be approximated by geodesics (Huckemann et al.) • one-dimensional concept • conditional congruency: X ˜d |X1 ,...,Xd is congruent • HCA defines a data-adapted coordinate system that provides a conditionally congruent splitting Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 10/14 Components May Flip Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 11/14 x2 x3 x4 (p) x1 = 0 slice x4 x3 x1 (q) x2 = 0 slice −1 0 1 −1.5 −1 −0.5 0 0.5 1 1.5 −1.5 −1 −0.5 0 0.5 1 1.5 x3 x 2 x1 (r) HCA visualization Figure: 3-dim manifold 2x2 1 −2x2 2 +x2 3 +x2 4 = 1 in R4 with samples from two Gaussians with largest variance in the x2 direction (0.62 vs. 0.42 ). (a,b) Slices x1 = 0 and x2 = 0. (c) The second HCA horizontal component has largest x2 component (blue vector) whereas the second PGA component has largest x1 component (red vector). Corpora Callosa Corpus callosum variation: 3σ1 along h1, 3σ2 along h2 Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 12/14 Corpora Callosa Corpus callosum variation: 3σ1 along h1, 3σ2 along h2 (Loading corporacallosa.mp4) Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 12/14 Summary • Horizontal Component Analysis performs PCA-like dimensionality reduction in Riemannian manifolds • subspaces constructed from iterated frame bundle development • the implied coordinate system • is data adapted • preserves certain pairwise-distances and orthogonality • provides covariance interpretation • decorrelates curvature-adapted measure • provides conditionally congruent components • handles multi-modal distribution with spread over large-curvature areas Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 13/14 References - Sommer: Horizontal Dimensionality Reduction and Iterated Frame Bundle Development, GSI 2013. - Sommer et al.: Optimization over Geodesics for Exact Principal Geodesic Analysis, ACOM, in press. - Sommer et al.: Manifold Valued Statistics, Exact Principal Geodesic Analysis and the Effect of Linear Approximations, ECCV 2010. http://github.com/nefan/smanifold Stefan Sommer (sommer@diku.dk) (Department of Computer Science, University of Copenhagen) — Horizontal Dimensionality Reduction and Iterated Frame Bundle Development Slide 14/14