Shift-invariant dictionary learning for sparse representations: extending K-SVD

Shift-invariant dictionaries are generated by taking all the possible shifts of a few short patterns. They are helpful to represent long signals where the same pattern can appear several times at different positions. We present an algorithm that learns shift invariant dictionaries from long training signals. This algorithm is an extension of K-SVD. It alternates a sparse decomposition step and a dictionary update step. The update is more difficult in the shift-invariant case because of occurrences of the same pattern that overlap. We propose and evaluate an unbiased extension of the method used in K-SVD, i.e. a method able to exactly retrieve the original dictionary in a noiseless case.