Search

We consider consensus algorithms in their most general setting and provide conditions under which such algorithms are guaranteed to converge, almost surely, to a consensus. Let {A(t), B(t)} ∈ RN×N be (possibly) stochastic, nonstationary matrices and {x(t), m(t)} 6 RN×1 be state and perturbation vectors, respectively. For any consensus algorithm of the form x(t + 1) = A(t)x(t) + B(t)m(t), we provide conditions under which consensus is achieved almost surely, i.e., Pr-{limt →∞ x(t) = c1} -1 for some c ∈ R. Moreover, we show that this general result subsumes recently reported results for specific consensus algorithms classes, including sum-preserving, nonsum-preserving, quantized, and noisy gossip algorithms. Also provided are the e-converging time for any such converging iterative algorithm, i.e., the earliest time at which the vector x(t) is e close to consensus, and sufficient conditions for convergence in expectation to the average of the initial node measurements. Finally, mean square error bounds of any consensus algorithm of the form discussed above are presented.

Motivated by applications to wireless sensor, peer-to-peer, and ad hoc networks, we study distributed broadcasting algorithms for exchanging information and computing in an arbitrarily connected network of nodes. Specifically, we study a broadcasting-based gossiping algorithm to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. We show that the broadcast gossip algorithm converges almost surely to a consensus. We prove that the random consensus value is, in expectation, the average of initial node measurements and that it can be made arbitrarily close to this value in mean squared error sense, under a balanced connectivity model and by trading off convergence speed with accuracy of the computation. We provide theoretical and numerical results on the mean square error performance, on the convergence rate and study the effect of the ldquomixing parameterrdquo on the convergence rate of the broadcast gossip algorithm. The results indicate that the mean squared error strictly decreases through iterations until the consensus is achieved. Finally, we assess and compare the communication cost of the broadcast gossip algorithm to achieve a given distance to consensus through theoretical and numerical results.

This paper proposes an approach to accelerate local, linear iterative network algorithms asymptotically achieving distributed average consensus. We focus on the class of algorithms in which each node initializes its ldquostate valuerdquo to the local measurement and then at each iteration of the algorithm, updates this state value by adding a weighted sum of its own and its neighbors' state values. Provided the weight matrix satisfies certain convergence conditions, the state values asymptotically converge to the average of the measurements, but the convergence is generally slow, impeding the practical application of these algorithms. In order to improve the rate of convergence, we propose a novel method where each node employs a linear predictor to predict future node values. The local update then becomes a convex (weighted) sum of the original consensus update and the prediction; convergence is faster because redundant states are bypassed. The method is linear and poses a small computational burden. For a concrete theoretical analysis, we prove the existence of a convergent solution in the general case and then focus on one-step prediction based on the current state, and derive the optimal mixing parameter in the convex sum for this case. Evaluation of the optimal mixing parameter requires knowledge of the eigenvalues of the weight matrix, so we present a bound on the optimal parameter. Calculation of this bound requires only local information. We provide simulation results that demonstrate the validity and effectiveness of the proposed scheme. The results indicate that the incorporation of a multistep predictor can lead to convergence rates that are much faster than those achieved by an optimum weight matrix in the standard consensus framework.

In this paper, we develop algorithms for distributed computation of averages of the node data over networks with bandwidth/power constraints or large volumes of data. Distributed averaging algorithms fail to achieve consensus when deterministic uniform quantization is adopted. We propose a distributed algorithm in which the nodes utilize probabilistically quantized information, i.e., dithered quantization, to communicate with each other. The algorithm we develop is a dynamical system that generates sequences achieving a consensus at one of the quantization values almost surely. In addition, we show that the expected value of the consensus is equal to the average of the original sensor data. We derive an upper bound on the mean-square-error performance of the probabilistically quantized distributed averaging (PQDA). Moreover, we show that the convergence of the PQDA is monotonic by studying the evolution of the minimum-length interval containing the node values. We reveal that the length of this interval is a monotonically nonincreasing function with limit zero. We also demonstrate that all the node values, in the worst case, converge to the final two quantization bins at the same rate as standard unquantized consensus. Finally, we report the results of simulations conducted to evaluate the behavior and the effectiveness of the proposed algorithm in various scenarios.

