BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jose M. F. Moura

Jose M. F. Moura appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITDistributed, Parallel, and Cluster ComputingSocial and Information Networkseess.SPMachine Learningmath.OCmath.PRmath.SPmath.STStatistics TheoryData Structures and AlgorithmsMultiagent SystemsNetworking and Internet ArchitectureNumerical Analysisphysics.soc-ph

Catalog footprint

What is connected

25works
16topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

25 published item(s)

preprint2022arXiv

Graph Signal Processing: Dualizing GSP Sampling in the Vertex and Spectral Domains

Vertex based and spectral based GSP sampling has been studied recently. The literature recognizes that methods in one domain do not have a counterpart in the other domain. This paper shows that in fact one can develop a unified graph signal sampling theory with analogous interpretations in both domains just like sampling in traditional DSP. To achieve it, we introduce a spectral shift $M$ acting in the spectral domain rather than shift $A$ that acts in the vertex domain. This leads to a GSP theory that starts from the spectral domain, for example, linear shift invariant (LSI) filtering in the spectral domain is with polynomials $P(M)$. We then develop GSP vertex and spectral domain dual versions for each of the four standard sampling steps of subsampling, decimation, upsampling, and interpolation. We show how GSP sampling reduces to DSP sampling when the graph is the directed time cycle graph. Simple examples illustrate the impact of choices that are available in GSP sampling.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Companion Model -- a Canonical Model in Graph Signal Processing

This paper introduces a $\textit{canonical}$ graph signal model defined by a $\textit{canonical}$ graph and a $\textit{canonical}$ shift, the $\textit{companion}$ graph and the $\textit{companion}$ shift. These are canonical because, under standard conditions, we show that any graph signal processing (GSP) model can be transformed into the canonical model. The transform that obtains this is the graph $z$-transform ($\textrm{G$z$T}$) that we introduce. The GSP canonical model comes closest to the discrete signal processing (DSP) time signal models: the structure of the companion shift decomposes into a line shift and a signal continuation just like the DSP shift and the GSP canonical graph is a directed line graph with a terminal condition reflecting the signal continuation condition. We further show that, surprisingly, in the canonical model, convolution of graph signals is fast convolution by the DSP FFT.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Primal-dual methods for large-scale and distributed convex optimization and data analytics

The augmented Lagrangian method (ALM) is a classical optimization tool that solves a given "difficult" (constrained) problem via finding solutions of a sequence of "easier"(often unconstrained) sub-problems with respect to the original (primal) variable, wherein constraints satisfaction is controlled via the so-called dual variables. ALM is highly flexible with respect to how primal sub-problems can be solved, giving rise to a plethora of different primal-dual methods. The powerful ALM mechanism has recently proved to be very successful in various large scale and distributed applications. In addition, several significant advances have appeared, primarily on precise complexity results with respect to computational and communication costs in the presence of inexact updates and design and analysis of novel optimal methods for distributed consensus optimization. We provide a tutorial-style introduction to ALM and its variants for solving convex optimization problems in large scale and distributed settings. We describe control-theoretic tools for the algorithms' analysis and design, survey recent results, and provide novel insights in the context of two emerging applications: federated learning and distributed energy trading.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Spectral Statistics of Lattice Graph Percolation Models

In graph signal processing, the graph adjacency matrix or the graph Laplacian commonly define the shift operator. The spectral decomposition of the shift operator plays an important role in that the eigenvalues represent frequencies and the eigenvectors provide a spectral basis. This is useful, for example, in the design of filters. However, the graph or network may be uncertain due to stochastic influences in construction and maintenance, and, under such conditions, the eigenvalues of the shift matrix become random variables. This paper examines the spectral distribution of the eigenvalues of random networks formed by including each link of a D-dimensional lattice supergraph independently with identical probability, a percolation model. Using the stochastic canonical equation methods developed by Girko for symmetric matrices with independent upper triangular entries, a deterministic distribution is found that asymptotically approximates the empirical spectral distribution of the scaled adjacency matrix for a model with arbitrary parameters. The main results characterize the form of the solution to an important system of equations that leads to this deterministic distribution function and significantly reduce the number of equations that must be solved to find the solution for a given set of model parameters. Simulations comparing the expected empirical spectral distributions and the computed deterministic distributions are provided for sample parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fast Distributed Gradient Methods

