Conditioning of incoherent sub-dictionaries sampled from a coherent dictionary
This provides a theoretical guarantee for stable sparse representation using coherent dictionaries, benefiting signal processing applications that rely on wavelet or Gabor frames.
The authors prove that sub-dictionaries selected via coherence rejective Poisson sampling from a coherent dictionary are well-conditioned with high probability, provided the expected sub-dictionary size scales as d/log(K).
Motivated by the desire to find a realistic and stable random model for $d$-dimensional signals, that are sparse in a transform-based and thus often coherent frame, such as a wavelet or a Gabor frame, we study the conditioning of incoherent sub-dictionaries sampled from a coherent dictionary, such as a unit norm frame. In particular, we show that if the sub-dictionary is selected via a coherence rejective Poisson sampling model, it is well-conditioned with high probability, as long as its expected size scales as $d/\log (K)$, where $K$ is the number of dictionary elements. The result is proved for the more general case of sampling quadratic sub-matrices from a real but not necessarily symmetric $K\times K$ matrix with zero diagonal, where coherence rejective sampling is defined via a symmetric mask, that acts as coherence substitute.