Ontology type: schema:ScholarlyArticle
2019-03-15
AUTHORSCédric Josz, Jean Bernard Lasserre, Bernard Mourrain
ABSTRACTWe show that the sparse polynomial interpolation problem reduces to a discrete super-resolution problem on the n-dimensional torus. Therefore, the semidefinite programming approach initiated by Candès and Fernandez-Granda (Commun. Pure Appl. Math. 67(6) 906–956, 2014) in the univariate case can be applied. We extend their result to the multivariate case, i.e., we show that exact recovery is guaranteed provided that a geometric spacing condition on the supports holds and evaluations are sufficiently many (but not many). It also turns out that the sparse recovery LP-formulation of ℓ1-norm minimization is also guaranteed to provide exact recovery provided that the evaluations are made in a certain manner and even though the restricted isometry property for exact recovery is not satisfied. (A naive sparse recovery LP approach does not offer such a guarantee.) Finally, we also describe the algebraic Prony method for sparse interpolation, which also recovers the exact decomposition but from less point evaluations and with no geometric spacing condition. We provide two sets of numerical experiments, one in which the super-resolution technique and Prony’s method seem to cope equally well with noise, and another in which the super-resolution technique seems to cope with noise better than Prony’s method, at the cost of an extra computational burden (i.e., a semidefinite optimization). More... »
PAGES1-37
http://scigraph.springernature.com/pub.10.1007/s10444-019-09672-2
DOIhttp://dx.doi.org/10.1007/s10444-019-09672-2
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1112775377
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": "Laboratory for Analysis and Architecture of Systems",
"id": "https://www.grid.ac/institutes/grid.462430.7",
"name": [
"LAAS-CNRS, 7 avenue du Colonel Roche, BP 54200, 31031, Toulouse C\u00e9dex 4, France"
],
"type": "Organization"
},
"familyName": "Josz",
"givenName": "C\u00e9dric",
"type": "Person"
},
{
"affiliation": {
"name": [
"LAAS-CNRS and Institute of Mathematics, 7 avenue du Colonel Roche, BP 54200, 31031, Toulouse C\u00e9dex 4, France"
],
"type": "Organization"
},
"familyName": "Lasserre",
"givenName": "Jean Bernard",
"type": "Person"
},
{
"affiliation": {
"alternateName": "French Institute for Research in Computer Science and Automation",
"id": "https://www.grid.ac/institutes/grid.5328.c",
"name": [
"Universit\u00e9 C\u00f4te d\u2019Azur, Inria, 2004 route des Lucioles, 06902, Sophia Antipolis, France"
],
"type": "Organization"
},
"familyName": "Mourrain",
"givenName": "Bernard",
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1016/j.laa.2015.10.023",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1000592834"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.crma.2008.03.014",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002389075"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/cpa.21455",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007862380"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2442829.2442852",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015567113"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10208-014-9228-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018150404",
"https://doi.org/10.1007/s10208-014-9228-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-51084-2_44",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1019811312",
"https://doi.org/10.1007/3-540-51084-2_44"
],
"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.1002/cpa.20124",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026640051"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/cpa.20124",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026640051"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1080/00036810903569499",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1028919232"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10107-013-0680-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029482687",
"https://doi.org/10.1007/s10107-013-0680-x"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-09519-5_73",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030416919",
"https://doi.org/10.1007/3-540-09519-5_73"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00041-013-9292-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033197525",
"https://doi.org/10.1007/s00041-013-9292-3"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1088/0266-5611/19/2/201",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033875454"
],
"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/2213977.2214029",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039665942"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00211-016-0844-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043346495",
"https://doi.org/10.1007/s00211-016-0844-8"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00211-016-0844-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043346495",
"https://doi.org/10.1007/s00211-016-0844-8"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.acha.2014.03.004",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047594799"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00013-009-0007-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051404760",
"https://doi.org/10.1007/s00013-009-0007-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00013-009-0007-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051404760",
"https://doi.org/10.1007/s00013-009-0007-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00013-009-0007-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051404760",
"https://doi.org/10.1007/s00013-009-0007-6"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.acha.2005.01.003",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052298732"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/29.32276",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061144455"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/78.143447",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061227994"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tit.1968.1054109",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061646428"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tit.1969.1054260",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061646572"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tit.2005.858979",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061650709"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tit.2006.885507",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061651193"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tit.2011.2161794",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061653441"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tit.2016.2619368",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061656092"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/0219073",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062842256"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/0302004",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062842516"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.19139/soic.v4i3.207",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1068763884"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.laa.2017.04.015",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1084820726"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10208-017-9372-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1092411221",
"https://doi.org/10.1007/s10208-017-9372-x"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.2174/97816080504821100101",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1109399006"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/17m1147822",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1111063557"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/17m1147822",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1111063557"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/17m1147822",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1111063557"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/17m1147822",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1111063557"
],
"type": "CreativeWork"
}
],
"datePublished": "2019-03-15",
"datePublishedReg": "2019-03-15",
"description": "We show that the sparse polynomial interpolation problem reduces to a discrete super-resolution problem on the n-dimensional torus. Therefore, the semidefinite programming approach initiated by Cand\u00e8s and Fernandez-Granda (Commun. Pure Appl. Math. 67(6) 906\u2013956, 2014) in the univariate case can be applied. We extend their result to the multivariate case, i.e., we show that exact recovery is guaranteed provided that a geometric spacing condition on the supports holds and evaluations are sufficiently many (but not many). It also turns out that the sparse recovery LP-formulation of \u21131-norm minimization is also guaranteed to provide exact recovery provided that the evaluations are made in a certain manner and even though the restricted isometry property for exact recovery is not satisfied. (A naive sparse recovery LP approach does not offer such a guarantee.) Finally, we also describe the algebraic Prony method for sparse interpolation, which also recovers the exact decomposition but from less point evaluations and with no geometric spacing condition. We provide two sets of numerical experiments, one in which the super-resolution technique and Prony\u2019s method seem to cope equally well with noise, and another in which the super-resolution technique seems to cope with noise better than Prony\u2019s method, at the cost of an extra computational burden (i.e., a semidefinite optimization).",
"genre": "research_article",
"id": "sg:pub.10.1007/s10444-019-09672-2",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isFundedItemOf": [
{
"id": "sg:grant.4273935",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1045108",
"issn": [
"1019-7168",
"1572-9044"
],
"name": "Advances in Computational Mathematics",
"type": "Periodical"
}
],
"name": "Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?",
"pagination": "1-37",
"productId": [
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"67a4b064113f8aaade0989bb25e9dfa44f8b2168f2d7eb3e4f767a9e966f91eb"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10444-019-09672-2"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1112775377"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10444-019-09672-2",
"https://app.dimensions.ai/details/publication/pub.1112775377"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T11:56",
"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/0000000359_0000000359/records_29215_00000004.jsonl",
"type": "ScholarlyArticle",
"url": "https://link.springer.com/10.1007%2Fs10444-019-09672-2"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/s10444-019-09672-2'
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/s10444-019-09672-2'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10444-019-09672-2'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10444-019-09672-2'
This table displays all metadata directly associated to this object as RDF triples.
186 TRIPLES
21 PREDICATES
59 URIs
16 LITERALS
5 BLANK NODES