We study distributed optimization problems when $N$ nodes minimize the sum of their individual costs subject to a common vector variable. The costs are convex, have Lipschitz continuous gradient (with constant $L$), and bounded gradient. We propose two fast distributed gradient algorithms based on the centralized Nesterov gradient algorithm and establish their convergence rates in terms of the per-node communications $\mathcal{K}$ and the per-node gradient evaluations $k$. Our first method, Distributed Nesterov Gradient, achieves rates $O\left({\log \mathcal{K}}/{\mathcal{K}}\right)$ and $O\left({\log k}/{k}\right)$. Our second method, Distributed Nesterov gradient with Consensus iterations, assumes at all nodes knowledge of $L$ and $μ(W)$ -- the second largest singular value of the $N \times N$ doubly stochastic weight matrix $W$. It achieves rates $O\left({1}/{\mathcal{K}^{2-ξ}}\right)$ and $O\left({1}/{k^2}\right)$ ($ξ>0$ arbitrarily small). Further, we give with both methods explicit dependence of the convergence constants on $N$ and $W$. Simulation examples illustrate our findings.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms

We study distributed optimization where nodes cooperatively minimize the sum of their individual, locally known, convex costs $f_i(x)$'s, $x \in {\mathbb R}^d$ is global. Distributed augmented Lagrangian (AL) methods have good empirical performance on several signal processing and learning applications, but there is limited understanding of their convergence rates and how it depends on the underlying network. This paper establishes globally linear (geometric) convergence rates of a class of deterministic and randomized distributed AL methods, when the $f_i$'s are twice continuously differentiable and have a bounded Hessian. We give explicit dependence of the convergence rates on the underlying network parameters. Simulations illustrate our analytical findings.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Discrete Signal Processing on Graphs: Frequency Analysis

Signals and datasets that arise in physical and engineering applications, as well as social, genetics, biomolecular, and many other domains, are becoming increasingly larger and more complex. In contrast to traditional time and image signals, data in these domains are supported by arbitrary graphs. Signal processing on graphs extends concepts and techniques from traditional signal processing to data indexed by generic graphs. This paper studies the concepts of low and high frequencies on graphs, and low-, high-, and band-pass graph filters. In traditional signal processing, there concepts are easily defined because of a natural frequency ordering that has a physical interpretation. For signals residing on graphs, in general, there is no obvious frequency ordering. We propose a definition of total variation for graph signals that naturally leads to a frequency ordering on graphs and defines low-, high-, and band-pass graph signals and filters. We study the design of graph filters with specified frequency response, and illustrate our approach with applications to sensor malfunction detection and data classification.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Eigendecomposition of Block Tridiagonal Matrices

Block tridiagonal matrices arise in applied mathematics, physics, and signal processing. Many applications require knowledge of eigenvalues and eigenvectors of block tridiagonal matrices, which can be prohibitively expensive for large matrix sizes. In this paper, we address the problem of the eigendecomposition of block tridiagonal matrices by studying a connection between their eigenvalues and zeros of appropriate matrix polynomials. We use this connection with matrix polynomials to derive a closed-form expression for the eigenvectors of block tridiagonal matrices, which eliminates the need for their direct calculation and can lead to a faster calculation of eigenvalues. We also demonstrate with an example that our work can lead to fast algorithms for the eigenvector expansion for block tridiagonal matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Consensus and Products of Random Stochastic Matrices: Exact Rate for Convergence in Probability

