Transcript Optimal
Optimal Sampling Strategies for Multiscale Stochastic Processes Vinay Ribeiro Rolf Riedi, Rich Baraniuk (Rice University) Motivation Global (space/time) average Limited number of local samples • Probing for RTT (ping, TCP), available bandwidth (pathload, pathChirp) • Packet trace collection – Traffic matrix estimation, overall traffic composition • Routing/Connectivity analysis – Sample few routing tables • Sensor networks – deploy limited number of sensors probe packets How to optimally placeTN samples 0 to estimate the global quantity? Multiscale Stochastic Processes root Scale j leaves • Nodes at higher scales – averages over larger regions • Powerful structure – model LRD traffic, image data, natural phenomena • root – global average, leaves – local samples • Choose N leaf nodes to give best linear estimate (in terms of mean squared error) of root node • Bunched, uniform, exponential? Quad-tree Independent Innovations Trees split N n N-n • Each node is linear combination of parent and independent random innovation • Recursive top-to-bottom algorithm • Concave optimization for split at each node • Polynomial time algorithm O(N x depth + (# tree nodes)) • Uniformly spaced leaves are optimal if innovations i.i.d. within scale Covariance Trees • Distance : Two leaf nodes have distance j if their lowest common ancestor is at scale j • Covariance tree : Covariance between leaf nodes with distance j is cj (only a function of distance), covariance between root and any leaf node is constant, • Positively correlation progression : cj>cj+1 • Negatively correlation progression : cj<cj+1 Covariance Tree Result Positive correlation progression Negative correlation progression optimal worst-case uniform bunch bunch (conjecture) uniform • Optimality proof: Simply construct an independent innovations tree with similar correlation structure • Worst case proof: Based on eigenanalysis Numerical Results • Covariance trees with fractional Gaussian noise correlation structure • Plots of normalized MSE vs. number of leaves for different leaf patterns Positive correlation progression Negative correlation progression Future Directions • Sampling – – – – more general tree structures non-linear estimates non-tree stochastic processes leverage related work in Statistics (Bellhouse et al) • Internet Inference – how to determine correlation between traffic traces, routing tables etc. • Sensor networks – jointly optimize with other constraints like power transmission Water-Filling • • • : arbitrary set of leaf nodes; : size of X : leaves on left, : leaves on right : linear min. mean sq. error of estimating root using X • • • 3 4 2 1 N= 0 • Repeat at next lower scale with N replaced by l*N (left) and (N-l*N) (right) • Result: If innovations identically distributed within each scale then uniformly distribute leaves, l*N=b N/2 c fL(l) 0 1 2 34 fR(l) 0 1 2 34 Covariance Tree Result • Result: For a positive correlation progresssion choosing leaf nodes uniformly in the tree is optimal. However, for negatively correlation progression this same uniform choice is the worst case! • Optimality proof: Simply construct an independent innovations tree with similar correlation structure • Worst case proof: The uniform choice maximizes sum of elements of SX Using eigen analysis show that this implies that uniform choice minimizes sum of elements of S-1X