Bounding the restricted isometry constants for a tight frame

I. E. Kaporin

Federal Research Center "Computer Science and Control" of Russian Academy of Sciences

Abstract: The standard restricted isometry condition for a tight frame (frequently used as a compressed sensing matrix) is considered, and deterministic lower bounds are obtained for the constants involved. These bounds depend only on the matrix sizes and sparsity level. The sharpness of the new estimates is discussed as well as their interplay with the existing compressed sensing theory.
Bibliography: 18 titles.

Keywords: compressed sensing, $k$-equivolume tight frame, restricted isometry property, Jacobi polynomials, extreme roots.

UDC: 512.643.8+517.538.3+519.142

MSC: Primary 42C15, 11C20; Secondary 65F15, 33C45

Received: 23.09.2016 and 14.04.2017

DOI: 10.4213/sm8822

 English version: Sbornik: Mathematics, 2017, 208:11, 1646–1660

Bibliographic databases:

• 
• 
• 
• 
• 
•