Distributed consensus and other linear systems with system stochastic matrices $W_k$ emerge in various settings, like opinion formation in social networks, rendezvous of robots, and distributed inference in sensor networks. The matrices $W_k$ are often random, due to, e.g., random packet dropouts in wireless sensor networks. Key in analyzing the performance of such systems is studying convergence of matrix products $W_kW_{k-1}... W_1$. In this paper, we find the exact exponential rate $I$ for the convergence in probability of the product of such matrices when time $k$ grows large, under the assumption that the $W_k$'s are symmetric and independent identically distributed in time. Further, for commonly used random models like with gossip and link failure, we show that the rate $I$ is found by solving a min-cut problem and, hence, easily computable. Finally, we apply our results to optimally allocate the sensors' transmission power in consensus+innovations distributed detection.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Discrete Signal Processing on Graphs

In social settings, individuals interact through webs of relationships. Each individual is a node in a complex network (or graph) of interdependencies and generates data, lots of data. We label the data by its source, or formally stated, we index the data by the nodes of the graph. The resulting signals (data indexed by the nodes) are far removed from time or image signals indexed by well ordered time samples or pixels. DSP, discrete signal processing, provides a comprehensive, elegant, and efficient methodology to describe, represent, transform, analyze, process, or synthesize these well ordered time or image signals. This paper extends to signals on graphs DSP and its basic tenets, including filters, convolution, z-transform, impulse response, spectral representation, Fourier transform, frequency response, and illustrates DSP on graphs by classifying blogs, linear predicting and compressing data from irregularly located weather stations, or predicting behavior of customers of a mobile service provider.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication

The paper studies distributed static parameter (vector) estimation in sensor networks with nonlinear observation models and noisy inter-sensor communication. It introduces \emph{separably estimable} observation models that generalize the observability condition in linear centralized estimation to nonlinear distributed estimation. It studies two distributed estimation algorithms in separably estimable models, the $\mathcal{NU}$ (with its linear counterpart $\mathcal{LU}$) and the $\mathcal{NLU}$. Their update rule combines a \emph{consensus} step (where each sensor updates the state by weight averaging it with its neighbors' states) and an \emph{innovation} step (where each sensor processes its local current observation.) This makes the three algorithms of the \textit{consensus + innovations} type, very different from traditional consensus. The paper proves consistency (all sensors reach consensus almost surely and converge to the true parameter value,) efficiency, and asymptotic unbiasedness. For $\mathcal{LU}$ and $\mathcal{NU}$, it proves asymptotic normality and provides convergence rate guarantees. The three algorithms are characterized by appropriately chosen decaying weight sequences. Algorithms $\mathcal{LU}$ and $\mathcal{NU}$ are analyzed in the framework of stochastic approximation theory; algorithm $\mathcal{NLU}$ exhibits mixed time-scale behavior and biased perturbations, and its analysis requires a different approach that is developed in the paper.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Large Deviations Performance of Consensus+Innovations Distributed Detection with Non-Gaussian Observations

We establish the large deviations asymptotic performance (error exponent) of consensus+innovations distributed detection over random networks with generic (non-Gaussian) sensor observations. At each time instant, sensors 1) combine theirs with the decision variables of their neighbors (consensus) and 2) assimilate their new observations (innovations). This paper shows for general non-Gaussian distributions that consensus+innovations distributed detection exhibits a phase transition behavior with respect to the network degree of connectivity. Above a threshold, distributed is as good as centralized, with the same optimal asymptotic detection performance, but, below the threshold, distributed detection is suboptimal with respect to centralized detection. We determine this threshold and quantify the performance loss below threshold. Finally, we show the dependence of the threshold and performance on the distribution of the observations: distributed detectors over the same random network, but with different observations' distributions, for example, Gaussian, Laplace, or quantized, may have different asymptotic performance, even when the corresponding centralized detectors have the same asymptotic performance.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Distributed Detection over Noisy Networks: Large Deviations Analysis

