Exact Support Recovery for Sparse Spikes Deconvolution View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2015-10

AUTHORS

Vincent Duval, Gabriel Peyré

ABSTRACT

This paper studies sparse spikes deconvolution over the space of measures. We focus on the recovery properties of the support of the measure (i.e., the location of the Dirac masses) using total variation of measures (TV) regularization. This regularization is the natural extension of the ℓ1 norm of vectors to the setting of measures. We show that support identification is governed by a specific solution of the dual problem (a so-called dual certificate) having minimum L2 norm. Our main result shows that if this certificate is non-degenerate (see the definition below), when the signal-to-noise ratio is large enough TV regularization recovers the exact same number of Diracs. We show that both the locations and the amplitudes of these Diracs converge toward those of the input measure when the noise drops to zero. Moreover, the non-degeneracy of this certificate can be checked by computing a so-called vanishing derivative pre-certificate. This proxy can be computed in closed form by solving a linear system. Lastly, we draw connections between the support of the recovered measure on a continuous domain and on a discretized grid. We show that when the signal-to-noise level is large enough, and provided the aforementioned dual certificate is non-degenerate, the solution of the discretized problem is supported on pairs of Diracs which are neighbors of the Diracs of the input measure. This gives a precise description of the convergence of the solution of the discretized problem toward the solution of the continuous grid-free problem, as the grid size tends to zero. More... »

PAGES

1315-1355

