Discrete curve fitting on manifolds

28/08/2013
OAI : oai:www.see.asso.fr:2552:5120
DOI : You do not have permission to access embedded form.

Résumé

Discrete curve fitting on manifolds

Métriques

66
8
521.32 Ko
 application/pdf
bitcache://a0233cf34d4513dd1c3f5b89cb36eb51a4ae533c

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/5120</identifier><creators><creator><creatorName>Pierre-Antoine Absil</creatorName></creator><creator><creatorName>Nicolas Boumal</creatorName></creator></creators><titles>
            <title>Discrete curve fitting on manifolds</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Tue 15 Oct 2013</date>
	    <date dateType="Updated">Mon 25 Jul 2016</date>
            <date dateType="Submitted">Sat 24 Feb 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">a0233cf34d4513dd1c3f5b89cb36eb51a4ae533c</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>25097</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Discrete curve fitting on manifolds Nicolas Boumal joint work with Pierre-Antoine Absil Universit´e catholique de Louvain August 2013 Motivation: interpolation on SO(3) 2 Motivation: interpolation on SO(3) 2 Motivation: interpolation on SO(3) 2 Motivation: interpolation on SO(3) 2 Motivation: interpolation on SO(3) 2 The regression problem in R2 A balance between fitting and smoothness 3 The regression problem in R2 A balance between fitting and smoothness p1 p2 p3 p4 Each data point pi corresponds to a fixed time ti. 3 The regression problem in R2 A balance between fitting and smoothness p1 p2 p3 p4 3 The regression problem in R2 A balance between fitting and smoothness p1 p2 p3 p4 3 The regression problem in R2 A balance between fitting and smoothness p1 p2 p3 p4 3 The regression problem in R2 A balance between fitting and smoothness p1 p2 p3 p4 Regression is about denoising and filling the gaps. 3 The regression problem in R2 can be seen as an optimization problem Minimize: ˆE(γ) = Penalty on misfit N i=1 pi − γ(ti) 2 +λ Penalty on velocity tN t1 ˙γ(t) 2 dt + µ Penalty on acceleration tN t1 ¨γ(t) 2 dt λ and µ (≥ 0) balance fitting VS smoothness. Minimize over some curve space ˆΓ: dim ˆΓ may be infinite. 4 We discretize the curves γ hence reverting to finite dimensional optimization p1 p2 p3 p4 5 We discretize the curves γ hence reverting to finite dimensional optimization p1 p2 p3 p4 γi γi+1 γi−1 γ1 γNd Each point γi corresponds to a fixed time τi Γ = Rn × · · · × Rn ≡ RNd×n 6 We thus need a new objective E defined over the new curve space Γ E(γ) = N i=1 pi − γ(ti) 2 ⇓ N i=1 pi − γsi 2 +λ tN t1 ˙γ(t) 2 dt ⇓ Nd i=1 αi vi 2 +µ tN t1 ¨γ(t) 2 dt ⇓ Nd i=1 βi ai 2 7 What if the data lies on a manifold? Manifolds are smoothly “curved” spaces. Simple toy example: the sphere S2 in R3 More exciting manifolds discussed in this work: Pn + and SO(n). 8 The regression problem on S2 9 The regression problem on S2 9 The regression problem on S2 9 The regression problem on S2 9 The regression problem on S2 9 The regression problem on S2 9 We need a few concepts from Riemannian geometry to define discrete regression on S2 Redefine E over Γ = S2 × · · · × S2: E(γ) = N i=1 pi − γsi 2 +λ Nd i=1 αi vi 2 + µ Nd i=1 βi ai 2 10 We need a few concepts from Riemannian geometry to define discrete regression on S2 Redefine E over Γ = S2 × · · · × S2: E(γ) = N i=1 pi − γsi 2 ⇓ N i=1 dist2 (pi, γsi ) +λ Nd i=1 αi vi 2 + µ Nd i=1 βi ai 2 10 We need a few concepts from Riemannian geometry to define discrete regression on S2 Redefine E over Γ = S2 × · · · × S2: E(γ) = N i=1 pi − γsi 2 ⇓ N i=1 dist2 (pi, γsi ) +λ Nd i=1 αi vi 2 + µ Nd i=1 βi ai 2 11 Finite differences are linear combinations but S2 is not a vector space :( The linear combination ai = γi+1 − 2γi + γi−1 ∆τ2 12 Finite differences are linear combinations but S2 is not a vector space :( The linear combination ai = γi+1 − 2γi + γi−1 ∆τ2 can be rewritten like this: ai = (γi+1 − γi) + (γi−1 − γi) ∆τ2 . 12 Finite differences are linear combinations but S2 is not a vector space :( The linear combination ai = γi+1 − 2γi + γi−1 ∆τ2 can be rewritten like this: ai = (γi+1 − γi) + (γi−1 − γi) ∆τ2 . Now, we can interpret the terms: γi+1 − γi is a vector rooted at γi and pointing toward γi+1 12 Logarithms on manifolds generalize differences We use them to define geometric finite differences Loga (b) is a vector rooted at a, in the tangent space to S2 at a, pointing toward b. Furthermore, Loga (b) = dist (a, b). 13 Logarithms on manifolds generalize differences We use them to define geometric finite differences Loga (b) is a vector rooted at a, in the tangent space to S2 at a, pointing toward b. Furthermore, Loga (b) = dist (a, b). b − a is replaced by Loga (b) Hence: vi = Logγi (γi+1) ∆τ ai = Logγi (γi+1) + Logγi (γi−1) ∆τ2 13 We now have a proper objective for manifolds E(γ) = Penalty on misfit N i=1 dist2 (pi, γsi ) +λ Penalty on velocity Nd−1 i=1 αi Logγi (γi+1) ∆τ 2 + µ Nd−1 i=2 βi Logγi (γi+1) + Logγi (γi−1) ∆τ2 2 Penalty on acceleration Minimize over Γ = S2 × · · · × S2, a finite dimensional manifold. The constraint γ ∈ Γ is tough for standard software. 14 To minimize E, we use Manopt A Matlab toolbox for optimization on manifolds Manopt is a user-friendly, documented package which gives access to 1 A large collection of manifold descriptions; 2 A number of solvers (including Riemannian trust-regions); 3 And helper tools to get things right. It is available at www.manopt.org. 15 In a nutshell 1 We defined the discrete regression problem in Rn; 16 In a nutshell 1 We defined the discrete regression problem in Rn; 2 Then generalized it to manifolds as an optimization problem on Γ; 16 In a nutshell 1 We defined the discrete regression problem in Rn; 2 Then generalized it to manifolds as an optimization problem on Γ; 3 And we feed it to Manopt. 16 Example of convergence on S2 with geometric non-linear CG and iterative refinement 17 Example of convergence on S2 with geometric non-linear CG and iterative refinement 18 It works well, but the manifold has to be “gentle” You need to compute the logarithmic map and its derivatives. . . Second order methods seem to help, but they require more work. . . . and that may not always be possible. If your manifold is not nice enough, perhaps you can make do with an approximate log map? 19