We study the large deviations performance of consensus+innovations distributed detection over noisy networks, where sensors at a time step k cooperate with immediate neighbors (consensus) and assimilate their new observations (innovation.) We show that, even under noisy communication, \emph{all sensors} can achieve exponential decay e^{-k C_{\mathrm{dis}}} of the detection error probability, even when certain (or most) sensors cannot detect the event of interest in isolation. We achieve this by designing a single time scale stochastic approximation type distributed detector with the optimal weight sequence {α_k}, by which sensors weigh their neighbors' messages. The optimal design of {α_k} balances the opposing effects of communication noise and information flow from neighbors: larger, slowly decaying α_k improves information flow but injects more communication noise. Further, we quantify the best achievable C_{\mathrm{dis}} as a function of the sensing signal and noise, communication noise, and network connectivity. Finally, we find a threshold on the communication noise power below which a sensor that can detect the event in isolation still improves its detection by cooperation through noisy links.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Distributed Detection over Random Networks: Large Deviations Analysis

We show by large deviations theory that the performance of running consensus is asymptotically equivalent to the performance of the (asymptotically) optimal centralized detector. Running consensus is a stochastic approximation type algorithm for distributed detection in sensor networks, recently proposed. At each time step, the state at each sensor is updated by a local averaging of its own state and the states of its neighbors (consensus) and by accounting for the new observations (innovation). We assume Gaussian, spatially correlated observations, and we allow for the underlying network to be randomly varying. This paper shows through large deviations that the Bayes probability of detection error, for the distributed detector, decays at the best achievable rate, namely, the Chernoff information rate. Numerical examples illustrate the behavior of the distributed detector for finite number of observations.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Distributed Detection over Random Networks: Large Deviations Performance Analysis

We study the large deviations performance, i.e., the exponential decay rate of the error probability, of distributed detection algorithms over random networks. At each time step $k$ each sensor: 1) averages its decision variable with the neighbors' decision variables; and 2) accounts on-the-fly for its new observation. We show that distributed detection exhibits a "phase change" behavior. When the rate of network information flow (the speed of averaging) is above a threshold, then distributed detection is asymptotically equivalent to the optimal centralized detection, i.e., the exponential decay rate of the error probability for distributed detection equals the Chernoff information. When the rate of information flow is below a threshold, distributed detection achieves only a fraction of the Chernoff information rate; we quantify this achievable rate as a function of the network rate of information flow. Simulation examples demonstrate our theoretical findings on the behavior of distributed detection over random networks.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Distributed Detection over Time Varying Networks: Large Deviations Analysis

We apply large deviations theory to study asymptotic performance of running consensus distributed detection in sensor networks. Running consensus is a stochastic approximation type algorithm, recently proposed. At each time step k, the state at each sensor is updated by a local averaging of the sensor's own state and the states of its neighbors (consensus) and by accounting for the new observations (innovation). We assume Gaussian, spatially correlated observations. We allow the underlying network be time varying, provided that the graph that collects the union of links that are online at least once over a finite time window is connected. This paper shows through large deviations that, under stated assumptions on the network connectivity and sensors' observations, the running consensus detection asymptotically approaches in performance the optimal centralized detection. That is, the Bayes probability of detection error (with the running consensus detector) decays exponentially to zero as k goes to infinity at the Chernoff information rate-the best achievable rate of the asymptotically optimal centralized detector.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Gossip Algorithms for Distributed Signal Processing

Gossip algorithms are attractive for in-network processing in sensor networks because they do not require any specialized routing, there is no bottleneck or single point of failure, and they are robust to unreliable wireless network conditions. Recently, there has been a surge of activity in the computer science, control, signal processing, and information theory communities, developing faster and more robust gossip algorithms and deriving theoretical performance guarantees. This article presents an overview of recent work in the area. We describe convergence rate results, which are related to the number of transmitted messages and thus the amount of energy consumed in the network for gossiping. We discuss issues related to gossiping over wireless links, including the effects of quantization and noise, and we illustrate the use of gossip algorithms for canonical signal processing tasks including distributed estimation, source localization, and compression.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Graphical Models as Block-Tree Graphs

