6486491
A fast lightweight approach to origin-destination IP traffic estimation using partial measurements
In this paper, a novel approach is proposed for estimating traffic matrices. Our method, called PamTram for PArtial Measurement of TRAffic Matrices, couples lightweight origin-destination (OD) flow measurements along with a computationally lightweight algorithm for producing OD estimates. The first key aspect of our method is to actively select a small number of informative OD flows to measure in each estimation interval. To avoid the heavy computation of optimal selection, we use intuition from game theory to develop randomized selection rules, with the goals of reducing errors and adapting to traffic changes. We show that it is sufficient to measure only one flow per measurement period to drastically reduce errors-thus rendering our method lightweight in terms of measurement overhead. The second key aspect is an explanation and proof that an Iterative Proportional Fitting algorithm approximates traffic matrix estimates when the goal is a minimum mean-squared error; this makes our method lightweight in terms of computation overhead. A one-step error bound is provided for PamTram that bounds the average error for the worst scenario. We validate our method using data from Sprint's European Tier-1 IP backbone network and demonstrate its consistent improvement over previous methods.
12165073
On the Convergence of Boosting Procedures
A boosting algorithm seeks to minimize empirically a loss function in a greedy fashion. The resulted estimator takes an additive function form and is built iteratively by applying a base estimator (or learner) to updated samples depending on the previous iterations. This paper studies convergence of boosting when it is carried out over the linear span of a family of basis functions. For general loss functions, we prove the convergence of boosting's greedy optimization to the infinimum of the loss function over the linear span. As a side product, these results reveal the importance of restricting the greedy search step sizes, as known in practice through the works of Friedman and others.
116839195
Some results on empirical processes and stochastic complexity
This thesis contains two parts. In Part I, an intuitive and simple approach is used to obtain uniform convergence and Central Limit Theorems for empirical processes indexed by families of functions, for stationary mixing sequences with not too slow a $\beta$-mixing (or $\phi$-mixing) rate. The conditions imposed are in terms of random metric entropies, and the $\beta$-mixing (or $\phi$-mixing) rate. In the case of a Vapnik-Cervonenkis class, the uniform convergence result holds for any strictly stationary sequence with $\beta$-mixing (or $\phi$-mixing) rate $\beta\sb{n}$ (or $\phi\sb{n}$) = $o$($n\sp{-d}$) for some d $>$ 0, while the Central Limit Theorem requires the rate $\beta\sb{n}$ (or $\phi\sb{n}$ = $o$($n\sp{-d}$) for some d $>$ 3. 
In Part II, we use a shortest code length criterion to select the bin width of a histo-gram from a string of i.i.d. observations. Under smoothness conditions on the underlying density on (0, 1), this criterion is shown to be optimal as a code selection criterion in reaching the smallest redundancy within the class of codes under consideration. Furthermore, the criterion consistently selects the underlying density when it is uniform on (0, 1). 
Minimax lower bounds for the redundancy over many smooth families of underlying densities are also derived. In a special case, the lower bound is shown to be achieved almost surely, and in expectation, by a predictive code based on a sequence of histograms. In the case of Sobolev balls, the minimax optimal code is described and a heuristic proof is provided.
828878
Image denoising via lossy compression and wavelet thresholding
Some past work has proposed to use lossy compression to remove noise, based on the rationale that a reasonable compression method retains the dominant signal features more than the randomness of the noise. Building on this theme, we explain why compression (via coefficient quantization) is appropriate for filtering noise from signal by making the connection that quantization of transform coefficients approximates the operation of wavelet thresholding for denoising. That is, denoising is mainly due to the zero-zone and that the full precision of the thresholded coefficients is of secondary importance. The method of quantization is facilitated by a criterion similar to Rissanen's minimum description length principle. An important issue is the threshold value of the zero-zone (and of wavelet thresholding). For a natural image, it has been observed that its subband coefficients can be well modeled by a Laplacian distribution. With this assumption, we derive a threshold which is easy to compute and is intuitive. Experiments show that the proposed threshold performs close to optimal thresholding.
2105049
Model Selection in Gaussian Graphical Models: High-Dimensional Consistency of l1-regularized MLE
We consider the problem of estimating the graph structure associated with a Gaussian Markov random field (GMRF) from i.i.d. samples. We study the performance of study the performance of thel1-regularized maximum likelihood estimator in the high-dimensional setting, where the number of nodes in the graph p, the number of edges in the graph s and the maximum node degree d, are allowed to grow as a function of the number of samples n. Our main result provides sufficient conditions on (n, p, d) for thel1-regularized MLE estimator to recover all the edges of the graph with high probability. Under some conditions on the model covariance, we show that model selection can be achieved for sample sizes n = Ω(d log(p)), with the error decaying as O(exp(−c log(p))) for some constant c. We illustrate our theoretical results via simulations and show good correspondences between the theoretical predictions and behavior in simulations.
6762008
Perceptual audio coding using adaptive pre- and post-filters and lossless compression
This paper proposes a versatile perceptual audio coding method that achieves high compression ratios and is capable of low encoding/decoding delay. It accommodates a variety of source signals (including both music and speech) with different sampling rates. It is based on separating irrelevance and redundancy reductions into independent functional units. This contrasts traditional audio coding where both are integrated within the same subband decomposition. The separation allows for the independent optimization of the irrelevance and redundancy reduction units. For both reductions, we rely on adaptive filtering and predictive coding as much as possible to minimize the delay. A psycho-acoustically controlled adaptive linear filter is used for the irrelevance reduction, and the redundancy reduction is carried out by a predictive lossless coding scheme, which is termed weighted cascaded least mean squared (WCLMS) method. Experiments are carried out on a database of moderate size which contains mono-signals of different sampling rates and varying nature (music, speech, or mixed). They show that the proposed WCLMS lossless coder outperforms other competing lossless coders in terms of compression ratios and delay, as applied to the pre-filtered signal. Moreover, a subjective listening test of the combined pre-filter/lossless coder and a state-of-the-art perceptual audio coder (PAC) shows that the new method achieves a comparable compression ratio and audio quality with a lower delay.
5803741
Incentive Mechanisms for Peer-to-Peer Systems
Most of the existing research in peer-to-peer systems focuses on protocol design and doesn’t consider the rationality of each peer. One phenomenon that should not be ignored is free riding. Some peers simply consume system resources but contribute nothing to the system. In this paper we present an agent-based peer-to-peer system, in which each peer is a software agent and the agents cooperate to search the whole system through referrals. We present a static and a dynamic pricing mechanism to motivate each agent to behave rationally while still achieving good overall system performance. We study the behavior of the agents under two pricing mechanisms and evaluate the impact of free riding using simulations.
15008871
Large Sample Properties of Weighted Monte Carlo Estimators
A general approach to improving simulation accuracy uses information about auxiliary control variables with known expected values to improve the estimation of unknown quantities. We analyze weighted Monte Carlo estimators that implement this idea by applying weights to independent replications. The weights are chosen to constrain the weighted averages of the control variables. We distinguish two cases (unbiased and biased), depending on whether the weighted averages of the controls are constrained to equal their expected values or some other values. In both cases, the number of constraints is usually smaller than the number of replications, so there may be many feasible weights. We select maximally uniform weights by minimizing a separable convex function of the weights subject to the control variable constraints. Estimators of this form arise (sometimes implicitly) in several settings, including at least two in finance: calibrating a model to market data (as in the work of Avellaneda et al. 2001) and calculating conditional expectations to price American options. We analyze properties of these estimators as the number of replications increases. We show that in the unbiased case, weighted Monte Carlo reduces asymptotic variance, and that all convex objective functions within a large class produce estimators that are very close to each other in a strong sense. In contrast, in the biased case the choice of objective function does matter. We show explicitly how the choice of objective determines the limit to which the estimator converges.
11758
A multi-stream adaptation framework for bandwidth management in 3D tele-immersion
Tele-immersive environments will improve the state of collaboration among distributed participants. However, along with the promise a new set of challenges have emerged including the real-time acquisition, streaming and rendering of 3D scenes to convey a realistic sense of immersive spaces. Unlike 2D video conferencing, a 3D tele-immersive environment employs multiple 3D cameras to cover a much wider field of view, thus generating a very large volume of data that need to be carefully coordinated, organized, and synchronized for Internet transmission, rendering and display. This is a challenging task and a dynamic bandwidth management must be in place. To achieve this goal, we propose a multi-stream adaptation framework for bandwidth management in 3D tele-immersion. The adaptation framework relies on the hierarchy of mechanisms and services that exploits the semantic link of multiple 3D video streams in the tele-immersive environment. We implement a prototype of the framework that integrates semantic stream selection, content adaptation, and 3D data compression services with user preference. The experimental results have demonstrated that the framework shows a good quality of the resulting composite 3D rendered video in case of sufficient bandwidth, while it adapts individual 3D video streams in a coordinated and user-friendly fashion, and yields graceful quality degradation in case of low bandwidth availability.
34534588
Lane boundary detection using a multiresolution Hough transform
Lane boundary detection is the problem of estimating the geometric structure of the lane boundaries of a road based on the images grabbed by a camera on board a vehicle. We use the Hough transform to detect lane boundaries with a parabolic model under a variety of road pavement types, lane structures and weather conditions. In the three-dimensional Hough space, a parabolic curve is represented as a straight line. To simplify the computation, the parametric space can be divided into (i) a two-dimensional space measured by the parameters which are shared by all the lane edges, and (ii) a one-dimensional space of the parameter which makes a distinction among different edges in an image. A multiresolution strategy is used to improve both the speed and accuracy of the Hough transform. Experimental results show that the proposed method is relatively less prone to the image noise and is computationally tractable.
677559
TEEVE: the next generation architecture for tele-immersive environments
Tele-immersive 3D multi-camera room environments are starting to emerge and with them new challenging research questions. One important question is how to organize the large amount of visual data, being captured, processed, transmitted and displayed, and their corresponding resources, over current COTS computing and networking infrastructures so that "everybody" would be able to install and use tele-immersive environments for conferencing and other activities. In this paper, we propose a novel cross-layer control and streaming framework over general purpose delivery infrastructure, called TEEVE (tele-immersive environments for everybody). TEEVE aims for effective and adaptive coordination, synchronization, and soft QoS-enabled delivery of tele-immersive visual streams to remote room(s). The TEEVE experiments between two tele-immersive rooms residing in different institutions more than 2000 miles apart show that we can sustain communication of up to 12 3D video streams with 4/spl sim/5 3D frames per second for each stream, yielding 4/spl sim/5 tele-immersive video rate.