Sparse Polynomial Interpolation by Variable Shift in the Presence of Noise and Outliers in the Evaluations View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Brice Boyer , Matthew T. Comer , Erich L. Kaltofen

ABSTRACT

We compute approximate sparse polynomial models of the form \(\widetilde{f}(x) = \sum _{j=1}^t \widetilde{c}_j (x - \widetilde{s})^{e_j}\) to a function \(f(x)\), of which an approximation of the evaluation \(f(\zeta )\) at any complex argument value \(\zeta \) can be obtained. We assume that several of the returned function evaluations \(f(\zeta )\) are perturbed not just by approximation/noise errors but also by highly perturbed outliers. None of the \(\widetilde{c}_j\), \(\widetilde{s}\), \(e_j\) and the location of the outliers are known beforehand. We use a numerical version of an exact algorithm by [4] together with a numerical version of the Reed–Solomon error correcting coding algorithm. We also compare with a simpler approach based on root finding of derivatives, while restricted to characteristic \(0\). In this preliminary report, we discuss how some of the problems of numerical instability and ill-conditioning in the arising optimization problems can be overcome. By way of experiments, we show that our techniques can recover approximate sparse shifted polynomial models, provided that there are few terms \(t\), few outliers and that the sparse shift is relatively small. More... »

PAGES

183-197

References to SciGraph publications

Book

TITLE

Computer Mathematics

ISBN

978-3-662-43798-8
978-3-662-43799-5

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-43799-5_16

DOI

