Optimal Dual Certificates for Noise Robustness Bounds in Compressive Sensing View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2015-11

AUTHORS

Marc Nicodème, Flavius Turcu, Charles Dossal

ABSTRACT

The paper deals with optimizing Lipschitz bounds relating locally the reconstruction error to the measurement error in the RIPless compressive sensing framework. Most recent theoretical papers in the field parametrize such bounds relative to certain families of vectors called dual certificates, which are fundamental to several reconstruction criteria. We show in the paper that such a family of bounds admits a unique minimizer that has a deep geometric meaning and can be explicitly constructed via a convex projection algorithm that we describe. We also give a faster greedy algorithm that provides approximate solutions. The algorithms are numerically illustrated and analyzed for different types of sensing matrices, such as random matrices or deterministic matrices issued from tomography and super-resolution. More... »

PAGES

251-263

References to SciGraph publications

  • 2015-10. Exact Support Recovery for Sparse Spikes Deconvolution in FOUNDATIONS OF COMPUTATIONAL MATHEMATICS
  • 2013-12. Super-Resolution from Noisy Data in JOURNAL OF FOURIER ANALYSIS AND APPLICATIONS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10851-015-0575-y

    DOI

    http://dx.doi.org/10.1007/s10851-015-0575-y

    DIMENSIONS

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


    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": "Institut de Math\u00e9matiques de Bordeaux", 
              "id": "https://www.grid.ac/institutes/grid.462496.b", 
              "name": [
                "IMS, Universit\u00e9 de Bordeaux, Talence, France", 
                "IMB, Universit\u00e9 de Bordeaux, Talence, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nicod\u00e8me", 
            "givenName": "Marc", 
            "id": "sg:person.012444162067.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012444162067.47"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Laboratoire de l'Integration du Materiau au Systeme", 
              "id": "https://www.grid.ac/institutes/grid.462974.a", 
              "name": [
                "IMS, Universit\u00e9 de Bordeaux, Talence, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Turcu", 
            "givenName": "Flavius", 
            "id": "sg:person.014141735732.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014141735732.43"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institut de Math\u00e9matiques de Bordeaux", 
              "id": "https://www.grid.ac/institutes/grid.462496.b", 
              "name": [
                "IMB, Universit\u00e9 de Bordeaux, Talence, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Dossal", 
            "givenName": "Charles", 
            "id": "sg:person.016043513033.79", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016043513033.79"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/j.crma.2011.12.014", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001116619"
            ], 
            "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.1109/tit.2006.871582", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007222025"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/cpa.21455", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007862380"
            ], 
            "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": "https://doi.org/10.1016/j.acha.2013.08.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022418491"
            ], 
            "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/20/5/005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037593251"
            ], 
            "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.1109/56.2083", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061189917"
            ], 
            "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.2005.858979", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061650709"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.2005.862083", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061650773"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.2005.864420", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061650802"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.2007.903129", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061651471"
            ], 
            "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/080714488", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062854422"
            ], 
            "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.1214/08-aos653", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064390227"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2015-11", 
        "datePublishedReg": "2015-11-01", 
        "description": "The paper deals with optimizing Lipschitz bounds relating locally the reconstruction error to the measurement error in the RIPless compressive sensing framework. Most recent theoretical papers in the field parametrize such bounds relative to certain families of vectors called dual certificates, which are fundamental to several reconstruction criteria. We show in the paper that such a family of bounds admits a unique minimizer that has a deep geometric meaning and can be explicitly constructed via a convex projection algorithm that we describe. We also give a faster greedy algorithm that provides approximate solutions. The algorithms are numerically illustrated and analyzed for different types of sensing matrices, such as random matrices or deterministic matrices issued from tomography and super-resolution.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s10851-015-0575-y", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1041815", 
            "issn": [
              "0924-9907", 
              "1573-7683"
            ], 
            "name": "Journal of Mathematical Imaging and Vision", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "53"
          }
        ], 
        "name": "Optimal Dual Certificates for Noise Robustness Bounds in Compressive Sensing", 
        "pagination": "251-263", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "9200febaf68dcc146315466ba0b2530234b8bffcade256832669020696aedff2"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10851-015-0575-y"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1030648142"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10851-015-0575-y", 
          "https://app.dimensions.ai/details/publication/pub.1030648142"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T17:32", 
        "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_8672_00000513.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs10851-015-0575-y"
      }
    ]
     

    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/s10851-015-0575-y'

    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/s10851-015-0575-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10851-015-0575-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10851-015-0575-y'


     

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

    138 TRIPLES      21 PREDICATES      46 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10851-015-0575-y schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 schema:author Ncf4bd3a4fe9545dbb12a785468dccad4
    4 schema:citation sg:pub.10.1007/s00041-013-9292-3
    5 sg:pub.10.1007/s10208-014-9228-6
    6 https://doi.org/10.1002/cpa.20350
    7 https://doi.org/10.1002/cpa.21455
    8 https://doi.org/10.1016/j.acha.2013.08.001
    9 https://doi.org/10.1016/j.crma.2008.03.014
    10 https://doi.org/10.1016/j.crma.2011.12.014
    11 https://doi.org/10.1088/0266-5611/20/5/005
    12 https://doi.org/10.1109/56.2083
    13 https://doi.org/10.1109/tit.2004.828141
    14 https://doi.org/10.1109/tit.2005.858979
    15 https://doi.org/10.1109/tit.2005.862083
    16 https://doi.org/10.1109/tit.2005.864420
    17 https://doi.org/10.1109/tit.2006.871582
    18 https://doi.org/10.1109/tit.2007.903129
    19 https://doi.org/10.1109/tit.2012.2233859
    20 https://doi.org/10.1137/080714488
    21 https://doi.org/10.1137/s1064827596304010
    22 https://doi.org/10.1214/08-aos653
    23 schema:datePublished 2015-11
    24 schema:datePublishedReg 2015-11-01
    25 schema:description The paper deals with optimizing Lipschitz bounds relating locally the reconstruction error to the measurement error in the RIPless compressive sensing framework. Most recent theoretical papers in the field parametrize such bounds relative to certain families of vectors called dual certificates, which are fundamental to several reconstruction criteria. We show in the paper that such a family of bounds admits a unique minimizer that has a deep geometric meaning and can be explicitly constructed via a convex projection algorithm that we describe. We also give a faster greedy algorithm that provides approximate solutions. The algorithms are numerically illustrated and analyzed for different types of sensing matrices, such as random matrices or deterministic matrices issued from tomography and super-resolution.
    26 schema:genre research_article
    27 schema:inLanguage en
    28 schema:isAccessibleForFree false
    29 schema:isPartOf N9e24bef3c08e401aa20704dea007c182
    30 Nf253525d584f4fcf87c49058ca845b30
    31 sg:journal.1041815
    32 schema:name Optimal Dual Certificates for Noise Robustness Bounds in Compressive Sensing
    33 schema:pagination 251-263
    34 schema:productId Nad6f775305d44ede8454a48aebaeb3ec
    35 Nc827a17bbb78437b9e848a5f0ce4b4fe
    36 Nd20adcb7b0bc45bba5068efcaba65a9c
    37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030648142
    38 https://doi.org/10.1007/s10851-015-0575-y
    39 schema:sdDatePublished 2019-04-10T17:32
    40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    41 schema:sdPublisher Necbbe938d64f4672a2ea5482c47c7340
    42 schema:url http://link.springer.com/10.1007%2Fs10851-015-0575-y
    43 sgo:license sg:explorer/license/
    44 sgo:sdDataset articles
    45 rdf:type schema:ScholarlyArticle
    46 N084cccd3f39e4d5d95acc6cdf01bbd3b rdf:first sg:person.016043513033.79
    47 rdf:rest rdf:nil
    48 N1d145406552a49ad9ab6c1c0d517f5cb rdf:first sg:person.014141735732.43
    49 rdf:rest N084cccd3f39e4d5d95acc6cdf01bbd3b
    50 N9e24bef3c08e401aa20704dea007c182 schema:volumeNumber 53
    51 rdf:type schema:PublicationVolume
    52 Nad6f775305d44ede8454a48aebaeb3ec schema:name readcube_id
    53 schema:value 9200febaf68dcc146315466ba0b2530234b8bffcade256832669020696aedff2
    54 rdf:type schema:PropertyValue
    55 Nc827a17bbb78437b9e848a5f0ce4b4fe schema:name doi
    56 schema:value 10.1007/s10851-015-0575-y
    57 rdf:type schema:PropertyValue
    58 Ncf4bd3a4fe9545dbb12a785468dccad4 rdf:first sg:person.012444162067.47
    59 rdf:rest N1d145406552a49ad9ab6c1c0d517f5cb
    60 Nd20adcb7b0bc45bba5068efcaba65a9c schema:name dimensions_id
    61 schema:value pub.1030648142
    62 rdf:type schema:PropertyValue
    63 Necbbe938d64f4672a2ea5482c47c7340 schema:name Springer Nature - SN SciGraph project
    64 rdf:type schema:Organization
    65 Nf253525d584f4fcf87c49058ca845b30 schema:issueNumber 3
    66 rdf:type schema:PublicationIssue
    67 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Mathematical Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Applied Mathematics
    72 rdf:type schema:DefinedTerm
    73 sg:journal.1041815 schema:issn 0924-9907
    74 1573-7683
    75 schema:name Journal of Mathematical Imaging and Vision
    76 rdf:type schema:Periodical
    77 sg:person.012444162067.47 schema:affiliation https://www.grid.ac/institutes/grid.462496.b
    78 schema:familyName Nicodème
    79 schema:givenName Marc
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012444162067.47
    81 rdf:type schema:Person
    82 sg:person.014141735732.43 schema:affiliation https://www.grid.ac/institutes/grid.462974.a
    83 schema:familyName Turcu
    84 schema:givenName Flavius
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014141735732.43
    86 rdf:type schema:Person
    87 sg:person.016043513033.79 schema:affiliation https://www.grid.ac/institutes/grid.462496.b
    88 schema:familyName Dossal
    89 schema:givenName Charles
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016043513033.79
    91 rdf:type schema:Person
    92 sg:pub.10.1007/s00041-013-9292-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033197525
    93 https://doi.org/10.1007/s00041-013-9292-3
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/s10208-014-9228-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018150404
    96 https://doi.org/10.1007/s10208-014-9228-6
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1002/cpa.20350 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053255083
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1002/cpa.21455 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007862380
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/j.acha.2013.08.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022418491
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/j.crma.2008.03.014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002389075
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/j.crma.2011.12.014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001116619
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1088/0266-5611/20/5/005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037593251
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1109/56.2083 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061189917
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1109/tit.2004.828141 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061650125
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1109/tit.2005.858979 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061650709
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1109/tit.2005.862083 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061650773
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1109/tit.2005.864420 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061650802
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1109/tit.2006.871582 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007222025
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1109/tit.2007.903129 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061651471
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1109/tit.2012.2233859 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061654241
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1137/080714488 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062854422
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1137/s1064827596304010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062884436
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1214/08-aos653 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064390227
    131 rdf:type schema:CreativeWork
    132 https://www.grid.ac/institutes/grid.462496.b schema:alternateName Institut de Mathématiques de Bordeaux
    133 schema:name IMB, Université de Bordeaux, Talence, France
    134 IMS, Université de Bordeaux, Talence, France
    135 rdf:type schema:Organization
    136 https://www.grid.ac/institutes/grid.462974.a schema:alternateName Laboratoire de l'Integration du Materiau au Systeme
    137 schema:name IMS, Université de Bordeaux, Talence, France
    138 rdf:type schema:Organization
     




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


    ...