A conditional construction of restricted isometries

Afonso S. Bandeira, Dustin G. Mixon, Joel Moreira

Research output: Contribution to journalArticle

Abstract

We study the restricted isometry property of a matrix that is built from the discrete Fourier transform matrix by collecting rows indexed by quadratic residues. We find an ∈ > 0 such that, conditioned on a folklore conjecture in number theory, this matrix satisfies the restricted isometry property with sparsity parameter K = Ω(M1/2+∈), where M is the number of rows.

Original languageEnglish (US)
Pages (from-to)372-381
Number of pages10
JournalInternational Mathematics Research Notices
Volume2017
Issue number2
DOIs
StatePublished - 2017

Fingerprint

Isometry
Quadratic residue
Discrete Fourier transform
Number theory
Sparsity

ASJC Scopus subject areas

  • Mathematics(all)

Cite this

Bandeira, A. S., Mixon, D. G., & Moreira, J. (2017). A conditional construction of restricted isometries. International Mathematics Research Notices, 2017(2), 372-381. DOI: 10.1093/imrn/rnv385

A conditional construction of restricted isometries. / Bandeira, Afonso S.; Mixon, Dustin G.; Moreira, Joel.

In: International Mathematics Research Notices, Vol. 2017, No. 2, 2017, p. 372-381.

Research output: Contribution to journalArticle

Bandeira, AS, Mixon, DG & Moreira, J 2017, 'A conditional construction of restricted isometries' International Mathematics Research Notices, vol 2017, no. 2, pp. 372-381. DOI: 10.1093/imrn/rnv385
Bandeira AS, Mixon DG, Moreira J. A conditional construction of restricted isometries. International Mathematics Research Notices. 2017;2017(2):372-381. Available from, DOI: 10.1093/imrn/rnv385

Bandeira, Afonso S.; Mixon, Dustin G.; Moreira, Joel / A conditional construction of restricted isometries.

In: International Mathematics Research Notices, Vol. 2017, No. 2, 2017, p. 372-381.

Research output: Contribution to journalArticle

@article{f8026a83bbea45fcbd010481f476f912,
title = "A conditional construction of restricted isometries",
abstract = "We study the restricted isometry property of a matrix that is built from the discrete Fourier transform matrix by collecting rows indexed by quadratic residues. We find an ∈ > 0 such that, conditioned on a folklore conjecture in number theory, this matrix satisfies the restricted isometry property with sparsity parameter K = Ω(M1/2+∈), where M is the number of rows.",
author = "Bandeira, {Afonso S.} and Mixon, {Dustin G.} and Joel Moreira",
year = "2017",
doi = "10.1093/imrn/rnv385",
volume = "2017",
pages = "372--381",
journal = "International Mathematics Research Notices",
issn = "1073-7928",
publisher = "Oxford University Press",
number = "2",

}

TY - JOUR

T1 - A conditional construction of restricted isometries

AU - Bandeira,Afonso S.

AU - Mixon,Dustin G.

AU - Moreira,Joel

PY - 2017

Y1 - 2017

N2 - We study the restricted isometry property of a matrix that is built from the discrete Fourier transform matrix by collecting rows indexed by quadratic residues. We find an ∈ > 0 such that, conditioned on a folklore conjecture in number theory, this matrix satisfies the restricted isometry property with sparsity parameter K = Ω(M1/2+∈), where M is the number of rows.

AB - We study the restricted isometry property of a matrix that is built from the discrete Fourier transform matrix by collecting rows indexed by quadratic residues. We find an ∈ > 0 such that, conditioned on a folklore conjecture in number theory, this matrix satisfies the restricted isometry property with sparsity parameter K = Ω(M1/2+∈), where M is the number of rows.

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

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

U2 - 10.1093/imrn/rnv385

DO - 10.1093/imrn/rnv385

M3 - Article

VL - 2017

SP - 372

EP - 381

JO - International Mathematics Research Notices

T2 - International Mathematics Research Notices

JF - International Mathematics Research Notices

SN - 1073-7928

IS - 2

ER -