Lipschitz embeddings of random sequences View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2014-08

AUTHORS

Riddhipratim Basu, Allan Sly

ABSTRACT

We develop a new multi-scale framework flexible enough to solve a number of problems involving embedding random sequences into random sequences. Grimmett et al. (Random Str Algorithm 37(1):85–99, 2010) asked whether there exists an increasing M-Lipschitz embedding from one i.i.d. Bernoulli sequence into an independent copy with positive probability. We give a positive answer for large enough M. A closely related problem is to show that two independent Poisson processes on R are roughly isometric (or quasi-isometric). Our approach also applies in this case answering a conjecture of Szegedy and of Peled (Ann Appl Probab 20:462–494, 2010). Our theorem also gives a new proof to Winkler’s compatible sequences problem. Our approach does not explicitly depend on the particular geometry of the problems and we believe it will be applicable to a range of multi-scale and random embedding problems. More... »

PAGES

721-775

References to SciGraph publications

  • 2000-08. Dependent percolation in two dimensions in PROBABILITY THEORY AND RELATED FIELDS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00440-013-0519-7

    DOI

    http://dx.doi.org/10.1007/s00440-013-0519-7

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure 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 California, Berkeley", 
              "id": "https://www.grid.ac/institutes/grid.47840.3f", 
              "name": [
                "Department of Statistics, University of California, Berkeley, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Basu", 
            "givenName": "Riddhipratim", 
            "id": "sg:person.010345577447.82", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010345577447.82"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of California, Berkeley", 
              "id": "https://www.grid.ac/institutes/grid.47840.3f", 
              "name": [
                "Department of Statistics, University of California, Berkeley, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sly", 
            "givenName": "Allan", 
            "id": "sg:person.015324560743.66", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015324560743.66"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1002/rsa.20368", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004468934"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00008732", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008559166", 
              "https://doi.org/10.1007/pl00008732"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1515/9781400881550-016", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017088614"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/cpa.21486", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017316975"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0963548304006340", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017411398"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/rsa.20551", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018094785"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9781139107174.018", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019469559"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/ejp.v6-77", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025303499"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/rsa.20312", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027107299"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/rsa.20312", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027107299"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/(sici)1098-2418(200001)16:1<58::aid-rsa5>3.0.co;2-e", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029297237"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0406029", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062844776"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/09-aap624", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064390607"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/10-aihp403", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064391269"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/10-aop615", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064391469"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/ecp.v15-1521", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064396016"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/ejp.v15-804", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064396782"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/ejp.v3-32", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064397379"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/aop/1176988173", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064403483"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1239/jap/1324046024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064442596"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2969/jmsj/03730391", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1070931278"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2014-08", 
        "datePublishedReg": "2014-08-01", 
        "description": "We develop a new multi-scale framework flexible enough to solve a number of problems involving embedding random sequences into random sequences. Grimmett et al. (Random Str Algorithm 37(1):85\u201399, 2010) asked whether there exists an increasing M-Lipschitz embedding from one i.i.d. Bernoulli sequence into an independent copy with positive probability. We give a positive answer for large enough M. A closely related problem is to show that two independent Poisson processes on R are roughly isometric (or quasi-isometric). Our approach also applies in this case answering a conjecture of Szegedy and of Peled (Ann Appl Probab 20:462\u2013494, 2010). Our theorem also gives a new proof to Winkler\u2019s compatible sequences problem. Our approach does not explicitly depend on the particular geometry of the problems and we believe it will be applicable to a range of multi-scale and random embedding problems.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00440-013-0519-7", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1053886", 
            "issn": [
              "0178-8051", 
              "1432-2064"
            ], 
            "name": "Probability Theory and Related Fields", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3-4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "159"
          }
        ], 
        "name": "Lipschitz embeddings of random sequences", 
        "pagination": "721-775", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "1d577ce407149545ab5cf714f5a710a9559a00dafc36c64cdb45e18bd8750702"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00440-013-0519-7"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1006159664"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00440-013-0519-7", 
          "https://app.dimensions.ai/details/publication/pub.1006159664"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T09:50", 
        "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/0000000347_0000000347/records_89786_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00440-013-0519-7"
      }
    ]
     

    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/s00440-013-0519-7'

    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/s00440-013-0519-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00440-013-0519-7'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00440-013-0519-7'


     

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

    129 TRIPLES      21 PREDICATES      47 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00440-013-0519-7 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nb2e5bb3b7dda4c4795336df348d977e4
    4 schema:citation sg:pub.10.1007/pl00008732
    5 https://doi.org/10.1002/(sici)1098-2418(200001)16:1<58::aid-rsa5>3.0.co;2-e
    6 https://doi.org/10.1002/cpa.21486
    7 https://doi.org/10.1002/rsa.20312
    8 https://doi.org/10.1002/rsa.20368
    9 https://doi.org/10.1002/rsa.20551
    10 https://doi.org/10.1017/cbo9781139107174.018
    11 https://doi.org/10.1017/s0963548304006340
    12 https://doi.org/10.1137/0406029
    13 https://doi.org/10.1214/09-aap624
    14 https://doi.org/10.1214/10-aihp403
    15 https://doi.org/10.1214/10-aop615
    16 https://doi.org/10.1214/aop/1176988173
    17 https://doi.org/10.1214/ecp.v15-1521
    18 https://doi.org/10.1214/ejp.v15-804
    19 https://doi.org/10.1214/ejp.v3-32
    20 https://doi.org/10.1214/ejp.v6-77
    21 https://doi.org/10.1239/jap/1324046024
    22 https://doi.org/10.1515/9781400881550-016
    23 https://doi.org/10.2969/jmsj/03730391
    24 schema:datePublished 2014-08
    25 schema:datePublishedReg 2014-08-01
    26 schema:description We develop a new multi-scale framework flexible enough to solve a number of problems involving embedding random sequences into random sequences. Grimmett et al. (Random Str Algorithm 37(1):85–99, 2010) asked whether there exists an increasing M-Lipschitz embedding from one i.i.d. Bernoulli sequence into an independent copy with positive probability. We give a positive answer for large enough M. A closely related problem is to show that two independent Poisson processes on R are roughly isometric (or quasi-isometric). Our approach also applies in this case answering a conjecture of Szegedy and of Peled (Ann Appl Probab 20:462–494, 2010). Our theorem also gives a new proof to Winkler’s compatible sequences problem. Our approach does not explicitly depend on the particular geometry of the problems and we believe it will be applicable to a range of multi-scale and random embedding problems.
    27 schema:genre research_article
    28 schema:inLanguage en
    29 schema:isAccessibleForFree false
    30 schema:isPartOf N3cb12bc831bd49d685d285ea8c2528f8
    31 N4956c03b77d94083b25cd79f2163d178
    32 sg:journal.1053886
    33 schema:name Lipschitz embeddings of random sequences
    34 schema:pagination 721-775
    35 schema:productId N23c71e18d6294eb9b61dd117bfcdeb5e
    36 N81dcf987e536420481784e6878c3ae13
    37 Nd9737e3e78284407a95e213736c534a7
    38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006159664
    39 https://doi.org/10.1007/s00440-013-0519-7
    40 schema:sdDatePublished 2019-04-11T09:50
    41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    42 schema:sdPublisher Nd0b1d72770374b78ac6a54aef2db654b
    43 schema:url https://link.springer.com/10.1007%2Fs00440-013-0519-7
    44 sgo:license sg:explorer/license/
    45 sgo:sdDataset articles
    46 rdf:type schema:ScholarlyArticle
    47 N23c71e18d6294eb9b61dd117bfcdeb5e schema:name readcube_id
    48 schema:value 1d577ce407149545ab5cf714f5a710a9559a00dafc36c64cdb45e18bd8750702
    49 rdf:type schema:PropertyValue
    50 N3cb12bc831bd49d685d285ea8c2528f8 schema:issueNumber 3-4
    51 rdf:type schema:PublicationIssue
    52 N4956c03b77d94083b25cd79f2163d178 schema:volumeNumber 159
    53 rdf:type schema:PublicationVolume
    54 N81dcf987e536420481784e6878c3ae13 schema:name doi
    55 schema:value 10.1007/s00440-013-0519-7
    56 rdf:type schema:PropertyValue
    57 Nb2e5bb3b7dda4c4795336df348d977e4 rdf:first sg:person.010345577447.82
    58 rdf:rest Nc6476cb82c2f46e2a5a0d62373a3eb2e
    59 Nc6476cb82c2f46e2a5a0d62373a3eb2e rdf:first sg:person.015324560743.66
    60 rdf:rest rdf:nil
    61 Nd0b1d72770374b78ac6a54aef2db654b schema:name Springer Nature - SN SciGraph project
    62 rdf:type schema:Organization
    63 Nd9737e3e78284407a95e213736c534a7 schema:name dimensions_id
    64 schema:value pub.1006159664
    65 rdf:type schema:PropertyValue
    66 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Mathematical Sciences
    68 rdf:type schema:DefinedTerm
    69 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Pure Mathematics
    71 rdf:type schema:DefinedTerm
    72 sg:journal.1053886 schema:issn 0178-8051
    73 1432-2064
    74 schema:name Probability Theory and Related Fields
    75 rdf:type schema:Periodical
    76 sg:person.010345577447.82 schema:affiliation https://www.grid.ac/institutes/grid.47840.3f
    77 schema:familyName Basu
    78 schema:givenName Riddhipratim
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010345577447.82
    80 rdf:type schema:Person
    81 sg:person.015324560743.66 schema:affiliation https://www.grid.ac/institutes/grid.47840.3f
    82 schema:familyName Sly
    83 schema:givenName Allan
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015324560743.66
    85 rdf:type schema:Person
    86 sg:pub.10.1007/pl00008732 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008559166
    87 https://doi.org/10.1007/pl00008732
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1002/(sici)1098-2418(200001)16:1<58::aid-rsa5>3.0.co;2-e schema:sameAs https://app.dimensions.ai/details/publication/pub.1029297237
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1002/cpa.21486 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017316975
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1002/rsa.20312 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027107299
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1002/rsa.20368 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004468934
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1002/rsa.20551 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018094785
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1017/cbo9781139107174.018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019469559
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1017/s0963548304006340 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017411398
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1137/0406029 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844776
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1214/09-aap624 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064390607
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1214/10-aihp403 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064391269
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1214/10-aop615 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064391469
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1214/aop/1176988173 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064403483
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1214/ecp.v15-1521 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064396016
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1214/ejp.v15-804 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064396782
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1214/ejp.v3-32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064397379
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1214/ejp.v6-77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025303499
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1239/jap/1324046024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064442596
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1515/9781400881550-016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017088614
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.2969/jmsj/03730391 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070931278
    126 rdf:type schema:CreativeWork
    127 https://www.grid.ac/institutes/grid.47840.3f schema:alternateName University of California, Berkeley
    128 schema:name Department of Statistics, University of California, Berkeley, USA
    129 rdf:type schema:Organization
     




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


    ...