We introduce block-tree graphs as a framework for deriving efficient algorithms on graphical models. We define block-tree graphs as a tree-structured graph where each node is a cluster of nodes such that the clusters in the graph are disjoint. This differs from junction-trees, where two clusters connected by an edge always have at least one common node. When compared to junction-trees, we show that constructing block-tree graphs is faster, and finding optimal block-tree graphs has a much smaller search space. Applying our block-tree graph framework to graphical models, we show that, for some graphs, e.g., grid graphs, using block-tree graphs for inference is computationally more efficient than using junction-trees. For graphical models with boundary conditions, the block-tree graph framework transforms the boundary valued problem into an initial value problem. For Gaussian graphical models, the block-tree graph framework leads to a linear state-space representation. Since exact inference in graphical models can be computationally intractable, we propose to use spanning block-trees to derive approximate inference algorithms. Experimental results show the improved performance in using spanning block-trees versus using spanning trees for approximate estimation over Gaussian graphical models.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Kalman Filtering with Intermittent Observations: Weak Convergence to a Stationary Distribution

The paper studies the asymptotic behavior of Random Algebraic Riccati Equations (RARE) arising in Kalman filtering when the arrival of the observations is described by a Bernoulli i.i.d. process. We model the RARE as an order-preserving, strongly sublinear random dynamical system (RDS). Under a sufficient condition, stochastic boundedness, and using a limit-set dichotomy result for order-preserving, strongly sublinear RDS, we establish the asymptotic properties of the RARE: the sequence of random prediction error covariance matrices converges weakly to a unique invariant distribution, whose support exhibits fractal behavior. In particular, this weak convergence holds under broad conditions and even when the observations arrival rate is below the critical probability for mean stability. We apply the weak-Feller property of the Markov process governing the RARE to characterize the support of the limiting invariant distribution as the topological closure of a countable set of points, which, in general, is not dense in the set of positive semi-definite matrices. We use the explicit characterization of the support of the invariant distribution and the almost sure ergodicity of the sample paths to easily compute the moments of the invariant distribution. A one dimensional example illustrates that the support is a fractured subset of the non-negative reals with self-similarity properties.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Telescoping Recursive Representations and Estimation of Gauss-Markov Random Fields

We present \emph{telescoping} recursive representations for both continuous and discrete indexed noncausal Gauss-Markov random fields. Our recursions start at the boundary (a hypersurface in $\R^d$, $d \ge 1$) and telescope inwards. For example, for images, the telescoping representation reduce recursions from $d = 2$ to $d = 1$, i.e., to recursions on a single dimension. Under appropriate conditions, the recursions for the random field are linear stochastic differential/difference equations driven by white noise, for which we derive recursive estimation algorithms, that extend standard algorithms, like the Kalman-Bucy filter and the Rauch-Tung-Striebel smoother, to noncausal Markov random fields.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

DILAND: An Algorithm for Distributed Sensor Localization with Noisy Distance Measurements

In this correspondence, we present an algorithm for distributed sensor localization with noisy distance measurements (DILAND) that extends and makes the DLRE more robust. DLRE is a distributed sensor localization algorithm in $\mathbb{R}^m$ $(m\geq1)$ introduced in \cite{usman_loctsp:08}. DILAND operates when (i) the communication among the sensors is noisy; (ii) the communication links in the network may fail with a non-zero probability; and (iii) the measurements performed to compute distances among the sensors are corrupted with noise. The sensors (which do not know their locations) lie in the convex hull of at least $m+1$ anchors (nodes that know their own locations.) Under minimal assumptions on the connectivity and triangulation of each sensor in the network, this correspondence shows that, under the broad random phenomena described above, DILAND converges almost surely (a.s.) to the exact sensor locations.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Higher Dimensional Consensus: Learning in Large-Scale Networks

