Fast Averaging
We are interested in the following question: given n numbers x[subscript 1], ..., x[subscript n], what sorts of approximation of average x[subscript ave] = 1overn (x[subscript 1] + ... + x[subscript n]) can be achieved by knowing only r of these n numbers. Indeed the answer depends on the variation...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72577 https://orcid.org/0000-0003-0737-3259 |
| Summary: | We are interested in the following question: given n numbers x[subscript 1], ..., x[subscript n], what sorts of approximation of average x[subscript ave] = 1overn (x[subscript 1] + ... + x[subscript n]) can be achieved by knowing only r of these n numbers. Indeed the answer depends on the variation in these n numbers. As the main result, we show that if the vector of these n numbers satisfies certain regularity properties captured in the form of finiteness of their empirical moments (third or higher), then it is possible to compute approximation of x[subscript ave] that is within 1 ±ε multiplicative factor with probability at least 1 - δ by choosing, on an average, r = r(ε, δ, σ) of the n numbers at random with r is dependent only on ε, δ and the amount of variation σ in the vector and is independent of n. The task of computing average has a variety of applications such as distributed estimation and optimization, a model for reaching consensus and computing symmetric functions. We discuss implications of the result in the context of two applications: load-balancing in a computational facility running MapReduce, and fast distributed averaging. |
|---|