Decentralized estimation of a noise-corrupted source parameter by a bandwidth-constrained sensor network feeding, through a noisy channel, a fusion center is considered. The sensors, due to bandwidth constraints, provide binary representatives of a noise-corrupted source parameter. Recently, proposed decentralized, distributed estimation, and power scheduling methods do no consider errors occurring during the transmission of binary observations from the sensors to fusion center. In this paper, we extend the decentralized estimation model to the case where imperfect transmission channels are considered. The proposed estimator, which operates on additive channel noise corrupted versions of quantized noisy sensor observations, is approached from maximum likelihood (ML) perspective. The resulting ML estimate is a root, in the region of interest (ROI), of a derivative polynomial function. We analyze the natural logarithm of the polynomial within the ROI showing that the function is log-concave, thereby indicating that numerical methods, such as Newton's algorithm, can be utilized to obtain the optimal solution. Due to complexity and implementation issues associated with the numerical methods, we derive and analyze simpler suboptimal solutions, i.e., the two-stage and mean estimators. The two-stage estimator first estimates the binary observations from noisy fusion center observations utilizing a threshold operation, followed by an estimate of the source parameter. The optimal threshold is the maximum a posteriori (MAP) detector for binary detection and minimizes the probability of binary observation estimation error. Optimal threshold expressions for commonly utilized light-(Gaussian) and heavy-tailed (Cauchy) channel noise models are derived. The mean estimator simply averages the noisy fusion center observations. The output variances of means of the proposed suboptimal estimators are derived. In addition, a computational complexity analysis is presented comparing the proposed ML optimal and suboptimal two-stage and mean estimators. Numerical examples evaluating and comparing the performance of proposed ML, two-stage and mean estimators are also presented.

A broad range of statistical processes is characterized by the generalized Gaussian statistics. For instance, the Gaussian and Laplacian probability density functions are special cases of generalized Gaussian statistics. Moreover, the linear and median filtering structures are statistically related to the maximum likelihood estimates of location under Gaussian and Laplacian statistics, respectively. In this paper, we investigate the well-established statistical relationship between Gaussian and Cauchy distributions, showing that the random variable formed as the ratio of two independent Gaussian distributed random variables is Cauchy distributed. We also note that the Cauchy distribution is a member of the generalized Cauchy distribution family. Recently proposed myriad filtering is based on the maximum likelihood estimate of location under Cauchy statistics. An analogous relationship is formed here for the Laplacian statistics, as the ratio of Laplacian statistics yields the distribution referred here to as the Meridian. Interestingly, the Meridian distribution is also a member of the generalized Cauchy family. The maximum likelihood estimate under the obtained statistics is analyzed. Motivated by the maximum likelihood estimate under meridian statistics, meridian filtering is proposed. The analysis presented here indicates that the proposed filtering structure exhibits characteristics more robust than that of median and myriad filtering structures. The statistical and deterministic properties essential to signal processing applications of the meridian filter are given. The meridian filtering structure is extended to admit real-valued weights utilizing the sign coupling approach. Finally, simulations are performed to evaluate and compare the proposed meridian filtering structure performance to those of linear, median, and myriad filtering.

Speckle is a multiplicative noise that degrades ultrasound images. Recent advancements in ultrasound instrumentation and portable ultrasound devices necessitate the need for more robust despeckling techniques, for both routine clinical practice and teleconsultation. Methods previously proposed for speckle reduction suffer from two major limitations: 1) noise attenuation is not sufficient, especially in the smooth and background areas; 2) existing methods do not sufficiently preserve or enhance edges--they only inhibit smoothing near edges. In this paper, we propose a novel technique that is capable of reducing the speckle more effectively than previous methods and jointly enhancing the edge information, rather than just inhibiting smoothing. The proposed method utilizes the Rayleigh distribution to model the speckle and adopts the robust maximum-likelihood estimation approach. The resulting estimator is statistically analyzed through first and second moment derivations. A tuning parameter that naturally evolves in the estimation equation is analyzed, and an adaptive method utilizing the instantaneous coefficient of variation is proposed to adjust this parameter. To further tailor performance, a weighted version of the proposed estimator is introduced to exploit varying statistics of input samples. Finally, the proposed method is evaluated and compared to well-accepted methods through simulations utilizing synthetic and real ultrasound data.

