On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Jelani Nelson , Huy L. Nguyễn , David P. Woodruff

ABSTRACT

We study classic streaming and sparse recovery problems using deterministic linear sketches, including ℓ1/ℓ1 and ℓ ∞ /ℓ1 sparse recovery problems, norm estimation, and approximate inner product. We focus on devising a fixed matrix A ∈ ℝm×n and a deterministic recovery/estimation procedure which work for all possible input vectors simultaneously. We contribute several improved bounds for these problems. A proof that ℓ ∞ /ℓ1 sparse recovery and inner product estimation are equivalent, and that incoherent matrices can be used to solve both problems. Our upper bound for the number of measurements is m = O(ε− 2 min {logn, (logn / log(1/ε))2}). We can also obtain fast sketching and recovery algorithms by making use of the Fast Johnson-Lindenstrauss transform. Both our running times and number of measurements improve upon previous work. We can also obtain better error guarantees than previous work in terms of a smaller tail of the input vector.A new lower bound for the number of linear measurements required to solve ℓ1/ℓ1 sparse recovery. We show Ω(k/ε2 + klog(n/k)/ε) measurements are required to recover an x′ with ∥ x − x′ ∥ 1 ≤ (1 + ε) ∥ xtail(k) ∥ 1, where xtail(k) is x projected onto all but its largest k coordinates in magnitude.A tight bound of m = Θ(ε− 2log(ε2n)) on the number of measurements required to solve deterministic norm estimation, i.e., to recover ∥ x ∥ 2 ±ε ∥ x ∥ 1. For all the problems we study, tight bounds are already known for the randomized complexity from previous work, except in the case of ℓ1/ℓ1 sparse recovery, where a nearly tight bound is known. Our work thus aims to study the deterministic complexities of these problems. More... »

PAGES

627-638

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-32511-3
978-3-642-32512-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-32512-0_53

DOI

http://dx.doi.org/10.1007/978-3-642-32512-0_53

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Princeton University, USA", 
          "id": "http://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Princeton University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nelson", 
        "givenName": "Jelani", 
        "id": "sg:person.01054252422.41", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01054252422.41"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Princeton University, USA", 
          "id": "http://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Princeton University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nguy\u00ea\u0303n", 
        "givenName": "Huy L.", 
        "id": "sg:person.015741115667.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015741115667.75"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center, San Jose, USA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center, San Jose, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Woodruff", 
        "givenName": "David P.", 
        "id": "sg:person.012727410605.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "We study classic streaming and sparse recovery problems using deterministic linear sketches, including \u21131/\u21131 and \u2113\u2009\u221e\u2009/\u21131 sparse recovery problems, norm estimation, and approximate inner product. We focus on devising a fixed matrix A\u2009\u2208\u2009\u211dm\u00d7n and a deterministic recovery/estimation procedure which work for all possible input vectors simultaneously. We contribute several improved bounds for these problems. \nA proof that \u2113\u2009\u221e\u2009/\u21131 sparse recovery and inner product estimation are equivalent, and that incoherent matrices can be used to solve both problems. Our upper bound for the number of measurements is m\u2009=\u2009O(\u03b5\u2212\u20092 min {logn, (logn / log(1/\u03b5))2}). We can also obtain fast sketching and recovery algorithms by making use of the Fast Johnson-Lindenstrauss transform. Both our running times and number of measurements improve upon previous work. We can also obtain better error guarantees than previous work in terms of a smaller tail of the input vector.A new lower bound for the number of linear measurements required to solve \u21131/\u21131 sparse recovery. We show \u03a9(k/\u03b52\u2009+\u2009klog(n/k)/\u03b5) measurements are required to recover an x\u2032 with \u2225\u2009x\u2009\u2212\u2009x\u2032\u2009\u2225\u20091\u2009\u2264\u2009(1\u2009+\u2009\u03b5)\u2009\u2225\u2009xtail(k)\u2009\u2225\u20091, where xtail(k) is x projected onto all but its largest k coordinates in magnitude.A tight bound of m\u2009=\u2009\u0398(\u03b5\u2212\u20092log(\u03b52n)) on the number of measurements required to solve deterministic norm estimation, i.e., to recover \u2225\u2009x\u2009\u2225\u20092 \u00b1\u03b5\u2009\u2225\u2009x\u2009\u2225\u20091.\nFor all the problems we study, tight bounds are already known for the randomized complexity from previous work, except in the case of \u21131/\u21131 sparse recovery, where a nearly tight bound is known. Our work thus aims to study the deterministic complexities of these problems.", 
    "editor": [
      {
        "familyName": "Gupta", 
        "givenName": "Anupam", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9", 
        "type": "Person"
      }, 
      {
        "familyName": "Servedio", 
        "givenName": "Rocco", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-32512-0_53", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-32511-3", 
        "978-3-642-32512-0"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "number of measurements", 
      "sparse recovery problem", 
      "norm estimation", 
      "sparse recovery", 
      "Approximate Inner Products", 
      "better error guarantees", 
      "recovery problem", 
      "fast sketching", 
      "Johnson-Lindenstrauss transform", 
      "Fast Johnson-Lindenstrauss Transform", 
      "linear sketches", 
      "incoherent matrices", 
      "k coordinates", 
      "inner product", 
      "improved bounds", 
      "tight bounds", 
      "estimation procedure", 
      "randomized complexity", 
      "deterministic complexity", 
      "possible input vectors", 
      "input vector", 
      "error guarantees", 
      "product estimation", 
      "previous work", 
      "bounds", 
      "recovery algorithm", 
      "estimation", 
      "linear measurements", 
      "problem", 
      "x\u2032", 
      "small tail", 
      "matrix", 
      "complexity", 
      "vector", 
      "coordinates", 
      "algorithm", 
      "number", 
      "guarantees", 
      "proof", 
      "measurements", 
      "sketching", 
      "work", 
      "terms", 
      "tail", 
      "transform", 
      "magnitude", 
      "streaming", 
      "cases", 
      "procedure", 
      "sketch", 
      "time", 
      "use", 
      "products", 
      "recovery"
    ], 
    "name": "On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation", 
    "pagination": "627-638", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029605275"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-32512-0_53"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-32512-0_53", 
      "https://app.dimensions.ai/details/publication/pub.1029605275"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_286.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-32512-0_53"
  }
]
 

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/978-3-642-32512-0_53'

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/978-3-642-32512-0_53'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-32512-0_53'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-32512-0_53'


 

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

