On support sizes of restricted isometry constants

A generic tool for analyzing sparse approximation algorithms is the restricted isometry property (RIP) introduced by Candes and Tao (2005) [11]. If R(k, n, N) is the RIP constant with support size k for an n x N measurement matrix, we investigate the trend of reducing the support size of the RIP constants for qualitative comparisons between sufficient conditions. For example, which condition is easier to satisfy, R(4k,n, N) < 0.1 or R(2k, n, N) < 0.025? Using a quantitative comparison via phase transitions for Gaussian measurement matrices, three examples from the literature of such support size reduction are considered. In each case, utilizing a larger support size for the RIP constants results in a sufficient condition for exact sparse recovery that is satisfied by a significantly larger subset of Gaussian matrices. (C) 2010 Elsevier Inc. All rights reserved.