Encoder blind combinatorial compressed sensing Article Swipe
Michael Murray
,
Jared Tanner
·
YOU?
·
· 2020
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2004.05094
YOU?
·
· 2020
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2004.05094
In its most elementary form, compressed sensing studies the design of decoding algorithms to recover a sufficiently sparse vector or code from a lower dimensional linear measurement vector. Typically it is assumed that the decoder has access to the encoder matrix, which in the combinatorial case is sparse and binary. In this paper we consider the problem of designing a decoder to recover a set of sparse codes from their linear measurements alone, that is without access to encoder matrix. To this end we study the matrix factorisation task of recovering both the encoder and sparse coding matrices from the associated linear measurement matrix. The contribution of this paper is a computationally efficient decoding algorithm, Decoder-Expander Based Factorisation, with strong performance guarantees. In particular, under mild assumptions on the sparse coding matrix and by deploying a novel random encoder matrix, we prove that Decoder-Expander Based Factorisation recovers both the encoder and sparse coding matrix at the optimal measurement rate with high probability and from a near optimal number of measurement vectors. In addition, our experiments demonstrate the efficacy and computational efficiency of our algorithm in practice. Beyond compressed sensing our results may be of interest for researchers working in areas such as linear sketching, coding theory and matrix compression.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2004.05094
- https://arxiv.org/pdf/2004.05094
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4287815857
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4287815857Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2004.05094Digital Object Identifier
- Title
-
Encoder blind combinatorial compressed sensingWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2020Year of publication
- Publication date
-
2020-04-10Full publication date if available
- Authors
-
Michael Murray, Jared TannerList of authors in order
- Landing page
-
https://arxiv.org/abs/2004.05094Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2004.05094Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2004.05094Direct OA link when available
- Concepts
-
Encoder, Compressed sensing, Decoding methods, Algorithm, Computer science, Parity-check matrix, Matrix (chemical analysis), Sparse matrix, Theoretical computer science, Low-density parity-check code, Quantum mechanics, Gaussian, Composite material, Materials science, Physics, Operating systemTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4287815857 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2004.05094 |
| ids.doi | https://doi.org/10.48550/arxiv.2004.05094 |
| ids.openalex | https://openalex.org/W4287815857 |
| fwci | |
| type | preprint |
| title | Encoder blind combinatorial compressed sensing |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10500 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9988999962806702 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2206 |
| topics[0].subfield.display_name | Computational Mechanics |
| topics[0].display_name | Sparse and Compressive Sensing Techniques |
| topics[1].id | https://openalex.org/T10796 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9951000213623047 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1705 |
| topics[1].subfield.display_name | Computer Networks and Communications |
| topics[1].display_name | Cooperative Communication and Network Coding |
| topics[2].id | https://openalex.org/T10964 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9948999881744385 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2208 |
| topics[2].subfield.display_name | Electrical and Electronic Engineering |
| topics[2].display_name | Wireless Communication Security Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C118505674 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7700962424278259 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q42586063 |
| concepts[0].display_name | Encoder |
| concepts[1].id | https://openalex.org/C124851039 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6985915899276733 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q2665459 |
| concepts[1].display_name | Compressed sensing |
| concepts[2].id | https://openalex.org/C57273362 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6763134598731995 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q576722 |
| concepts[2].display_name | Decoding methods |
| concepts[3].id | https://openalex.org/C11413529 |
| concepts[3].level | 1 |
| concepts[3].score | 0.6114200353622437 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[3].display_name | Algorithm |
| concepts[4].id | https://openalex.org/C41008148 |
| concepts[4].level | 0 |
| concepts[4].score | 0.5881452560424805 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[4].display_name | Computer science |
| concepts[5].id | https://openalex.org/C95925971 |
| concepts[5].level | 4 |
| concepts[5].score | 0.5851984024047852 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q3100414 |
| concepts[5].display_name | Parity-check matrix |
| concepts[6].id | https://openalex.org/C106487976 |
| concepts[6].level | 2 |
| concepts[6].score | 0.5130259394645691 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q685816 |
| concepts[6].display_name | Matrix (chemical analysis) |
| concepts[7].id | https://openalex.org/C56372850 |
| concepts[7].level | 3 |
| concepts[7].score | 0.4751988649368286 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q1050404 |
| concepts[7].display_name | Sparse matrix |
| concepts[8].id | https://openalex.org/C80444323 |
| concepts[8].level | 1 |
| concepts[8].score | 0.38502731919288635 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[8].display_name | Theoretical computer science |
| concepts[9].id | https://openalex.org/C67692717 |
| concepts[9].level | 3 |
| concepts[9].score | 0.21668222546577454 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q187444 |
| concepts[9].display_name | Low-density parity-check code |
| concepts[10].id | https://openalex.org/C62520636 |
| concepts[10].level | 1 |
| concepts[10].score | 0.0 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[10].display_name | Quantum mechanics |
| concepts[11].id | https://openalex.org/C163716315 |
| concepts[11].level | 2 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q901177 |
| concepts[11].display_name | Gaussian |
| concepts[12].id | https://openalex.org/C159985019 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q181790 |
| concepts[12].display_name | Composite material |
| concepts[13].id | https://openalex.org/C192562407 |
| concepts[13].level | 0 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q228736 |
| concepts[13].display_name | Materials science |
| concepts[14].id | https://openalex.org/C121332964 |
| concepts[14].level | 0 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[14].display_name | Physics |
| concepts[15].id | https://openalex.org/C111919701 |
| concepts[15].level | 1 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q9135 |
| concepts[15].display_name | Operating system |
| keywords[0].id | https://openalex.org/keywords/encoder |
| keywords[0].score | 0.7700962424278259 |
| keywords[0].display_name | Encoder |
| keywords[1].id | https://openalex.org/keywords/compressed-sensing |
| keywords[1].score | 0.6985915899276733 |
| keywords[1].display_name | Compressed sensing |
| keywords[2].id | https://openalex.org/keywords/decoding-methods |
| keywords[2].score | 0.6763134598731995 |
| keywords[2].display_name | Decoding methods |
| keywords[3].id | https://openalex.org/keywords/algorithm |
| keywords[3].score | 0.6114200353622437 |
| keywords[3].display_name | Algorithm |
| keywords[4].id | https://openalex.org/keywords/computer-science |
| keywords[4].score | 0.5881452560424805 |
| keywords[4].display_name | Computer science |
| keywords[5].id | https://openalex.org/keywords/parity-check-matrix |
| keywords[5].score | 0.5851984024047852 |
| keywords[5].display_name | Parity-check matrix |
| keywords[6].id | https://openalex.org/keywords/matrix |
| keywords[6].score | 0.5130259394645691 |
| keywords[6].display_name | Matrix (chemical analysis) |
| keywords[7].id | https://openalex.org/keywords/sparse-matrix |
| keywords[7].score | 0.4751988649368286 |
| keywords[7].display_name | Sparse matrix |
| keywords[8].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[8].score | 0.38502731919288635 |
| keywords[8].display_name | Theoretical computer science |
| keywords[9].id | https://openalex.org/keywords/low-density-parity-check-code |
| keywords[9].score | 0.21668222546577454 |
| keywords[9].display_name | Low-density parity-check code |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2004.05094 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | cc-by-sa |
| locations[0].pdf_url | https://arxiv.org/pdf/2004.05094 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | https://openalex.org/licenses/cc-by-sa |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2004.05094 |
| locations[1].id | doi:10.48550/arxiv.2004.05094 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2004.05094 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5101429451 |
| authorships[0].author.orcid | https://orcid.org/0009-0003-5764-2362 |
| authorships[0].author.display_name | Michael Murray |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Murray, Michael |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5059562923 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-5561-9949 |
| authorships[1].author.display_name | Jared Tanner |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Tanner, Jared |
| authorships[1].is_corresponding | False |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2004.05094 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Encoder blind combinatorial compressed sensing |
| has_fulltext | True |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10500 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9988999962806702 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2206 |
| primary_topic.subfield.display_name | Computational Mechanics |
| primary_topic.display_name | Sparse and Compressive Sensing Techniques |
| related_works | https://openalex.org/W2158224665, https://openalex.org/W2171839442, https://openalex.org/W2145403642, https://openalex.org/W2118148379, https://openalex.org/W2737338842, https://openalex.org/W3005946484, https://openalex.org/W3080746295, https://openalex.org/W2125154953, https://openalex.org/W4293057822, https://openalex.org/W2140459655 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2004.05094 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | cc-by-sa |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2004.05094 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by-sa |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2004.05094 |
| primary_location.id | pmh:oai:arXiv.org:2004.05094 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | cc-by-sa |
| primary_location.pdf_url | https://arxiv.org/pdf/2004.05094 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | https://openalex.org/licenses/cc-by-sa |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2004.05094 |
| publication_date | 2020-04-10 |
| publication_year | 2020 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 15, 22, 59, 63, 110, 135, 164 |
| abstract_inverted_index.In | 0, 50, 122, 171 |
| abstract_inverted_index.To | 80 |
| abstract_inverted_index.as | 201 |
| abstract_inverted_index.at | 154 |
| abstract_inverted_index.be | 192 |
| abstract_inverted_index.by | 133 |
| abstract_inverted_index.in | 42, 184, 198 |
| abstract_inverted_index.is | 30, 46, 74, 109 |
| abstract_inverted_index.it | 29 |
| abstract_inverted_index.of | 10, 57, 65, 89, 106, 168, 181, 193 |
| abstract_inverted_index.on | 127 |
| abstract_inverted_index.or | 19 |
| abstract_inverted_index.to | 13, 37, 61, 77 |
| abstract_inverted_index.we | 53, 83, 140 |
| abstract_inverted_index.The | 104 |
| abstract_inverted_index.and | 48, 94, 132, 150, 162, 178, 206 |
| abstract_inverted_index.end | 82 |
| abstract_inverted_index.for | 195 |
| abstract_inverted_index.has | 35 |
| abstract_inverted_index.its | 1 |
| abstract_inverted_index.may | 191 |
| abstract_inverted_index.our | 173, 182, 189 |
| abstract_inverted_index.set | 64 |
| abstract_inverted_index.the | 8, 33, 38, 43, 55, 85, 92, 99, 128, 148, 155, 176 |
| abstract_inverted_index.both | 91, 147 |
| abstract_inverted_index.case | 45 |
| abstract_inverted_index.code | 20 |
| abstract_inverted_index.from | 21, 68, 98, 163 |
| abstract_inverted_index.high | 160 |
| abstract_inverted_index.mild | 125 |
| abstract_inverted_index.most | 2 |
| abstract_inverted_index.near | 165 |
| abstract_inverted_index.rate | 158 |
| abstract_inverted_index.such | 200 |
| abstract_inverted_index.task | 88 |
| abstract_inverted_index.that | 32, 73, 142 |
| abstract_inverted_index.this | 51, 81, 107 |
| abstract_inverted_index.with | 118, 159 |
| abstract_inverted_index.Based | 116, 144 |
| abstract_inverted_index.areas | 199 |
| abstract_inverted_index.codes | 67 |
| abstract_inverted_index.form, | 4 |
| abstract_inverted_index.lower | 23 |
| abstract_inverted_index.novel | 136 |
| abstract_inverted_index.paper | 52, 108 |
| abstract_inverted_index.prove | 141 |
| abstract_inverted_index.study | 84 |
| abstract_inverted_index.their | 69 |
| abstract_inverted_index.under | 124 |
| abstract_inverted_index.which | 41 |
| abstract_inverted_index.Beyond | 186 |
| abstract_inverted_index.access | 36, 76 |
| abstract_inverted_index.alone, | 72 |
| abstract_inverted_index.coding | 96, 130, 152, 204 |
| abstract_inverted_index.design | 9 |
| abstract_inverted_index.linear | 25, 70, 101, 202 |
| abstract_inverted_index.matrix | 86, 131, 153, 207 |
| abstract_inverted_index.number | 167 |
| abstract_inverted_index.random | 137 |
| abstract_inverted_index.sparse | 17, 47, 66, 95, 129, 151 |
| abstract_inverted_index.strong | 119 |
| abstract_inverted_index.theory | 205 |
| abstract_inverted_index.vector | 18 |
| abstract_inverted_index.assumed | 31 |
| abstract_inverted_index.binary. | 49 |
| abstract_inverted_index.decoder | 34, 60 |
| abstract_inverted_index.encoder | 39, 78, 93, 138, 149 |
| abstract_inverted_index.matrix, | 40, 139 |
| abstract_inverted_index.matrix. | 79, 103 |
| abstract_inverted_index.optimal | 156, 166 |
| abstract_inverted_index.problem | 56 |
| abstract_inverted_index.recover | 14, 62 |
| abstract_inverted_index.results | 190 |
| abstract_inverted_index.sensing | 6, 188 |
| abstract_inverted_index.studies | 7 |
| abstract_inverted_index.vector. | 27 |
| abstract_inverted_index.without | 75 |
| abstract_inverted_index.working | 197 |
| abstract_inverted_index.consider | 54 |
| abstract_inverted_index.decoding | 11, 113 |
| abstract_inverted_index.efficacy | 177 |
| abstract_inverted_index.interest | 194 |
| abstract_inverted_index.matrices | 97 |
| abstract_inverted_index.recovers | 146 |
| abstract_inverted_index.vectors. | 170 |
| abstract_inverted_index.Typically | 28 |
| abstract_inverted_index.addition, | 172 |
| abstract_inverted_index.algorithm | 183 |
| abstract_inverted_index.deploying | 134 |
| abstract_inverted_index.designing | 58 |
| abstract_inverted_index.efficient | 112 |
| abstract_inverted_index.practice. | 185 |
| abstract_inverted_index.algorithm, | 114 |
| abstract_inverted_index.algorithms | 12 |
| abstract_inverted_index.associated | 100 |
| abstract_inverted_index.compressed | 5, 187 |
| abstract_inverted_index.efficiency | 180 |
| abstract_inverted_index.elementary | 3 |
| abstract_inverted_index.recovering | 90 |
| abstract_inverted_index.sketching, | 203 |
| abstract_inverted_index.assumptions | 126 |
| abstract_inverted_index.demonstrate | 175 |
| abstract_inverted_index.dimensional | 24 |
| abstract_inverted_index.experiments | 174 |
| abstract_inverted_index.guarantees. | 121 |
| abstract_inverted_index.measurement | 26, 102, 157, 169 |
| abstract_inverted_index.particular, | 123 |
| abstract_inverted_index.performance | 120 |
| abstract_inverted_index.probability | 161 |
| abstract_inverted_index.researchers | 196 |
| abstract_inverted_index.compression. | 208 |
| abstract_inverted_index.contribution | 105 |
| abstract_inverted_index.measurements | 71 |
| abstract_inverted_index.sufficiently | 16 |
| abstract_inverted_index.Factorisation | 145 |
| abstract_inverted_index.combinatorial | 44 |
| abstract_inverted_index.computational | 179 |
| abstract_inverted_index.factorisation | 87 |
| abstract_inverted_index.Factorisation, | 117 |
| abstract_inverted_index.computationally | 111 |
| abstract_inverted_index.Decoder-Expander | 115, 143 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile |