Information Theoretic Lower Bound of Restricted Isometry Property Constant

Compressed sensing seeks to recover an unknown sparse vector from undersampled rate measurements. Since its introduction, there have been enormous works on compressed sensing that develop efficient algorithms for sparse signal recovery. The restricted isometry property (RIP) has become the dominant...

Full description

Saved in:
Bibliographic Details
Main Authors: Li, Gen, Yan, Jingkai, Gu, Yuantao
Format: Conference Proceeding
Language:English
Subjects:
Compressed sensing
Gaussian random matrix
restricted isometry property
sparse recovery
upper and lower bound
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Compressed sensing seeks to recover an unknown sparse vector from undersampled rate measurements. Since its introduction, there have been enormous works on compressed sensing that develop efficient algorithms for sparse signal recovery. The restricted isometry property (RIP) has become the dominant tool used for the analysis of exact reconstruction from seemingly undersampled measurements. Although the upper bound of the RIP constant has been studied extensively, as far as we know, the result is missing for the lower bound. In this work, we first present a tight lower bound for the RIP constant, filling the gap there. The lower bound is at the same order as the upper bound for the RIP constant. Moreover, we also show that our lower bound is close to the upper bound by numerical simulations. Our bound on the RIP constant provides an information-theoretic lower bound about the sampling rate for the first time, which is the essential question for practitioners.
ISSN:2379-190X
DOI:10.1109/ICASSP.2019.8683742