Low-Rank Methods in Event Detection.

We present low-rank methods for event detection. We assume that normal observation come from a low-rank subspace, prior to being corrupted by a uniformly distributed noise. Correspondingly, we aim at recovering a representation of the subspace, and perform event detection by running point-to-subspace distance query in $\ell^\infty$, for each incoming observation. In particular, we use a variant of matrix completion under interval uncertainty on a suitable flattening $M \in R^{m \times n}$ of the input data to obtain a low-rank model $M \approx L \times R$, $L \in R^{m \times r}$, $R \in R^{r \times n}$, $r \ll m$. On-line, we compute the distance of each incoming $x \in R^n$ to the space spanned by $R$. For the distance computation, we present a constant-time algorithm with a one-sided error bounded by a function of the number of coordinates employed.