Huber proposed the Pepsi family of epsi-contaminated normal distributions to model environments characterized by heavy-tailed distributions. Based on this two-component mixture distribution, mean-median (MEM) filters were proposed. The MEM filter output is a combination of the sample mean and the sample median, where observation samples are weighted uniformly. This property of MEM filters constrains them to the class of smoothers lacking frequency-selective filtering capabilities. This paper extends MEM filtering to the weighted sum-median (WSM) filtering structure admitting real-valued weights, thereby enabling more general filtering characteristics, i.e, bandpass and high-pass filtering. The proposed filter structure is also well motivated from a presented maximum likelihood (ML) estimate analysis under epsi-contaminated statistics. The ML analysis demonstrates the need for a combination of weighted sum (WS) and weighted median (WM) type filters for processing of signals corrupted by epsi-contaminated noise. The WSM filter is statistically analyzed through the determination of filter output variance and breakdown probability. The combination parameter alpha is optimized to minimize the filter output variance, which is a measure of noise attenuation capability. Moreover, filter design procedures that yield a desired spectral response are detailed. Finally, the proposed WSM filter structure is tested utilizing signal processing applications including low-pass, bandpass, and high-pass filtering and image processing applications including image sharpening and denoising, evaluating and comparing the WSM filter performance to that of the WS, WM, and MEM filters

Linear combinations of polynomial terms yield poor performance in environments characterized by heavy-tailed distributions. Weighted myriad (WMy) filters, however, are well known for their outlier suppression and detail preservation properties. It is shown here that the WMy methodology is naturally extended to the polynomial sample case, yielding filter structures that exploit the higher order statistics of the observed samples while simultaneously being robust to outliers for heavy-tailed distributions environments. Moreover, the introduced power weighted myriad (PWMy) filter class is well motivated by analysis of cross- and square-term statistics of heavy-tailed distributions. The effectiveness of the proposed filter is evaluated through simulations

Traditional polynomial filtering theory, based on linear combinations of polynomial terms, is able to approximate important classes of nonlinear systems. The linear combination of polynomial terms, however, yields poor performance in environments characterized by Gaussian and heavy tailed distributions. Weighted median and weighted myriad filters, in contrast, are well known for their outlier suppression and detail preservation properties. It is shown here that the weighted median and weighted myriad methodologies are naturally extended to the polynomial sample case, yielding hybrid filter structures that exploits the higher-order statistics of the observed samples while simultaneously being robust to outliers for both Gaussian and heavy-tailed distributions environments. Moreover, the introduced hybrid polynomial filter classes are well motivated by analysis of cross and square term statistics of Gaussian and heavy-tailed distributions. A presented asymptotic tail mass analysis shows that polynomial terms, both under Gaussian and heavy-tailed noise statistics, have heavier tails than the observed samples, indicating that robust combination methods should be utilized to avoid undue influence of outliers. Further analysis shows weighted median processing of polynomial terms for the Gaussian noise case, and weighted median and weighted myriad processing of cross and square terms, respectively, for the heavy-tailed noise case, are justified from a maximum likelihood perspective. Filters parameter optimization procedures are also presented. Finally, the effectiveness of hybrid filters is demonstrated through simulations that include temporal, spectrum, and bispectrum analysis

Quadratic Volterra filters are effective in image sharpening applications. The linear combination of polynomial terms, however, yields poor performance in noisy environments. Weighted median (WM) filters, in contrast, are well known for their outlier suppression and detail preservation properties. The WM sample selection methodology is naturally extended to the quadratic sample case, yielding a filter structure referred to as quadratic weighted median (QWM) that exploits the higher order statistics of the observed samples while simultaneously being robust to outliers arising in the higher order statistics of environment noise. Through statistical analysis of higher order samples, it is shown that, although the parent Gaussian distribution is light tailed, the higher order terms exhibit heavy-tailed distributions. The optimal combination of terms contributing to a quadratic system, i.e., cross and square, is approached from a maximum likelihood perspective which yields the WM processing of these terms. The proposed QWM filter structure is analyzed through determination of the output variance and breakdown probability. The studies show that the QWM exhibits lower variance and breakdown probability indicating the robustness of the proposed structure. The performance of the QWM filter is tested on constant regions, edges and real images, and compared to its weighted-sum dual, the quadratic Volterra filter. The simulation results show that the proposed method simultaneously suppresses the noise and enhances image details. Compared with the quadratic Volterra sharpener, the QWM filter exhibits superior qualitative and quantitative performance in noisy image sharpening.

