Tracking and approximating data matrices in streaming fashion is a fundamental challenge. The problem requires more care and attention when data comes from multiple distributed sites, each receiving a stream of data. This paper considers the problem of "tracking approximations to a matrix" in the distributed streaming model. In this model, there are m distributed sites each observing a distinct stream of data (where each element is a row of a distributed matrix) and has a communication channel with a coordinator, and the goal is to track an eps-approximation to the norm of the matrix along any direction. To that end, we present novel algorithms to address the matrix approximation problem. Our algorithms maintain a smaller matrix B, as an approximation to a distributed streaming matrix A, such that for any unit vector x: | ||A x||^2 - ||B x||^2 | <= eps ||A||_F^2. Our algorithms work in streaming fashion and incur small communication, which is critical for distributed computation. Our best method is deterministic and uses only O((m eps) log(beta N)) communication, where N is the size of stream (at the time of the query) and beta is an upper-bound on the squared norm of any row of the matrix. In addition to proving all algorithmic properties theoretically, extensive experiments with real large datasets demonstrate the efficiency of these protocols.
An extension of FD to derive streaming sketch results with bounds on relative errors, i.e., to ensure that @math , appeared in @cite_31 . It also gives that @math where @math is the top @math rows of @math and @math is the projection of @math onto the row-space of @math . This latter bound is interesting because, as we will see, it indicates that when most of the variation is captured in the first @math principal components, then we can almost recover the entire matrix exactly.
@cite_31
2962984690
We consider processing an n x d matrix A in a stream with row-wise updates according to a recent algorithm called Frequent Directions (Liberty, KDD 2013). This algorithm maintains an e x d matrix Q deterministically, processing each row in O(de2) time; the processing time can be decreased to O(de) with a slight modification in the algorithm and a constant increase in space. Then for any unit vector x, the matrix Q satisfies [EQUATION] We show that if one sets e = ⌈k + k e⌉ and returns Qk, a k x d matrix that is simply the top k rows of Q, then we achieve the following properties: [EQUATION] and where πQk (A) is the projection of A onto the rowspace of Qk then [EQUATION] We also show that Frequent Directions cannot be adapted to a sparse version in an obvious way that retains e original rows of the matrix, as opposed to a linear combination or sketch of the rows.