The paper presents higher dimension consensus (HDC) for large-scale networks. HDC generalizes the well-known average-consensus algorithm. It divides the nodes of the large-scale network into anchors and sensors. Anchors are nodes whose states are fixed over the HDC iterations, whereas sensors are nodes that update their states as a linear combination of the neighboring states. Under appropriate conditions, we show that the sensor states converge to a linear combination of the anchor states. Through the concept of anchors, HDC captures in a unified framework several interesting network tasks, including distributed sensor localization, leader-follower, distributed Jacobi to solve linear systems of algebraic equations, and, of course, average-consensus. In many network applications, it is of interest to learn the weights of the distributed linear algorithm so that the sensors converge to a desired state. We term this inverse problem the HDC learning problem. We pose learning in HDC as a constrained non-convex optimization problem, which we cast in the framework of multi-objective optimization (MOP) and to which we apply Pareto optimality. We prove analytically relevant properties of the MOP solutions and of the Pareto front from which we derive the solution to learning in HDC. Finally, the paper shows how the MOP approach resolves interesting tradeoffs (speed of convergence versus quality of the final state) arising in learning in HDC in resource constrained networks.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Weight Optimization for Consensus Algorithms with Correlated Switching Topology

We design the weights in consensus algorithms with spatially correlated random topologies. These arise with: 1) networks with spatially correlated random link failures and 2) networks with randomized averaging protocols. We show that the weight optimization problem is convex for both symmetric and asymmetric random graphs. With symmetric random networks, we choose the consensus mean squared error (MSE) convergence rate as optimization criterion and explicitly express this rate as a function of the link formation probabilities, the link formation spatial correlations, and the consensus weights. We prove that the MSE convergence rate is a convex, nonsmooth function of the weights, enabling global optimization of the weights for arbitrary link formation probabilities and link correlation structures. We extend our results to the case of asymmetric random links. We adopt as optimization criterion the mean squared deviation (MSdev) of the nodes states from the current average state. We prove that MSdev is a convex function of the weights. Simulations show that significant performance gain is achieved with our weight design method when compared with methods available in the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Distributing the Kalman Filter for Large-Scale Systems

This paper derives a \emph{distributed} Kalman filter to estimate a sparsely connected, large-scale, $n-$dimensional, dynamical system monitored by a network of $N$ sensors. Local Kalman filters are implemented on the ($n_l-$dimensional, where $n_l\ll n$) sub-systems that are obtained after spatially decomposing the large-scale system. The resulting sub-systems overlap, which along with an assimilation procedure on the local Kalman filters, preserve an $L$th order Gauss-Markovian structure of the centralized error processes. The information loss due to the $L$th order Gauss-Markovian approximation is controllable as it can be characterized by a divergence that decreases as $L\uparrow$. The order of the approximation, $L$, leads to a lower bound on the dimension of the sub-systems, hence, providing a criterion for sub-system selection. The assimilation procedure is carried out on the local error covariances with a distributed iterate collapse inversion (DICI) algorithm that we introduce. The DICI algorithm computes the (approximated) centralized Riccati and Lyapunov equations iteratively with only local communication and low-order computation. We fuse the observations that are common among the local Kalman filters using bipartite fusion graphs and consensus averaging algorithms. The proposed algorithm achieves full distribution of the Kalman filter that is coherent with the centralized Kalman filter with an $L$th order Gaussian-Markovian structure on the centralized error processes. Nowhere storage, communication, or computation of $n-$dimensional vectors and matrices is needed; only $n_l \ll n$ dimensional vectors and matrices are communicated or used in the computation at the sensors.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs

This paper presents a systematic methodology based on the algebraic theory of signal processing to classify and derive fast algorithms for linear transforms. Instead of manipulating the entries of transform matrices, our approach derives the algorithms by stepwise decomposition of the associated signal models, or polynomial algebras. This decomposition is based on two generic methods or algebraic principles that generalize the well-known Cooley-Tukey FFT and make the algorithms' derivations concise and transparent. Application to the 16 discrete cosine and sine transforms yields a large class of fast algorithms, many of which have not been found before.

0 citations0 reviewsNo code linkedOpen access