This correspondence studies the second-order distributions of heavy-tail distributed random variables (RVs). Two models for the heavy-tailed distributions are considered: power law and epsi-contaminated distributions. Special cases of the models considered include 1) RVs formed by the product of two independent, but not necessarily identically distributed, heavy-tailed RVs X and Y, such that Z=XY, and 2) RVs formed through squaring a heavy-tail distributed RV X, such that W=X2. Tail analysis of the RVs, their cross terms, and square values shows the ordering of their tail heaviness. The following results hold strictly for power law distributions and, under mild conditions, for epsi-contaminated distributions: The tail of f Z(x) is heavier than that of fX(x), and the tail of fW(x) is heavier than that of fZ(x), where f (.)(x) denotes the probability density distribution of the corresponding random variable. The heaviness of the tails indicates that robust methods of sample combination and output determination should be utilized to avoid undue influence of outliers and degradation in performance. As examples, the denoising and frequency-selective filtering problems under the derived cross and square statistics for hyperbolic-tailed and epsi-contaminated models are considered. Simulation results indicate that the weighted myriad (WMY) filter outperforms the weighted median (WM) filter, and the WM filter outperforms the weighted sum [finite-impulse-response (FIR)] filter. The results may be exploited in higher order applications of heavy-tailed distributions in networking, such as data traffic modeling, and in nonlinear signal and image processing, such as polynomial and Volterra filtering

This paper extends weighted median (WM) filters to the class of polynomial weighted median (PWM) filters. Traditional polynomial filtering theory, based on linear combinations of polynomial terms, is able to approximate important classes of nonlinear systems. The linear combination of polynomial terms, however, yields poor performance in environments characterized by heavy tailed distributions. Weighted median filters, in contrast, are well known for their outlier suppression and detail preservation properties. The weighted median sample selection methodology is naturally extended to the polynomial sample case, yielding a filter structure that exploits the higher order statistics of the observed samples while simultaneously being robust to outliers. Moreover, the PWM filter class is well motivated by an analysis of cross and square term statistics. A presented probability density function analysis shows that these terms have heavier tails than the observed samples, indicating that robust combination methods should be utilized to avoid undue influence of outliers. Further analysis shows weighted median processing of polynomial terms is justified from a maximum likelihood perspective. The established PWM filter class is statistically analyzed through the determination of the filter output distribution and breakdown probability. Filter parameter optimization procedures are also presented. Finally, the effectiveness of PWM filters is demonstrated through simulations that include temporal, spectrum, and bispectrum analysis.

Statistical modeling is at the heart of many engineering problems. The importance of statistical modeling emanates not only from the desire to accurately characterize stochastic events, but also from the fact that distributions are the central models utilized to derive sample processing theories and methods. The generalized Cauchy distribution (GCD) family has a closed-form pdf expression across the whole family as well as algebraic tails, whichmakes it suitable formodeling many real-life impulsive processes. This paper develops a GCD theory-based approach that allows challenging problems to be formulated in a robust fashion. Notably, the proposed framework subsumes generalized Gaussian distribution (GGD) family-based developments, thereby guaranteeing performance improvements over traditional GCD-based problem formulation techniques. This robust framework can be adapted to a variety of applications in signal processing. As examples, we formulate four practical applications under this framework: (1) filtering for power line communications, (2) estimation in sensor networks with noisy channels, (3) reconstruction methods for compressed sensing, and (4) fuzzy clustering.

The average consensus problem in the distributed signal processing context is addressed by linear iterative algorithms, with asymptotic convergence to the consensus. The convergence of the average consensus for an arbitrary weight matrix satisfying the convergence conditions is unfortunately slow restricting the use of the developed algorithms in applications. In this paper, we propose the use of linear extrapolation methods in order to accelerate distributed linear iterations. We provide analytical and simulation results that demonstrate the validity and effectiveness of the proposed scheme. Finally, we report simulation results showing that the generalized version of our algorithm, when a grid search for the unknown optimum value of mixing parameter is used, significantly outperforms the optimum consensus algorithm based on weight matrix optimization.

Methods to automatically convert graphics into raised-line images have been recently investigated. In this paper, concepts from previous research are extended to the vector graphics case, producing tactile pictures in which important features are emphasized. The proposed algorithm extracts object boundaries and employs a classification process, based on a graphic's hierarchical structure, to determine critical outlines. A single parameter is introduced into the classification process, enabling users to tailor graphics to their own preferences. The resulting outlines are printed using a Braille printer to produce tactile output. Critical outlines are embossed with raised dots of highest height while other lines and details are embossed with a lower height. Psychophysical experiments including discrimination, identification, and comprehension are utilized to evaluate and compare the proposed algorithm. Results indicate that the proposed method outperforms other methods in all three considered tasks. The results also show that emphasizing important features significantly increases comprehension of tactile graphics, validating the proposed method's effectiveness in conveying visual information.