Fast online L<inf>1</inf>-dictionary learning algorithms for novel document detection

Shiva Prasad Kasiviswanathan

Abstract

Online L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -dictionary learning, introduced by Kasiviswanathan et al. [1], is the process of generating a sequence of (dictionary) matrices {A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t+1</sub> }, one at a time, for t = 0, 1,.... After committing to A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t+1</sub> , a pair of matrices (P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t+1</sub> ,X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t+1</sub> ) is revealed and the online algorithm incurs a cost of ∥P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t+1</sub> - A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t+1</sub> X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t+1</sub> ∥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.
BibTeX
@inproceedings{kasiviswanathan2013fast,
  author = {Shiva Prasad Kasiviswanathan},
  title = {{Fast online L\&lt;inf\&gt;1\&lt;/inf\&gt;-dictionary learning algorithms for novel document detection}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2013},
  url = {https://openreview.net/forum?id=lbEG3bLX1c},
}

Loading related content...

Figure