Truncated Laurent expansions for the fast evaluation of thin plate splines View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1993-02

AUTHORS

M. J. D. Powell

ABSTRACT

Thin plate splines are highly useful for the approximation of functions of two variables, partly because they provide the interpolant to scattered function values that minimizes a 2-norm of second derivatives. On the other hand, they have the severe disadvantage that the explicit calculation of a thin plate spline approximation requires a log function to be evaluatedm times, wherem is the number of “r2logr2” terms that occur. Therefore we consider a recent technique that saves much work whenm is large by forming sets of terms, and then the total contribution to the thin plate spline from the terms of each set is estimated by a single truncated Laurent expansion. In order to apply this technique, one has to pick the sets, one has to generate the coefficients of the expansions, and one has to decide which expansions give enough accuracy when the value of the spline is required at a general point of ℓ2. Our answers to these questions are different from those that are given elsewhere, as we prefer to refine sets of terms recursively by splitting them into two rather than four subsets. Some theoretical properties and several numerical results of our method are presented. They show that the work to calculate all the Laurent coefficients is usuallyO(m logm), and then onlyO(logm) operations are needed to estimate the value of the thin plate spline at a typical point of ℓ2. Thus substantial gains over direct methods are achieved form⩾200. More... »

PAGES

99-120

References to SciGraph publications

  • 1993-02. Side-scan sonar image processing using thin plate splines and control point matching in NUMERICAL ALGORITHMS
  • 1990-09. Multivariate cardinal interpolation with radial-basis functions in CONSTRUCTIVE APPROXIMATION
  • 1977. Splines minimizing rotation-invariant semi-norms in Sobolev spaces in CONSTRUCTIVE THEORY OF FUNCTIONS OF SEVERAL VARIABLES
  • 1992. Tabulation of Thin Plate Splines on a Very Fine Two-Dimensional Grid in NUMERICAL METHODS IN APPROXIMATION THEORY, VOL. 9
  • Journal

    TITLE

    Numerical Algorithms

    ISSUE

    2

    VOLUME

    5

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf02212042

    DOI

    http://dx.doi.org/10.1007/bf02212042

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1045413075


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Cambridge", 
              "id": "https://www.grid.ac/institutes/grid.5335.0", 
              "name": [
                "Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, UK"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Powell", 
            "givenName": "M. J. D.", 
            "id": "sg:person.07731545105.07", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731545105.07"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0021-9991(87)90140-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003548487"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-0348-8619-2_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004562359", 
              "https://doi.org/10.1007/978-3-0348-8619-2_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-0348-8619-2_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004562359", 
              "https://doi.org/10.1007/978-3-0348-8619-2_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01890410", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024658569", 
              "https://doi.org/10.1007/bf01890410"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01890410", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024658569", 
              "https://doi.org/10.1007/bf01890410"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02212041", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029600981", 
              "https://doi.org/10.1007/bf02212041"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02212041", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029600981", 
              "https://doi.org/10.1007/bf02212041"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0898-1221(92)90167-g", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036018437"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0086566", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046059419", 
              "https://doi.org/10.1007/bfb0086566"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1993-02", 
        "datePublishedReg": "1993-02-01", 
        "description": "Thin plate splines are highly useful for the approximation of functions of two variables, partly because they provide the interpolant to scattered function values that minimizes a 2-norm of second derivatives. On the other hand, they have the severe disadvantage that the explicit calculation of a thin plate spline approximation requires a log function to be evaluatedm times, wherem is the number of \u201cr2logr2\u201d terms that occur. Therefore we consider a recent technique that saves much work whenm is large by forming sets of terms, and then the total contribution to the thin plate spline from the terms of each set is estimated by a single truncated Laurent expansion. In order to apply this technique, one has to pick the sets, one has to generate the coefficients of the expansions, and one has to decide which expansions give enough accuracy when the value of the spline is required at a general point of \u21132. Our answers to these questions are different from those that are given elsewhere, as we prefer to refine sets of terms recursively by splitting them into two rather than four subsets. Some theoretical properties and several numerical results of our method are presented. They show that the work to calculate all the Laurent coefficients is usuallyO(m logm), and then onlyO(logm) operations are needed to estimate the value of the thin plate spline at a typical point of \u21132. Thus substantial gains over direct methods are achieved form\u2a7e200.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf02212042", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1050467", 
            "issn": [
              "1017-1398", 
              "1572-9265"
            ], 
            "name": "Numerical Algorithms", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "5"
          }
        ], 
        "name": "Truncated Laurent expansions for the fast evaluation of thin plate splines", 
        "pagination": "99-120", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "d852b3c1dfdba13178ce22309a68b6cbac9b699bf533fd50d8d1bdee883debaf"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf02212042"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1045413075"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf02212042", 
          "https://app.dimensions.ai/details/publication/pub.1045413075"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T12:11", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000361_0000000361/records_53984_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2FBF02212042"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf02212042'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf02212042'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02212042'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02212042'


     

    This table displays all metadata directly associated to this object as RDF triples.

    83 TRIPLES      21 PREDICATES      33 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf02212042 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 schema:author Neb3d4cfce6fc4fcdb342d7560fe27c19
    4 schema:citation sg:pub.10.1007/978-3-0348-8619-2_13
    5 sg:pub.10.1007/bf01890410
    6 sg:pub.10.1007/bf02212041
    7 sg:pub.10.1007/bfb0086566
    8 https://doi.org/10.1016/0021-9991(87)90140-9
    9 https://doi.org/10.1016/0898-1221(92)90167-g
    10 schema:datePublished 1993-02
    11 schema:datePublishedReg 1993-02-01
    12 schema:description Thin plate splines are highly useful for the approximation of functions of two variables, partly because they provide the interpolant to scattered function values that minimizes a 2-norm of second derivatives. On the other hand, they have the severe disadvantage that the explicit calculation of a thin plate spline approximation requires a log function to be evaluatedm times, wherem is the number of “r2logr2” terms that occur. Therefore we consider a recent technique that saves much work whenm is large by forming sets of terms, and then the total contribution to the thin plate spline from the terms of each set is estimated by a single truncated Laurent expansion. In order to apply this technique, one has to pick the sets, one has to generate the coefficients of the expansions, and one has to decide which expansions give enough accuracy when the value of the spline is required at a general point of ℓ2. Our answers to these questions are different from those that are given elsewhere, as we prefer to refine sets of terms recursively by splitting them into two rather than four subsets. Some theoretical properties and several numerical results of our method are presented. They show that the work to calculate all the Laurent coefficients is usuallyO(m logm), and then onlyO(logm) operations are needed to estimate the value of the thin plate spline at a typical point of ℓ2. Thus substantial gains over direct methods are achieved form⩾200.
    13 schema:genre research_article
    14 schema:inLanguage en
    15 schema:isAccessibleForFree false
    16 schema:isPartOf N102e2c47fb004355add068a3da893242
    17 N3bf53be1ddae401fabdd6df62e6e865d
    18 sg:journal.1050467
    19 schema:name Truncated Laurent expansions for the fast evaluation of thin plate splines
    20 schema:pagination 99-120
    21 schema:productId N1de1f6defdb44d0b99e880540c21cdfa
    22 N21df4e2f7c6a425ba1fbb39973ef4d0f
    23 Nff58604f32b14d289a76118ec32d8c8a
    24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045413075
    25 https://doi.org/10.1007/bf02212042
    26 schema:sdDatePublished 2019-04-11T12:11
    27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    28 schema:sdPublisher N56a8eaa6a1f14ba682197a1ce13aca64
    29 schema:url http://link.springer.com/10.1007%2FBF02212042
    30 sgo:license sg:explorer/license/
    31 sgo:sdDataset articles
    32 rdf:type schema:ScholarlyArticle
    33 N102e2c47fb004355add068a3da893242 schema:issueNumber 2
    34 rdf:type schema:PublicationIssue
    35 N1de1f6defdb44d0b99e880540c21cdfa schema:name readcube_id
    36 schema:value d852b3c1dfdba13178ce22309a68b6cbac9b699bf533fd50d8d1bdee883debaf
    37 rdf:type schema:PropertyValue
    38 N21df4e2f7c6a425ba1fbb39973ef4d0f schema:name doi
    39 schema:value 10.1007/bf02212042
    40 rdf:type schema:PropertyValue
    41 N3bf53be1ddae401fabdd6df62e6e865d schema:volumeNumber 5
    42 rdf:type schema:PublicationVolume
    43 N56a8eaa6a1f14ba682197a1ce13aca64 schema:name Springer Nature - SN SciGraph project
    44 rdf:type schema:Organization
    45 Neb3d4cfce6fc4fcdb342d7560fe27c19 rdf:first sg:person.07731545105.07
    46 rdf:rest rdf:nil
    47 Nff58604f32b14d289a76118ec32d8c8a schema:name dimensions_id
    48 schema:value pub.1045413075
    49 rdf:type schema:PropertyValue
    50 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    51 schema:name Mathematical Sciences
    52 rdf:type schema:DefinedTerm
    53 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    54 schema:name Applied Mathematics
    55 rdf:type schema:DefinedTerm
    56 sg:journal.1050467 schema:issn 1017-1398
    57 1572-9265
    58 schema:name Numerical Algorithms
    59 rdf:type schema:Periodical
    60 sg:person.07731545105.07 schema:affiliation https://www.grid.ac/institutes/grid.5335.0
    61 schema:familyName Powell
    62 schema:givenName M. J. D.
    63 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731545105.07
    64 rdf:type schema:Person
    65 sg:pub.10.1007/978-3-0348-8619-2_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004562359
    66 https://doi.org/10.1007/978-3-0348-8619-2_13
    67 rdf:type schema:CreativeWork
    68 sg:pub.10.1007/bf01890410 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024658569
    69 https://doi.org/10.1007/bf01890410
    70 rdf:type schema:CreativeWork
    71 sg:pub.10.1007/bf02212041 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029600981
    72 https://doi.org/10.1007/bf02212041
    73 rdf:type schema:CreativeWork
    74 sg:pub.10.1007/bfb0086566 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046059419
    75 https://doi.org/10.1007/bfb0086566
    76 rdf:type schema:CreativeWork
    77 https://doi.org/10.1016/0021-9991(87)90140-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003548487
    78 rdf:type schema:CreativeWork
    79 https://doi.org/10.1016/0898-1221(92)90167-g schema:sameAs https://app.dimensions.ai/details/publication/pub.1036018437
    80 rdf:type schema:CreativeWork
    81 https://www.grid.ac/institutes/grid.5335.0 schema:alternateName University of Cambridge
    82 schema:name Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, UK
    83 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...