Fast online L1-dictionary learning algorithms for novel document detection

Online L₁-dictionary learning, introduced by Kasiviswanathan et al. [1], is the process of generating a sequence of (dictionary) matrices {A_t+1}, one at a time, for t = 0, 1,.... After committing to A_t+1, a pair of matrices (P_t+1,X_t+1) is revealed and the online algorithm incurs a cost of ∥P_t+1 - A_t+1X_t+1∥1. The goal of the online algorithm is to ensure that the total cost up to each time is not much larger than the smallest total cost of any fixed A chosen with the benefit of hindsight. In this paper, we study three different algorithms for this problem based on the schemes of dual averaging, projected gradient, and alternating direction method of multipliers. We focus on the performance of these algorithms for the application of novel document detection, where online dictionary learning could be used to automatically identify emerging topics of discussion from a voluminous stream of text documents in a scalable manner. Our empirical results show the relative benefits of these three algorithms for this application.