Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs

Simone Brugiapaglia; Sjoerd Dirksen; Hans Christian Jung; Holger Rauhut

doi:10.1016/j.acha.2021.01.004

Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs

Simone Brugiapaglia, Sjoerd Dirksen, Hans Christian Jung, Holger Rauhut^*

^*Corresponding author for this work

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

Abstract

We study sparse recovery with structured random measurement matrices having independent, identically distributed, and uniformly bounded rows and with a nontrivial covariance structure. This class of matrices arises from random sampling of bounded Riesz systems and generalizes random partial Fourier matrices. Our main result improves the currently available results for the null space and restricted isometry properties of such random matrices. The main novelty of our analysis is a new upper bound for the expectation of the supremum of a Bernoulli process associated with a restricted isometry constant. We apply our result to prove new performance guarantees for the CORSING method, a recently introduced numerical approximation technique for partial differential equations (PDEs) based on compressive sensing.

Original language	English
Pages (from-to)	231-269
Number of pages	39
Journal	Applied and Computational Harmonic Analysis
Volume	53
DOIs	https://doi.org/10.1016/j.acha.2021.01.004
Publication status	Published - 1 Jul 2021

Bibliographical note

Funding Information:
S.B. acknowledges the Postdoctoral Training Centre in Stochastics of the Pacific Institute for the Mathematical Sciences ( PIMS ), the Natural Sciences and Engineering Research Council of Canada (NSERC) through grant number 611675 and RGPIN-2020-06766 , the Centre for Advanced Modelling Science (CADMOS), and the Faculty of Arts and Science of Concordia University for their financial support. S.D., H.C.J., and H.R. acknowledge funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under the priority program SPP 1798 (COSIP -Compressed Sensing in Information Processing) through the project Quantized Compressive Spectrum Sensing (project no. 273202924 ).

Publisher Copyright:
© 2021 Elsevier Inc.

Keywords

Bounded Riesz systems
CORSING method
Compressive sensing
Generic chaining
Numerical PDEs
Restricted isometry constants

Access to Document

10.1016/j.acha.2021.01.004

1-s2.0-S1063520321000051-mainFinal published version, 772 KB

Cite this

@article{1c2821d58a684656a27e45b36e2a5802,

title = "Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs",

abstract = "We study sparse recovery with structured random measurement matrices having independent, identically distributed, and uniformly bounded rows and with a nontrivial covariance structure. This class of matrices arises from random sampling of bounded Riesz systems and generalizes random partial Fourier matrices. Our main result improves the currently available results for the null space and restricted isometry properties of such random matrices. The main novelty of our analysis is a new upper bound for the expectation of the supremum of a Bernoulli process associated with a restricted isometry constant. We apply our result to prove new performance guarantees for the CORSING method, a recently introduced numerical approximation technique for partial differential equations (PDEs) based on compressive sensing.",

keywords = "Bounded Riesz systems, CORSING method, Compressive sensing, Generic chaining, Numerical PDEs, Restricted isometry constants",

author = "Simone Brugiapaglia and Sjoerd Dirksen and Jung, {Hans Christian} and Holger Rauhut",

note = "Funding Information: S.B. acknowledges the Postdoctoral Training Centre in Stochastics of the Pacific Institute for the Mathematical Sciences ( PIMS ), the Natural Sciences and Engineering Research Council of Canada (NSERC) through grant number 611675 and RGPIN-2020-06766 , the Centre for Advanced Modelling Science (CADMOS), and the Faculty of Arts and Science of Concordia University for their financial support. S.D., H.C.J., and H.R. acknowledge funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under the priority program SPP 1798 (COSIP -Compressed Sensing in Information Processing) through the project Quantized Compressive Spectrum Sensing (project no. 273202924 ). Publisher Copyright: {\textcopyright} 2021 Elsevier Inc.",

year = "2021",

month = jul,

day = "1",

doi = "10.1016/j.acha.2021.01.004",

language = "English",

volume = "53",

pages = "231--269",

journal = "Applied and Computational Harmonic Analysis",

issn = "1063-5203",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs

AU - Brugiapaglia, Simone

AU - Dirksen, Sjoerd

AU - Jung, Hans Christian

AU - Rauhut, Holger

N1 - Funding Information: S.B. acknowledges the Postdoctoral Training Centre in Stochastics of the Pacific Institute for the Mathematical Sciences ( PIMS ), the Natural Sciences and Engineering Research Council of Canada (NSERC) through grant number 611675 and RGPIN-2020-06766 , the Centre for Advanced Modelling Science (CADMOS), and the Faculty of Arts and Science of Concordia University for their financial support. S.D., H.C.J., and H.R. acknowledge funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under the priority program SPP 1798 (COSIP -Compressed Sensing in Information Processing) through the project Quantized Compressive Spectrum Sensing (project no. 273202924 ). Publisher Copyright: © 2021 Elsevier Inc.

PY - 2021/7/1

Y1 - 2021/7/1

N2 - We study sparse recovery with structured random measurement matrices having independent, identically distributed, and uniformly bounded rows and with a nontrivial covariance structure. This class of matrices arises from random sampling of bounded Riesz systems and generalizes random partial Fourier matrices. Our main result improves the currently available results for the null space and restricted isometry properties of such random matrices. The main novelty of our analysis is a new upper bound for the expectation of the supremum of a Bernoulli process associated with a restricted isometry constant. We apply our result to prove new performance guarantees for the CORSING method, a recently introduced numerical approximation technique for partial differential equations (PDEs) based on compressive sensing.

AB - We study sparse recovery with structured random measurement matrices having independent, identically distributed, and uniformly bounded rows and with a nontrivial covariance structure. This class of matrices arises from random sampling of bounded Riesz systems and generalizes random partial Fourier matrices. Our main result improves the currently available results for the null space and restricted isometry properties of such random matrices. The main novelty of our analysis is a new upper bound for the expectation of the supremum of a Bernoulli process associated with a restricted isometry constant. We apply our result to prove new performance guarantees for the CORSING method, a recently introduced numerical approximation technique for partial differential equations (PDEs) based on compressive sensing.

KW - Bounded Riesz systems

KW - CORSING method

KW - Compressive sensing

KW - Generic chaining

KW - Numerical PDEs

KW - Restricted isometry constants

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

U2 - 10.1016/j.acha.2021.01.004

DO - 10.1016/j.acha.2021.01.004

M3 - Article

SN - 1063-5203

VL - 53

SP - 231

EP - 269

JO - Applied and Computational Harmonic Analysis

JF - Applied and Computational Harmonic Analysis

ER -

Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this