On the size of incoherent systems (Q719361)

Upper bounds and lower bounds on the sizes of the dictionaries and such bounds on the coherence parameters are provided in this paper for approximations of the greedy type in \(n\) dimensions (both complex or real valued). These bounds are motivated by the current research on compressed sensing where systems are used with small coherence parameters, and on these systems the useful greedy algorithms are employed. A typical upper bound on the characteristic \(N(n,\mu)\), \(n\) being the dimension and \(\mu\) the coherence, is \(\exp(C n\mu^2\log(\mu^{-1}))\).