Efficient Shift-Invariant Dictionary Learning
Guoqing Zheng*, Carnegie Mellon University; Yiming Yang, ; Jaime Carbonell,
Shift-invariant dictionary learning (SIDL) refers to the problem of discovering a set of latent basis vectors (the dictionary) that captures informative local patterns at diﬀerent locations of the input sequences, and a sparse coding for each sequence as a linear combination of the latent basis elements. It diﬀers from conventional dictionary learning and sparse coding where the latent basis has the same dimension as the input vectors, where the focus is on global patterns instead of shift-invariant local patterns. Unsupervised discovery of shift-invariant dictionary and the corresponding sparse coding has been an open challenge as the number of candidate local patterns is extremely large, and the number of possible linear combinations of such local patterns is even more so. In this paper we propose a new framework for unsupervised discovery of both the shift-invariant basis and the sparse coding of input data, with eﬃcient algorithms for tractable optimization. Empirical evaluations on multiple time series data sets demonstrate the eﬀectiveness and eﬃciency of the proposed method.