Before revision:  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  .
After revision:  In particular, we use a variant of low-rank factorisation, which considers interval uncertainty sets around "known entries", 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 .