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

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 N87bf1f840caa46e4b97cf50ddbbe10f6
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 N8be10f954d4144b39671ca7b845a1c5a
31 Na13f91b344084221acc811b47f6c778e
32 sg:journal.1053886
33 schema:name Lipschitz embeddings of random sequences
34 schema:pagination 721-775
35 schema:productId N6f4ba8dbcc2e460ebf552fe7099daad6
36 N8b0fdc9d335a40488722bf696ecd6dd0
37 Nb71ebfc1a3cf402ab4cf2ef02f005d56
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 Ne4a53785bb5a44878647dfc8473006ba
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 N435494d577d144a6a5ec3b294e88429f rdf:first sg:person.015324560743.66
48 rdf:rest rdf:nil
49 N6f4ba8dbcc2e460ebf552fe7099daad6 schema:name readcube_id
50 schema:value 1d577ce407149545ab5cf714f5a710a9559a00dafc36c64cdb45e18bd8750702
51 rdf:type schema:PropertyValue
52 N87bf1f840caa46e4b97cf50ddbbe10f6 rdf:first sg:person.010345577447.82
53 rdf:rest N435494d577d144a6a5ec3b294e88429f
54 N8b0fdc9d335a40488722bf696ecd6dd0 schema:name doi
55 schema:value 10.1007/s00440-013-0519-7
56 rdf:type schema:PropertyValue
57 N8be10f954d4144b39671ca7b845a1c5a schema:issueNumber 3-4
58 rdf:type schema:PublicationIssue
59 Na13f91b344084221acc811b47f6c778e schema:volumeNumber 159
60 rdf:type schema:PublicationVolume
61 Nb71ebfc1a3cf402ab4cf2ef02f005d56 schema:name dimensions_id
62 schema:value pub.1006159664
63 rdf:type schema:PropertyValue
64 Ne4a53785bb5a44878647dfc8473006ba schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
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)


...