References to SciGraph publications

  • 2013-12. Super-Resolution from Noisy Data in JOURNAL OF FOURIER ANALYSIS AND APPLICATIONS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10208-014-9228-6

    DOI

    http://dx.doi.org/10.1007/s10208-014-9228-6

    DIMENSIONS

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


    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": "French Institute for Research in Computer Science and Automation", 
              "id": "https://www.grid.ac/institutes/grid.5328.c", 
              "name": [
                "INRIA, Domaine de Voluceau, Rocquencourt, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Duval", 
            "givenName": "Vincent", 
            "id": "sg:person.012464515135.01", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012464515135.01"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "French National Centre for Scientific Research", 
              "id": "https://www.grid.ac/institutes/grid.4444.0", 
              "name": [
                "CNRS, CEREMADE, Universit\u00e9 Paris-Dauphine, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Peyr\u00e9", 
            "givenName": "Gabriel", 
            "id": "sg:person.010527176161.50", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010527176161.50"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1190/1.1441261", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003225384"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1190/1.1440378", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007414246"
            ], 
            "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.1016/j.jmaa.2012.05.011", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011113812"
            ], 
            "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/23/3/009", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036990724"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/0266-5611/23/3/009", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036990724"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/0266-5611/20/5/005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037593251"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.acha.2012.08.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047380109"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/cpa.20350", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053255083"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/cpa.20350", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053255083"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1051/cocv/2011205", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1056951899"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/2040-8978/14/8/083001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059179851"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/8.320744", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061233143"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/msp.2003.1203207", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061422055"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/msp.2007.914998", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061422957"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.2004.828141", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061650125"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.2012.2233859", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061654241"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0523074", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062848487"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0907087", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062855872"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/110838509", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062865067"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s1064827596304010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062884436"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/allerton.2011.6120177", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094748284"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2015-10", 
        "datePublishedReg": "2015-10-01", 
        "description": "This paper studies sparse spikes deconvolution over the space of measures. We focus on the recovery properties of the support of the measure (i.e., the location of the Dirac masses) using total variation of measures (TV) regularization. This regularization is the natural extension of the \u21131 norm of vectors to the setting of measures. We show that support identification is governed by a specific solution of the dual problem (a so-called dual certificate) having minimum L2 norm. Our main result shows that if this certificate is non-degenerate (see the definition below), when the signal-to-noise ratio is large enough TV regularization recovers the exact same number of Diracs. We show that both the locations and the amplitudes of these Diracs converge toward those of the input measure when the noise drops to zero. Moreover, the non-degeneracy of this certificate can be checked by computing a so-called vanishing derivative pre-certificate. This proxy can be computed in closed form by solving a linear system. Lastly, we draw connections between the support of the recovered measure on a continuous domain and on a discretized grid. We show that when the signal-to-noise level is large enough, and provided the aforementioned dual certificate is non-degenerate, the solution of the discretized problem is supported on pairs of Diracs which are neighbors of the Diracs of the input measure. This gives a precise description of the convergence of the solution of the discretized problem toward the solution of the continuous grid-free problem, as the grid size tends to zero.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s10208-014-9228-6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1046692", 
            "issn": [
              "1615-3375", 
              "1615-3383"
            ], 
            "name": "Foundations of Computational Mathematics", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "5", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "15"
          }
        ], 
        "name": "Exact Support Recovery for Sparse Spikes Deconvolution", 
        "pagination": "1315-1355", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "567af768cd07c40bc8abc1d0c64d4aff968b3a8f95100132a6987369a80bb63a"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10208-014-9228-6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1018150404"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10208-014-9228-6", 
          "https://app.dimensions.ai/details/publication/pub.1018150404"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T19:52", 
        "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_8681_00000487.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s10208-014-9228-6"
      }
    ]
     

    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/s10208-014-9228-6'

    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/s10208-014-9228-6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10208-014-9228-6'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10208-014-9228-6'


     

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

    135 TRIPLES      21 PREDICATES      48 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10208-014-9228-6 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author N58385b4d4be54dbf8d02e8154293da74
    4 schema:citation sg:pub.10.1007/s00041-013-9292-3
    5 https://doi.org/10.1002/cpa.20350
    6 https://doi.org/10.1002/cpa.21455
    7 https://doi.org/10.1016/j.acha.2012.08.003
    8 https://doi.org/10.1016/j.jmaa.2012.05.011
    9 https://doi.org/10.1051/cocv/2011205
    10 https://doi.org/10.1088/0266-5611/20/5/005
    11 https://doi.org/10.1088/0266-5611/23/3/009
    12 https://doi.org/10.1088/2040-8978/14/8/083001
    13 https://doi.org/10.1109/8.320744
    14 https://doi.org/10.1109/allerton.2011.6120177
    15 https://doi.org/10.1109/msp.2003.1203207
    16 https://doi.org/10.1109/msp.2007.914998
    17 https://doi.org/10.1109/tit.2004.828141
    18 https://doi.org/10.1109/tit.2012.2233859
    19 https://doi.org/10.1137/0523074
    20 https://doi.org/10.1137/0907087
    21 https://doi.org/10.1137/110838509
    22 https://doi.org/10.1137/s1064827596304010
    23 https://doi.org/10.1190/1.1440378
    24 https://doi.org/10.1190/1.1441261
    25 schema:datePublished 2015-10
    26 schema:datePublishedReg 2015-10-01
    27 schema:description This paper studies sparse spikes deconvolution over the space of measures. We focus on the recovery properties of the support of the measure (i.e., the location of the Dirac masses) using total variation of measures (TV) regularization. This regularization is the natural extension of the ℓ1 norm of vectors to the setting of measures. We show that support identification is governed by a specific solution of the dual problem (a so-called dual certificate) having minimum L2 norm. Our main result shows that if this certificate is non-degenerate (see the definition below), when the signal-to-noise ratio is large enough TV regularization recovers the exact same number of Diracs. We show that both the locations and the amplitudes of these Diracs converge toward those of the input measure when the noise drops to zero. Moreover, the non-degeneracy of this certificate can be checked by computing a so-called vanishing derivative pre-certificate. This proxy can be computed in closed form by solving a linear system. Lastly, we draw connections between the support of the recovered measure on a continuous domain and on a discretized grid. We show that when the signal-to-noise level is large enough, and provided the aforementioned dual certificate is non-degenerate, the solution of the discretized problem is supported on pairs of Diracs which are neighbors of the Diracs of the input measure. This gives a precise description of the convergence of the solution of the discretized problem toward the solution of the continuous grid-free problem, as the grid size tends to zero.
    28 schema:genre research_article
    29 schema:inLanguage en
    30 schema:isAccessibleForFree true
    31 schema:isPartOf N6ebfb567104b446ba5077e34b8a37393
    32 Nb5c86a355de04dcabd89b37bcce5fd28
    33 sg:journal.1046692
    34 schema:name Exact Support Recovery for Sparse Spikes Deconvolution
    35 schema:pagination 1315-1355
    36 schema:productId N2811835819574b6ba437b4888092939d
    37 N73c6246f66214a6ca42be0e7f67a0475
    38 Na6a9ed8a455449b392c32087e6be1122
    39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018150404
    40 https://doi.org/10.1007/s10208-014-9228-6
    41 schema:sdDatePublished 2019-04-10T19:52
    42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    43 schema:sdPublisher N626f31edb69e4db9b7012d32fa8adf29
    44 schema:url http://link.springer.com/10.1007/s10208-014-9228-6
    45 sgo:license sg:explorer/license/
    46 sgo:sdDataset articles
    47 rdf:type schema:ScholarlyArticle
    48 N2811835819574b6ba437b4888092939d schema:name dimensions_id
    49 schema:value pub.1018150404
    50 rdf:type schema:PropertyValue
    51 N58385b4d4be54dbf8d02e8154293da74 rdf:first sg:person.012464515135.01
    52 rdf:rest Ne4a5f21592444c51b846e51b7ab5bd12
    53 N626f31edb69e4db9b7012d32fa8adf29 schema:name Springer Nature - SN SciGraph project
    54 rdf:type schema:Organization
    55 N6ebfb567104b446ba5077e34b8a37393 schema:volumeNumber 15
    56 rdf:type schema:PublicationVolume
    57 N73c6246f66214a6ca42be0e7f67a0475 schema:name readcube_id
    58 schema:value 567af768cd07c40bc8abc1d0c64d4aff968b3a8f95100132a6987369a80bb63a
    59 rdf:type schema:PropertyValue
    60 Na6a9ed8a455449b392c32087e6be1122 schema:name doi
    61 schema:value 10.1007/s10208-014-9228-6
    62 rdf:type schema:PropertyValue
    63 Nb5c86a355de04dcabd89b37bcce5fd28 schema:issueNumber 5
    64 rdf:type schema:PublicationIssue
    65 Ne4a5f21592444c51b846e51b7ab5bd12 rdf:first sg:person.010527176161.50
    66 rdf:rest rdf:nil
    67 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Mathematical Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Numerical and Computational Mathematics
    72 rdf:type schema:DefinedTerm
    73 sg:journal.1046692 schema:issn 1615-3375
    74 1615-3383
    75 schema:name Foundations of Computational Mathematics
    76 rdf:type schema:Periodical
    77 sg:person.010527176161.50 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
    78 schema:familyName Peyré
    79 schema:givenName Gabriel
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010527176161.50
    81 rdf:type schema:Person
    82 sg:person.012464515135.01 schema:affiliation https://www.grid.ac/institutes/grid.5328.c
    83 schema:familyName Duval
    84 schema:givenName Vincent
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012464515135.01
    86 rdf:type schema:Person
    87 sg:pub.10.1007/s00041-013-9292-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033197525
    88 https://doi.org/10.1007/s00041-013-9292-3
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1002/cpa.20350 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053255083
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1002/cpa.21455 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007862380
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1016/j.acha.2012.08.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047380109
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1016/j.jmaa.2012.05.011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011113812
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1051/cocv/2011205 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056951899
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1088/0266-5611/20/5/005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037593251
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1088/0266-5611/23/3/009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036990724
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1088/2040-8978/14/8/083001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059179851
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1109/8.320744 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061233143
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1109/allerton.2011.6120177 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094748284
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1109/msp.2003.1203207 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061422055
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1109/msp.2007.914998 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061422957
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1109/tit.2004.828141 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061650125
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1109/tit.2012.2233859 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061654241
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1137/0523074 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848487
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1137/0907087 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062855872
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1137/110838509 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062865067
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1137/s1064827596304010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062884436
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1190/1.1440378 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007414246
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1190/1.1441261 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003225384
    129 rdf:type schema:CreativeWork
    130 https://www.grid.ac/institutes/grid.4444.0 schema:alternateName French National Centre for Scientific Research
    131 schema:name CNRS, CEREMADE, Université Paris-Dauphine, Paris, France
    132 rdf:type schema:Organization
    133 https://www.grid.ac/institutes/grid.5328.c schema:alternateName French Institute for Research in Computer Science and Automation
    134 schema:name INRIA, Domaine de Voluceau, Rocquencourt, France
    135 rdf:type schema:Organization
     




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


    ...