145 TRIPLES      22 PREDICATES      79 URIs      72 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-32512-0_53 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N821416fb6d1c4960b6a53ca55e472d0c
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description We study classic streaming and sparse recovery problems using deterministic linear sketches, including ℓ1/ℓ1 and ℓ ∞ /ℓ1 sparse recovery problems, norm estimation, and approximate inner product. We focus on devising a fixed matrix A ∈ ℝm×n and a deterministic recovery/estimation procedure which work for all possible input vectors simultaneously. We contribute several improved bounds for these problems. A proof that ℓ ∞ /ℓ1 sparse recovery and inner product estimation are equivalent, and that incoherent matrices can be used to solve both problems. Our upper bound for the number of measurements is m = O(ε− 2 min {logn, (logn / log(1/ε))2}). We can also obtain fast sketching and recovery algorithms by making use of the Fast Johnson-Lindenstrauss transform. Both our running times and number of measurements improve upon previous work. We can also obtain better error guarantees than previous work in terms of a smaller tail of the input vector.A new lower bound for the number of linear measurements required to solve ℓ1/ℓ1 sparse recovery. We show Ω(k/ε2 + klog(n/k)/ε) measurements are required to recover an x′ with ∥ x − x′ ∥ 1 ≤ (1 + ε) ∥ xtail(k) ∥ 1, where xtail(k) is x projected onto all but its largest k coordinates in magnitude.A tight bound of m = Θ(ε− 2log(ε2n)) on the number of measurements required to solve deterministic norm estimation, i.e., to recover ∥ x ∥ 2 ±ε ∥ x ∥ 1. For all the problems we study, tight bounds are already known for the randomized complexity from previous work, except in the case of ℓ1/ℓ1 sparse recovery, where a nearly tight bound is known. Our work thus aims to study the deterministic complexities of these problems.
7 schema:editor Ne429aec77d42439c95db4240f0adf86d
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N620fe1910cf44418b14140a729254b1c
11 schema:keywords Approximate Inner Products
12 Fast Johnson-Lindenstrauss Transform
13 Johnson-Lindenstrauss transform
14 algorithm
15 better error guarantees
16 bounds
17 cases
18 complexity
19 coordinates
20 deterministic complexity
21 error guarantees
22 estimation
23 estimation procedure
24 fast sketching
25 guarantees
26 improved bounds
27 incoherent matrices
28 inner product
29 input vector
30 k coordinates
31 linear measurements
32 linear sketches
33 magnitude
34 matrix
35 measurements
36 norm estimation
37 number
38 number of measurements
39 possible input vectors
40 previous work
41 problem
42 procedure
43 product estimation
44 products
45 proof
46 randomized complexity
47 recovery
48 recovery algorithm
49 recovery problem
50 sketch
51 sketching
52 small tail
53 sparse recovery
54 sparse recovery problem
55 streaming
56 tail
57 terms
58 tight bounds
59 time
60 transform
61 use
62 vector
63 work
64 x′
65 schema:name On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation
66 schema:pagination 627-638
67 schema:productId N892d2701e50f48329558a6560b186ef1
68 Nf12f28c5c37d414c979a6dc41c4433c8
69 schema:publisher N7f36c71b41144d4e96961ce84af65438
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029605275
71 https://doi.org/10.1007/978-3-642-32512-0_53
72 schema:sdDatePublished 2022-11-24T21:15
73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
74 schema:sdPublisher N13a469cc259041fc8ad7090a5d28d2ed
75 schema:url https://doi.org/10.1007/978-3-642-32512-0_53
76 sgo:license sg:explorer/license/
77 sgo:sdDataset chapters
78 rdf:type schema:Chapter
79 N13a469cc259041fc8ad7090a5d28d2ed schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 N620fe1910cf44418b14140a729254b1c schema:isbn 978-3-642-32511-3
82 978-3-642-32512-0
83 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
84 rdf:type schema:Book
85 N7f36c71b41144d4e96961ce84af65438 schema:name Springer Nature
86 rdf:type schema:Organisation
87 N821416fb6d1c4960b6a53ca55e472d0c rdf:first sg:person.01054252422.41
88 rdf:rest Nfdf5c1b627af4377a8a53da107e1e12f
89 N83cac0f4ab6f4a7fb11043272bffcb24 schema:familyName Gupta
90 schema:givenName Anupam
91 rdf:type schema:Person
92 N892d2701e50f48329558a6560b186ef1 schema:name dimensions_id
93 schema:value pub.1029605275
94 rdf:type schema:PropertyValue
95 N976036f1a4f54f1d9f9297e79a708b57 schema:familyName Servedio
96 schema:givenName Rocco
97 rdf:type schema:Person
98 Nc4cde458b08940e4966e5993fdf3bca1 schema:familyName Jansen
99 schema:givenName Klaus
100 rdf:type schema:Person
101 Nddbba90883c4480b820924cff70e7ff0 schema:familyName Rolim
102 schema:givenName José
103 rdf:type schema:Person
104 Ne0bc9a1f609b4eaaa22a0824d496d51d rdf:first sg:person.012727410605.86
105 rdf:rest rdf:nil
106 Ne429aec77d42439c95db4240f0adf86d rdf:first N83cac0f4ab6f4a7fb11043272bffcb24
107 rdf:rest Nf16f40498cb1425daaf374689788d330
108 Ne998088d48e54900a5a7c6bf6a90726c rdf:first N976036f1a4f54f1d9f9297e79a708b57
109 rdf:rest rdf:nil
110 Nf12f28c5c37d414c979a6dc41c4433c8 schema:name doi
111 schema:value 10.1007/978-3-642-32512-0_53
112 rdf:type schema:PropertyValue
113 Nf16f40498cb1425daaf374689788d330 rdf:first Nc4cde458b08940e4966e5993fdf3bca1
114 rdf:rest Nfa9d6be5a0cb4ab6aa20e24bf06772fb
115 Nfa9d6be5a0cb4ab6aa20e24bf06772fb rdf:first Nddbba90883c4480b820924cff70e7ff0
116 rdf:rest Ne998088d48e54900a5a7c6bf6a90726c
117 Nfdf5c1b627af4377a8a53da107e1e12f rdf:first sg:person.015741115667.75
118 rdf:rest Ne0bc9a1f609b4eaaa22a0824d496d51d
119 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
120 schema:name Mathematical Sciences
121 rdf:type schema:DefinedTerm
122 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
123 schema:name Statistics
124 rdf:type schema:DefinedTerm
125 sg:person.01054252422.41 schema:affiliation grid-institutes:grid.16750.35
126 schema:familyName Nelson
127 schema:givenName Jelani
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01054252422.41
129 rdf:type schema:Person
130 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.481551.c
131 schema:familyName Woodruff
132 schema:givenName David P.
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
134 rdf:type schema:Person
135 sg:person.015741115667.75 schema:affiliation grid-institutes:grid.16750.35
136 schema:familyName Nguyễn
137 schema:givenName Huy L.
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015741115667.75
139 rdf:type schema:Person
140 grid-institutes:grid.16750.35 schema:alternateName Princeton University, USA
141 schema:name Princeton University, USA
142 rdf:type schema:Organization
143 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, San Jose, USA
144 schema:name IBM Almaden Research Center, San Jose, USA
145 rdf:type schema:Organization
 




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


...