http://dx.doi.org/10.1007/978-3-662-43799-5_16

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational 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": "North Carolina State University", 
          "id": "https://www.grid.ac/institutes/grid.40803.3f", 
          "name": [
            "Department of Mathematics, North Carolina State University, Raleigh, NC\u00a027695-8205, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Boyer", 
        "givenName": "Brice", 
        "id": "sg:person.014470544462.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014470544462.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "North Carolina State University", 
          "id": "https://www.grid.ac/institutes/grid.40803.3f", 
          "name": [
            "Department of Mathematics, North Carolina State University, Raleigh, NC\u00a027695-8205, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Comer", 
        "givenName": "Matthew T.", 
        "id": "sg:person.010730102700.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010730102700.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "North Carolina State University", 
          "id": "https://www.grid.ac/institutes/grid.40803.3f", 
          "name": [
            "Department of Mathematics, North Carolina State University, Raleigh, NC\u00a027695-8205, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kaltofen", 
        "givenName": "Erich L.", 
        "id": "sg:person.013117774373.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013117774373.47"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-1-4613-0261-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009025132", 
          "https://doi.org/10.1007/978-1-4613-0261-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4613-0261-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009025132", 
          "https://doi.org/10.1007/978-1-4613-0261-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1837934.1837985", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013834603"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s002000050004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015987695", 
          "https://doi.org/10.1007/s002000050004"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0747-7171(03)00087-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019050533"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0747-7171(03)00087-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019050533"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0747-7171(08)80018-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024811749"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/96877.96912", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026066276"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jsc.2008.11.003", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034521606"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/62212.62241", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037365455"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1993886.1993909", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048129065"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01293594", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050840454", 
          "https://doi.org/10.1007/bf01293594"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01293594", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050840454", 
          "https://doi.org/10.1007/bf01293594"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0747-7171(03)00088-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052663940"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0747-7171(03)00088-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052663940"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539792237784", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879769"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "We compute approximate sparse polynomial models of the form \\(\\widetilde{f}(x) = \\sum _{j=1}^t \\widetilde{c}_j (x - \\widetilde{s})^{e_j}\\) to a function \\(f(x)\\), of which an approximation of the evaluation \\(f(\\zeta )\\) at any complex argument value \\(\\zeta \\) can be obtained. We assume that several of the returned function evaluations \\(f(\\zeta )\\) are perturbed not just by approximation/noise errors but also by highly perturbed outliers. None of the \\(\\widetilde{c}_j\\), \\(\\widetilde{s}\\), \\(e_j\\) and the location of the outliers are known beforehand. We use a numerical version of an exact algorithm by [4] together with a numerical version of the Reed\u2013Solomon error correcting coding algorithm. We also compare with a simpler approach based on root finding of derivatives, while restricted to characteristic \\(0\\). In this preliminary report, we discuss how some of the problems of numerical instability and ill-conditioning in the arising optimization problems can be overcome. By way of experiments, we show that our techniques can recover approximate sparse shifted polynomial models, provided that there are few terms \\(t\\), few outliers and that the sparse shift is relatively small.", 
    "editor": [
      {
        "familyName": "Feng", 
        "givenName": "Ruyong", 
        "type": "Person"
      }, 
      {
        "familyName": "Lee", 
        "givenName": "Wen-shin", 
        "type": "Person"
      }, 
      {
        "familyName": "Sato", 
        "givenName": "Yosuke", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-43799-5_16", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3092619", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3126722", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-662-43798-8", 
        "978-3-662-43799-5"
      ], 
      "name": "Computer Mathematics", 
      "type": "Book"
    }, 
    "name": "Sparse Polynomial Interpolation by Variable Shift in the Presence of Noise and Outliers in the Evaluations", 
    "pagination": "183-197", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-43799-5_16"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e69024ad0284ac3e0ed459a121e9cb1c73ccb8311433674e9ed12f65ebbdfd5a"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048398624"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-43799-5_16", 
      "https://app.dimensions.ai/details/publication/pub.1048398624"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T00:51", 
    "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/0000000001_0000000264/records_8700_00000273.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-662-43799-5_16"
  }
]
 

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/978-3-662-43799-5_16'

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/978-3-662-43799-5_16'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-43799-5_16'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-43799-5_16'


 

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

132 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-43799-5_16 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N72c2144ffe134dfda48df9d9df343b56
4 schema:citation sg:pub.10.1007/978-1-4613-0261-2
5 sg:pub.10.1007/bf01293594
6 sg:pub.10.1007/s002000050004
7 https://doi.org/10.1016/j.jsc.2008.11.003
8 https://doi.org/10.1016/s0747-7171(03)00087-7
9 https://doi.org/10.1016/s0747-7171(03)00088-9
10 https://doi.org/10.1016/s0747-7171(08)80018-1
11 https://doi.org/10.1137/s0097539792237784
12 https://doi.org/10.1145/1837934.1837985
13 https://doi.org/10.1145/1993886.1993909
14 https://doi.org/10.1145/62212.62241
15 https://doi.org/10.1145/96877.96912
16 schema:datePublished 2014
17 schema:datePublishedReg 2014-01-01
18 schema:description We compute approximate sparse polynomial models of the form \(\widetilde{f}(x) = \sum _{j=1}^t \widetilde{c}_j (x - \widetilde{s})^{e_j}\) to a function \(f(x)\), of which an approximation of the evaluation \(f(\zeta )\) at any complex argument value \(\zeta \) can be obtained. We assume that several of the returned function evaluations \(f(\zeta )\) are perturbed not just by approximation/noise errors but also by highly perturbed outliers. None of the \(\widetilde{c}_j\), \(\widetilde{s}\), \(e_j\) and the location of the outliers are known beforehand. We use a numerical version of an exact algorithm by [4] together with a numerical version of the Reed–Solomon error correcting coding algorithm. We also compare with a simpler approach based on root finding of derivatives, while restricted to characteristic \(0\). In this preliminary report, we discuss how some of the problems of numerical instability and ill-conditioning in the arising optimization problems can be overcome. By way of experiments, we show that our techniques can recover approximate sparse shifted polynomial models, provided that there are few terms \(t\), few outliers and that the sparse shift is relatively small.
19 schema:editor Nf8e2bf9f097d41828f3105f1a4302186
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree true
23 schema:isPartOf Nac8cc942bf924125a88b0174e2d932bc
24 schema:name Sparse Polynomial Interpolation by Variable Shift in the Presence of Noise and Outliers in the Evaluations
25 schema:pagination 183-197
26 schema:productId N6583fb6e76714107b6267c0c3a4c9075
27 Nd3f6ddec970447b6864f98eccd708d3b
28 Nd46acf6fb0364b0688f86e23a25e059e
29 schema:publisher N28dde848f28c446d91954b8c4aebbfdf
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048398624
31 https://doi.org/10.1007/978-3-662-43799-5_16
32 schema:sdDatePublished 2019-04-16T00:51
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher Nc05bb8561734483bb015d0ff492eb52f
35 schema:url http://link.springer.com/10.1007/978-3-662-43799-5_16
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N28dde848f28c446d91954b8c4aebbfdf schema:location Berlin, Heidelberg
40 schema:name Springer Berlin Heidelberg
41 rdf:type schema:Organisation
42 N2a0a91b4a3d3440d818479061d4ebd5c schema:familyName Feng
43 schema:givenName Ruyong
44 rdf:type schema:Person
45 N37cb1835fe1040618c2570edb8a1aeb8 rdf:first N49e36b31c11e4ee682afd1e03fdad4d7
46 rdf:rest rdf:nil
47 N3af7c15d8d5c4e1c8a5bc8f9a0cd5c4f rdf:first Nc0fb6c9275bb4760bd9afd1c19020e4f
48 rdf:rest N37cb1835fe1040618c2570edb8a1aeb8
49 N49e36b31c11e4ee682afd1e03fdad4d7 schema:familyName Sato
50 schema:givenName Yosuke
51 rdf:type schema:Person
52 N6583fb6e76714107b6267c0c3a4c9075 schema:name dimensions_id
53 schema:value pub.1048398624
54 rdf:type schema:PropertyValue
55 N72c2144ffe134dfda48df9d9df343b56 rdf:first sg:person.014470544462.50
56 rdf:rest Nb3e95cb07c434cb993bc5563684bb06e
57 N97b7f2c906f3469e8fcecfbaf0661051 rdf:first sg:person.013117774373.47
58 rdf:rest rdf:nil
59 Nac8cc942bf924125a88b0174e2d932bc schema:isbn 978-3-662-43798-8
60 978-3-662-43799-5
61 schema:name Computer Mathematics
62 rdf:type schema:Book
63 Nb3e95cb07c434cb993bc5563684bb06e rdf:first sg:person.010730102700.79
64 rdf:rest N97b7f2c906f3469e8fcecfbaf0661051
65 Nc05bb8561734483bb015d0ff492eb52f schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 Nc0fb6c9275bb4760bd9afd1c19020e4f schema:familyName Lee
68 schema:givenName Wen-shin
69 rdf:type schema:Person
70 Nd3f6ddec970447b6864f98eccd708d3b schema:name doi
71 schema:value 10.1007/978-3-662-43799-5_16
72 rdf:type schema:PropertyValue
73 Nd46acf6fb0364b0688f86e23a25e059e schema:name readcube_id
74 schema:value e69024ad0284ac3e0ed459a121e9cb1c73ccb8311433674e9ed12f65ebbdfd5a
75 rdf:type schema:PropertyValue
76 Nf8e2bf9f097d41828f3105f1a4302186 rdf:first N2a0a91b4a3d3440d818479061d4ebd5c
77 rdf:rest N3af7c15d8d5c4e1c8a5bc8f9a0cd5c4f
78 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
79 schema:name Mathematical Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
82 schema:name Numerical and Computational Mathematics
83 rdf:type schema:DefinedTerm
84 sg:grant.3092619 http://pending.schema.org/fundedItem sg:pub.10.1007/978-3-662-43799-5_16
85 rdf:type schema:MonetaryGrant
86 sg:grant.3126722 http://pending.schema.org/fundedItem sg:pub.10.1007/978-3-662-43799-5_16
87 rdf:type schema:MonetaryGrant
88 sg:person.010730102700.79 schema:affiliation https://www.grid.ac/institutes/grid.40803.3f
89 schema:familyName Comer
90 schema:givenName Matthew T.
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010730102700.79
92 rdf:type schema:Person
93 sg:person.013117774373.47 schema:affiliation https://www.grid.ac/institutes/grid.40803.3f
94 schema:familyName Kaltofen
95 schema:givenName Erich L.
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013117774373.47
97 rdf:type schema:Person
98 sg:person.014470544462.50 schema:affiliation https://www.grid.ac/institutes/grid.40803.3f
99 schema:familyName Boyer
100 schema:givenName Brice
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014470544462.50
102 rdf:type schema:Person
103 sg:pub.10.1007/978-1-4613-0261-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009025132
104 https://doi.org/10.1007/978-1-4613-0261-2
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/bf01293594 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050840454
107 https://doi.org/10.1007/bf01293594
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/s002000050004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015987695
110 https://doi.org/10.1007/s002000050004
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/j.jsc.2008.11.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034521606
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/s0747-7171(03)00087-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019050533
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/s0747-7171(03)00088-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052663940
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1016/s0747-7171(08)80018-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024811749
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1137/s0097539792237784 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879769
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/1837934.1837985 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013834603
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/1993886.1993909 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048129065
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/62212.62241 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037365455
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/96877.96912 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026066276
129 rdf:type schema:CreativeWork
130 https://www.grid.ac/institutes/grid.40803.3f schema:alternateName North Carolina State University
131 schema:name Department of Mathematics, North Carolina State University, Raleigh, NC 27695-8205, USA
132 rdf:type schema:Organization
 




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


...