Learning Measurement Matrices for Redundant Dictionaries

Sparsity as a powerful instrument in signal processing is now commonplace. However, it is also well known that certain classes of signals do not admit a sparse expansion in an orthonormal basis (e.g., a mixture of spikes and sinuoids is non-sparse in either the canonical or Fourier basis). Therefore, it is typical to use an overcomplete basis, or a redundant dictionary, for representing such complicated signals. Mathematically, x 2 RN is k-sparse in a dictionary D 2 RnN, where n < N, if x = D where 2 RN contains only k nonzeros. Compressive Sensing (CS) [1] encompasses the development of efficient techniques for sampling and reconstruction of sparse signals. A signal x 2 Rn may be sampled by inner products with m < n vectors; therefore, y = x = D, where 2 Rmn is the measurement matrix. Here, the matrix D is sometimes called the holographic basis. Signal reconstruction can be performed using a slew of algorithms; see, for example, [2]. It is generally accepte