Derandomizing Restricted Isometries via the Legendre Symbol

Afonso S. Bandeira; Matthew Fickus; Dustin G. Mixon; Joel Moreira

doi:10.1007/s00365-015-9310-6

Derandomizing Restricted Isometries via the Legendre Symbol

Afonso S. Bandeira, Matthew Fickus, Dustin G. Mixon, Joel Moreira^*

^*Corresponding author for this work

Mathematics

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

The restricted isometry property (RIP) is an important matrix condition in compressed sensing, but the best matrix constructions to date use randomness. This paper leverages pseudorandom properties of the Legendre symbol to reduce the number of random bits in an RIP matrix with Bernoulli entries. In this regard, the Legendre symbol is not special—our main result naturally generalizes to any small-bias sample space. We also conjecture that no random bits are necessary for our Legendre symbol-based construction.

Original language	English (US)
Pages (from-to)	409-424
Number of pages	16
Journal	Constructive Approximation
Volume	43
Issue number	3
DOIs	https://doi.org/10.1007/s00365-015-9310-6
State	Published - Jun 1 2016

Funding

The authors thank Prof. Peter Sarnak for insightful discussions. A. S. Bandeira was supported by AFOSR Grant No. FA9550-12-1-0317, and M. Fickus and D. G. Mixon were supported by NSF Grant No. DMS-1321779. The views expressed in this article are those of the authors and do not reflect the official policy or position of the United States Air Force, Department of Defense, or the U.S. Government.

Keywords

Compressed sensing
Derandomization
Legendre symbol
Restricted isometry property
Small-bias sample space

ASJC Scopus subject areas

Analysis
General Mathematics
Computational Mathematics

Access to Document

10.1007/s00365-015-9310-6

Cite this

@article{c8a385926771430695aa0db506b3f04b,

title = "Derandomizing Restricted Isometries via the Legendre Symbol",

abstract = "The restricted isometry property (RIP) is an important matrix condition in compressed sensing, but the best matrix constructions to date use randomness. This paper leverages pseudorandom properties of the Legendre symbol to reduce the number of random bits in an RIP matrix with Bernoulli entries. In this regard, the Legendre symbol is not special—our main result naturally generalizes to any small-bias sample space. We also conjecture that no random bits are necessary for our Legendre symbol-based construction.",

keywords = "Compressed sensing, Derandomization, Legendre symbol, Restricted isometry property, Small-bias sample space",

author = "Bandeira, {Afonso S.} and Matthew Fickus and Mixon, {Dustin G.} and Joel Moreira",

note = "Publisher Copyright: {\textcopyright} 2015, Springer Science+Business Media New York.",

year = "2016",

month = jun,

day = "1",

doi = "10.1007/s00365-015-9310-6",

language = "English (US)",

volume = "43",

pages = "409--424",

journal = "Constructive Approximation",

issn = "0176-4276",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Derandomizing Restricted Isometries via the Legendre Symbol

AU - Bandeira, Afonso S.

AU - Fickus, Matthew

AU - Mixon, Dustin G.

AU - Moreira, Joel

PY - 2016/6/1

Y1 - 2016/6/1

N2 - The restricted isometry property (RIP) is an important matrix condition in compressed sensing, but the best matrix constructions to date use randomness. This paper leverages pseudorandom properties of the Legendre symbol to reduce the number of random bits in an RIP matrix with Bernoulli entries. In this regard, the Legendre symbol is not special—our main result naturally generalizes to any small-bias sample space. We also conjecture that no random bits are necessary for our Legendre symbol-based construction.

AB - The restricted isometry property (RIP) is an important matrix condition in compressed sensing, but the best matrix constructions to date use randomness. This paper leverages pseudorandom properties of the Legendre symbol to reduce the number of random bits in an RIP matrix with Bernoulli entries. In this regard, the Legendre symbol is not special—our main result naturally generalizes to any small-bias sample space. We also conjecture that no random bits are necessary for our Legendre symbol-based construction.

KW - Compressed sensing

KW - Derandomization

KW - Legendre symbol

KW - Restricted isometry property

KW - Small-bias sample space

UR - http://www.scopus.com/inward/record.url?scp=84944523644&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944523644&partnerID=8YFLogxK

U2 - 10.1007/s00365-015-9310-6

DO - 10.1007/s00365-015-9310-6

M3 - Article

AN - SCOPUS:84944523644

SN - 0176-4276

VL - 43

SP - 409

EP - 424

JO - Constructive Approximation

JF - Constructive Approximation

IS - 3

ER -

Derandomizing Restricted Isometries via the Legendre Symbol

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this