State-of-the-art object trackers primarily model appearance relations between the image template and the search region with Siamese networks. However, this well-established approach has a limited ability to leverage both motion and semantic cues of the target object, leading to increasing errors in challenging scenarios like drastic appearance changes and similar-looking distractors. To address the above weaknesses, we propose a novel tracking framework with Motion and Semantic Reasoning (MSRTrack), integrating short-term motion modeling and distinctive semantic features for robust tracking across diverse conditions. Powered by vision large language models (VLLMs) and the Segment Anything Model 2 (SAM2), MSRTrack identifies unique semantic attributes of the target, exploits motion cues across consecutive frames, and complements appearance-based trackers with strong semantic and dynamic reasoning capabilities. Unlike previous vision language tracking (VLT) methods that rely on broad captioning, MSRTrack automatically focuses on a concise set of key semantic attributes of the target, substantially improving target lost recovery and distractor rejection. MSRTrack achieves state-of-the-art performance across multiple tracking benchmarks, with 2.2% improvement on the LaSOT dataset, 9.5% improvement on the VastTrack dataset, and 1.4% on the TNL2K dataset.

Foundation models are now a major focus of leading technology organizations due to their ability to generalize across diverse tasks. Existing approaches for adapting foundation models to new applications often rely on Federated Learning (FL) and disclose the foundation model weights to clients when using it to initialize the global model. While these methods ensure client data privacy, they compromise model and information security. In this paper, we introduce Federated Learning Aggregation Biased by a Foundation Model (FedBaF), a novel method for dynamically integrating pre-trained foundation model weights during the FL aggregation phase. Unlike conventional methods, FedBaF preserves the confidentiality of the foundation model while still leveraging its power to train more accurate models, especially in non-IID and adversarial scenarios. Our comprehensive experiments use Pre-ResNet and foundation models like Vision Transformer to demonstrate that FedBaF not only matches, but often surpasses the test accuracy of traditional weight initialization methods by up to 11.4% in IID and up to 15.8% in non-IID settings. Additionally, FedBaF applied to a Transformer-based language model significantly reduced perplexity by up to 39.2%.

Peer-to-peer learning is an increasingly popular framework that enables beyond-5G distributed edge devices to collaboratively train deep neural networks in a privacy-preserving manner without the aid of a central server. Neural network training algorithms for emerging environments, e.g., smart cities, have many design considerations that are difficult to tune in deployment settings – such as neural network architectures and hyperparameters. This presents a critical need for characterizing the training dynamics of distributed optimization algorithms used to train highly nonconvex neural networks in peer-to-peer learning environments. In this work, we provide an explicit characterization of the learning dynamics of wide neural networks trained using popular distributed gradient descent (DGD) algorithms. Our results leverage both recent advancements in neural tangent kernel (NTK) theory and extensive previous work on distributed learning and consensus. We validate our analytical results by accurately predicting the parameter and error dynamics of wide neural networks trained for classification tasks.

Forecasting graph-based, time-dependent data has broad practical applications but presents challenges. Effective models must capture both spatial and temporal dependencies in the data, while also incorporating auxiliary information to enhance prediction accuracy. In this article, we identify limitations in current state-of-the-art models regarding temporal dependency handling. To overcome this, we introduce GSA-Forecaster, a new deep learning model designed for forecasting in graph-based, time-dependent contexts. GSA-Forecaster utilizes graph sequence attention, a new attention mechanism proposed in this article, to effectively manage temporal dependencies. GSA-Forecaster integrates the data’s graph structure directly into its architecture, addressing spatial dependencies. Additionally, it incorporates auxiliary information to refine its predictions further. We validate its performance using real-world graph-based, time-dependent datasets, where it demonstrates superior effectiveness compared to existing state-of-the-art models.

This paper considers learning the hidden causal network of a linear networked dynamical system (NDS) from the time series data at some of its nodes -- partial observability. The dynamics of the NDS are driven by colored noise that generates spurious associations across pairs of nodes, rendering the problem much harder. To address the challenge of noise correlation and partial observability, we assign to each pair of nodes a feature vector computed from the time series data of observed nodes. The feature embedding is engineered to yield structural consistency: there exists an affine hyperplane that consistently partitions the set of features, separating the feature vectors corresponding to connected pairs of nodes from those corresponding to disconnected pairs. The causal inference problem is thus addressed via clustering the designed features. We demonstrate with simple baseline supervised methods the competitive performance of the proposed causal inference mechanism under broad connectivity regimes and noise correlation levels, including a real world network. Further, we devise novel technical guarantees of structural consistency for linear NDS under the considered regime.

Uncertainty quantification of neural networks is critical to measuring the reliability and robustness of deep learning systems. However, this often involves costly or inaccurate sampling methods and approximations. This paper presents a sample-free moment propagation technique that propagates mean vectors and covariance matrices across a network to accurately characterize the input-output distributions of neural networks. A key enabler of our technique is an analytic solution for the covariance of random variables passed through nonlinear activation functions, such as Heaviside, ReLU, and GELU. The wide applicability and merits of the proposed technique are shown in experiments analyzing the input-output distributions of trained neural networks and training Bayesian neural networks.

While deep learning has been very successful in computer vision, real world operating conditions such as lighting variation, background clutter, or occlusion hinder its accuracy across several tasks. Prior work has shown that hybrid models—combining neural networks and heuristics/algorithms—can outperform vanilla deep learning for several computer vision tasks, such as classification or tracking.We consider the case of object tracking, and evaluate a hybrid model (PhyOT) that conceptualizes deep neural networks as "sensors" in a Kalman filter setup, where prior knowledge, in the form of Newtonian laws of motion, is used to fuse sensor observations and to perform improved estimations. Our experiments combine three neural networks, performing position, indirect velocity and acceleration estimation, respectively, and evaluate such a formulation on two benchmark datasets: a warehouse security camera dataset that we collected and annotated and a traffic camera open dataset.Results suggest that our PhyOT can track objects in extreme conditions that the state-of-the-art deep neural networks fail while its performance in general cases does not degrade significantly from that of existing deep learning approaches. Results also suggest that our PhyOT components are generalizable and transferable.

In a Networked Dynamical System (NDS), each node is a system whose dynamics are coupled with the dynamics of neighboring nodes. The global dynamics naturally builds on this network of couplings and it is often excited by a noise input with nontrivial structure. The underlying network is unknown in many applications and should be inferred from observed data. We assume: i) Partial observability— time series data is only available over a subset of the nodes; ii) Input noise— it is correlated across distinct nodes while temporally independent, i.e., it is spatially colored. We present a feasibility condition on the noise correlation structure wherein there exists a consistent network inference estimator to recover the underlying fundamental dependencies among the observed nodes. Further, we describe a structure identification algorithm that exhibits competitive performance across distinct regimes of network connectivity, observability, and noise correlation.

Graph Convolutional Neural Networks (graph CNNs) adapt the traditional CNN architecture for use on graphs, replacing convolution layers with graph convolution layers. Although similar in architecture, graph CNNs are used for geometric deep learning whereas conventional CNNs are used for deep learning on grid-based data, such as audio or images, with seemingly no direct relationship between the two classes of neural networks.This paper shows that under certain conditions traditional CNNs can be used with graph data as a good approximation to graph CNNs, avoiding the need for graph CNNs. We show this by using an alternative graph signal representation – the graph companion model that we recently proposed in [1]. Instead of using the given graph and signal in the nodal domain, the graph companion model uses the equivalent companion graph and signal representation in the companion domain. By this way, the graph CNN architecture in the nodal domain is equivalent to our deep learning architecture: a traditional CNN in the companion domain with appropriate boundary conditions (b.c.). The paper shows that we obtain similar results on graph classification experiments using a traditional CNN in the companion domain vs. the usual graph CNNs in the nodal domain.

Many Graph Signal Processing (GSP) applications consider product graphs, the product of smaller graphs. For example, with time-varying graph data, the graph shift can be the (Cartesian) product of a space graph and the cyclic time shift. Instead of treating the product graph as a single entity and applying existing GSP techniques, there are computational and experimental advantages to considering the product graph as the product of its factors.Recently, in [1], we showed that GSP is DSP plus boundary conditions (b.c.) in the companion model that we introduced. Under certain conditions, any graph can be converted into a companion graph consisting of a 1D directed path graph augmented with appropriate b.c.. However, when applied to the product graph, the 1D companion model treats the graph as a single entity, producing a 1D path graph with b.c. that cannot be expressed as a product of two graphs, losing the computational and experimental advantages of product graphs.The paper develops a 2D companion model for the product graph in GSP. Our model shows that by considering the product graph in terms of its factors, the 2D companion shift is a 2D directed grid with b.c. in both directions. We show that, under this 2D companion model, GSP is DSP plus b.c. in the multiple dimension case.

We study the problem of graph structure identification, i.e., of recovering the graph of dependencies among time series. We model these time series data as components of the state of linear stochastic networked dynamical systems. We assume partial observability, where the state evolution of only a subset of nodes comprising the network is observed. We propose a new feature-based paradigm: to each pair of nodes, we compute a feature vector from the observed time series. We prove that these features are linearly separable, i.e., there exists a hyperplane that separates the cluster of features associated with connected pairs of nodes from those of disconnected pairs. This renders the features amenable to train a variety of classifiers to perform causal inference. In particular, we use these features to train Convolutional Neural Networks (CNNs). The resulting causal inference mechanism outperforms state-of-the-art counterparts w.r.t. sample-complexity. The trained CNNs generalize well over structurally distinct networks (dense or sparse) and noise-level profiles. Remarkably, they also generalize well to real-world networks while trained over a synthetic network -- namely, a particular realization of a random graph.

A major task in chip design involves identifying the location and shape of each major design block/module in the layout footprint. This is commonly known as floorplanning. The first step of this task is known as global floorplanning and involves identifying a location for each module that minimizes wire length and leaves sufficient area for each module. Existing global floorplanning methods either have a non-convex problem formulation, or have trivial global solutions with no guarantee on the quality of the result. Here, we model the global floorplanning as a Semi-Definite Programming (SDP) problem with a rank constraint. We replace the rank constraint with a direction matrix and convexify the problem, whose solution is shown to be a global optimum if an appropriate direction matrix is chosen. To calculate the direction matrix, a convex iteration algorithm is used where the problem is decomposed into two SDP sub-problems. Furthermore, we introduce a series of techniques that enhance the flexibility, accuracy, and efficiency of our algorithm. Design experiments demonstrate that our proposed method reduces the average wirelength up to 20% for different benchmarks and outline aspect ratios.

While much effort has been devoted to deriving and analyzing effective convex formulations of signal processing problems, the gradients of convex functions also have critical applications ranging from gradient-based optimization to optimal transport. Recent works have explored data-driven methods for learning convex objective functions, but learning their monotone gradients is seldom studied. In this work, we propose C-MGN and M-MGN, two monotone gradient neural network architectures for directly learning the gradients of convex functions. We show that, compared to state of the art methods, our networks are easier to train, learn monotone gradient fields more accurately, and use significantly fewer parameters. We further demonstrate their ability to learn optimal transport mappings to augment driving image data.

Forecasting the dynamics of COVID-19 enables government agencies and public health administrators to take proactive measures to combat the pandemic. This forecasting task faces several key challenges: First, the dynamics of COVID-19 exhibit complex spatial and temporal dependencies. The current growing trend at a location may be similar to that at another location in the past. Second, numerous factors, such as population mobility and geographic proximity between regions, mask usage, vaccine coverage, etc., significantly impact the dynamics. Third, we need to find the appropriate granularity for the forecasting task. The granularity should not be too coarse that we ignore the idiosyncrasies of individual regions. Still, the granularity should not be too fine that the prediction results are seriously vulnerable to noise.This paper addresses these challenges. We propose a simple but effective clustering algorithm that finds the appropriate granularity for the forecasting task. We invent generalized spatiotemporal attention, an attention mechanism that is generalized enough to capture the complex spatial and temporal dependencies and to flexibly account for intra- and inter-region characteristics such as geographic proximity and population mobility. Based on this generalized spatiotemporal attention, we designed COVID-Forecaster, a lightweight deep learning model for forecasting the dynamics of COVID-19. Experimental results demonstrate that COVID-Forecaster significantly outperforms state-of-the-art models. For example, COVID-Forecaster reduces the mean absolute percentage error (MAPE) by 6.8% and the weighted absolute percentage error (WAPE) by 13.5% in forecasting the COVID-19 dynamics at the 3141 counties of the United States.

Unsupervised time series clustering is a challenging problem with diverse industrial applications such as anomaly detection, bio-wearables, etc. These applications typically involve small, low-power devices on the edge that collect and process real-time sensory signals. State-of-the-art time-series clustering methods perform some form of loss minimization that is extremely computationally intensive from the perspective of edge devices. In this work, we propose a neuromorphic approach to unsupervised time series clustering based on Temporal Neural Networks that is capable of ultra low-power, continuous online learning. We demonstrate its clustering performance on a subset of UCR Time Series Archive datasets. Our results show that the proposed approach either outperforms or performs similarly to most of the existing algorithms while being far more amenable for efficient hardware implementation. Our hardware assessment analysis shows that in 7 nm CMOS the proposed architecture, on average, consumes only about 0.005 mm2die area and 22 μW power and can process each signal with about 5 ns latency.

Few-shot classification aims at classifying categories of a novel task by learning from just a few (typically, 1 to 5) labelled examples. An effective approach to few-shot classification involves a prior model trained on a large-sample base domain, which is then finetuned over the novel few-shot task to yield generalizable representations. However, task-specific finetuning is prone to overfitting due to the lack of enough training examples. To alleviate this issue, we propose a new finetuning approach based on contrastive learning that reuses unlabelled examples from the base do-main in the form of distractors. Unlike the nature of unlabelled data used in prior works, distractors belong to classes that do not overlap with the novel categories. We demonstrate for the first time that inclusion of such distractors can significantly boost few-shot generalization. Our technical novelty includes a stochastic pairing of examples sharing the same category in the few-shot task and a weighting term that controls the relative influence of task-specific negatives and distractors. An important aspect of our finetuning objective is that it is agnostic to distractor labels and hence applicable to various base domain settings. More precisely, compared to state-of-the-art approaches, our method shows accuracy gains of up to 12% in cross-domain and up to 5% in unsupervised prior-learning settings. Our code is available at https://github.com/quantacode/Contrastive-Finetuning.git

Deep learning has achieved great success in recognizing video actions, but the collection and annotation of training data are still quite laborious, which mainly lies in two aspects: (1) the amount of required annotated data is large; (2) temporally annotating the location of each action is time-consuming. Works such as few-shot learning or untrimmed video recognition have been proposed to handle either one aspect or the other. However, very few existing works can handle both issues simultaneously. In this paper, we target a new problem, Annotation-Efficient Video Recognition, to reduce the requirement of annotations for both large amount of samples and the action location. Such problem is challenging due to two aspects: (1) the untrimmed videos only have weak supervision; (2) video segments not relevant to current actions of interests (background, BG) could contain actions of interests (foreground, FG) in novel classes, which is a widely existing phenomenon but has rarely been studied in few-shot untrimmed video recognition. To achieve this goal, by analyzing the property of BG, we categorize BG into informative BG (IBG) and non-informative BG (NBG), and we propose (1) an open-set detection based method to find the NBG and FG, (2) a contrastive learning method to learn IBG and distinguish NBG in a self-supervised way, and (3) a self-weighting mechanism for the better distinguishing of IBG and FG. Extensive experiments on ActivityNet v1.2 and ActivityNet v1.3 verify the rationale and effectiveness of the proposed methods.

Existing few-shot learning (FSL) methods usually assume base classes and novel classes are from the same domain (in-domain setting). However, in practice, it may be infeasible to collect sufficient training samples for some special domains to construct base classes. To solve this problem, cross-domain FSL (CDFSL) is proposed very recently to transfer knowledge from general-domain base classes to special-domain novel classes. Existing CDFSL works mostly focus on transferring between near domains, while rarely consider transferring between distant domains, which is in practical need as any novel classes could appear in real-world applications, and is even more challenging. In this paper, we study a challenging subset of CDFSL where the novel classes are in distant domains from base classes, by revisiting the mid-level features, which are more transferable yet under-explored in main stream FSL work. To boost the discriminability of mid-level features, we propose a residual-prediction task to encourage mid-level features to learn discriminative information of each sample. Notably, such mechanism also benefits the in-domain FSL and CDFSL in near domains. Therefore, we provide two types of features for both cross- and in-domain FSL respectively, under the same training framework. Experiments under both settings on six public datasets, including two challenging medical datasets, validate the our rationale and demonstrate state-of-the-art performance. Code will be released.

Deep learning has led to major advances in fields like natural language processing, computer vision, and other Euclidean data domains. Yet, many important fields have data defined on irregular domains, requiring graphs to be explicitly modeled. One such application is drug discovery. Recently, research has found that using graph neural network (GNN) models, given enough data, can perform better than using human-engineered fingerprints or descriptors in predicting molecular properties of potential antibiotics.We explore these state-of-the-art AI models on predicting desirable molecular properties for drugs that can inhibit SARS-CoV-2. We build upon the GNN models with ideas from recent breakthroughs in geometric deep learning, inspired by the topologies of the molecules. In this poster paper, we present an overview of the drug discovery framework, drug-target interaction framework, and GNNs. Preliminary results on two COVID-19 related datasets are encouraging, achieving a ROC-AUC of 0.72 for FDA-approved chemical library screened against SARS-CoV-2 in vitro.

Spatial and time-dependent data is of interest in many applications. This task is difficult due to its complex spatial dependency, long-range temporal dependency, data non-stationarity, and data heterogeneity. To address these challenges, we propose Forecaster, a graph Transformer architecture. Specifically, we start by learning the structure of the graph that parsimoniously represents the spatial dependency between the data at different locations. Based on the topology of the graph, we sparsify the Transformer to account for the strength of spatial dependency, long-range temporal dependency, data non-stationarity, and data heterogeneity. We evaluate Forecaster in the problem of forecasting taxi ride-hailing demand and show that our proposed architecture significantly outperforms the state-of-the-art baselines.

This paper studies the resilient distributed recovery of large fields under measurement attacks, by a team of agents, where each measures a small subset of the components of a large spatially distributed field. An adversary corrupts some of the measurements. The agents collaborate to process their measurements, and each is interested in recovering only a fraction of the field. We present a field recovery consensus+innovations type distributed algorithm that is resilient to measurement attacks, where an agent maintains and updates a local state based on its neighbors states and its own measurement. Under sufficient conditions on the attacker and the connectivity of the communication network, each agent's state, even those with compromised measurements, converges to the true value of the field components that it is interested in recovering. Finally, we illustrate the performance of our algorithm through numerical examples.

In this paper, we present a new approach to interpret deep learning models. By coupling mutual information with network science, we explore how information flows through feedforward networks. We show that efficiently approximating mutual information allows us to create an information measure that quantifies how much information flows between any two neurons of a deep learning model. To that end, we propose NIF, Neural Information Flow, a technique for codifying information flow that exposes deep learning model internals and provides feature attributions.

A feature-based model explanation denotes how much each input feature contributes to a model's output for a given data point. As the number of proposed explanation functions grows, we lack quantitative evaluation criteria to help practitioners know when to use which explanation function. This paper proposes quantitative evaluation criteria for feature-based explanations: low sensitivity, high faithfulness, and low complexity. We devise a framework for aggregating explanation functions. We develop a procedure for learning an aggregate explanation function with lower complexity and then derive a new aggregate Shapley value explanation function that minimizes sensitivity.

Few-shot learning (FSL) aims at recognizing novel classes given only few training samples, which still remains a great challenge for deep learning. However, humans can easily recognize novel classes with only few samples. A key component of such ability is the compositional recognition that human can perform, which has been well studied in cognitive science but is not well explored in FSL. Inspired by such capability of humans, to imitate humans' ability of learning visual primitives and composing primitives to recognize novel classes, we propose an approach to FSL to learn a feature representation composed of important primitives, which is jointly trained with two parts, i.e. primitive discovery and primitive enhancing. In primitive discovery, we focus on learning primitives related to object parts by self-supervision from the order of image splits, avoiding extra laborious annotations and alleviating the effect of semantic gaps. In primitive enhancing, inspired by current studies on the interpretability of deep networks, we provide our composition view for the FSL baseline model. To modify this model for effective composition, inspired by both mathematical deduction and biological studies (the Hebbian Learning rule and the Winner-Take-All mechanism), we propose a soft composition mechanism by enlarging the activation of important primitives while reducing that of others, so as to enhance the influence of important primitives and better utilize these primitives to compose novel classes. Extensive experiments on public benchmarks are conducted on both the few-shot image classification and video recognition tasks. Our method achieves the state-of-the-art performance on all these datasets and shows better interpretability.

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) subproblems 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 subproblems 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 into the context of two emerging applications: federated learning and distributed energy trading.

Developing human-machine trust is a prerequisite for adoption of machine learning systems in decision critical settings (e.g healthcare and governance). Users develop appropriate trust in these systems when they understand how the systems make their decisions. Interpretability not only helps users understand what a system learns but also helps users contest that system to align with their intuition. We propose an algorithm, AVA: Aggregate Valuation of Antecedents, that generates a consensus feature attribution, retrieving local explanations and capturing global patterns learned by a model. Our empirical results show that AVA rivals current benchmarks.

Internet of Things (IoT) applications for Smart Cities, such as systems for traffic control and pollution monitoring, increasingly rely on trustworthy and secure data analytics. Proper countermeasures are needed to ensure that IoT applications function reliably under security threats. This paper studies secure analytics and resilient inference for IoT in the context of recursive parameter estimation. A team of devices makes noisy measurements of an unknown parameter, and an attacker manipulates the measurement data of a subset of the devices. We present a resilient recursive estimation algorithm that processes the measurement streams to recover the value of the parameter, even when a subset of the devices fall under attack. The estimator is guaranteed to be strongly consistent - that is, the estimate converges almost surely to the value of the parameter - as long as less than half of the devices fall under attack. We illustrate the performance of the estimator through numerical examples.

We introduce the task of Visual Dialog, which requires an AI agent to hold a meaningful dialog with humans in natural, conversational language about visual content. Specifically, given an image, a dialog history, and a question about the image, the agent has to ground the question in image, infer context from history, and answer the question accurately. Visual Dialog is disentangled enough from a specific downstream task so as to serve as a general test of machine intelligence, while being sufficiently grounded in vision to allow objective evaluation of individual responses and benchmark progress. We develop a novel two-person real-time chat data-collection protocol to curate a large-scale Visual Dialog dataset (VisDial). VisDial v0.9 has been released and consists of$\sim$1.2M dialog question-answer pairs from 10-round, human-human dialogs grounded in$\sim$120k images from the COCO dataset. We introduce a family of neural encoder-decoder models for Visual Dialog with 3 encoders—Late Fusion, Hierarchical Recurrent Encoder and Memory Network (optionally with attention over image features)—and 2 decoders (generative and discriminative), which outperform a number of sophisticated baselines. We propose a retrieval-based evaluation protocol for Visual Dialog where the AI agent is asked to sort a set of candidate answers and evaluated on metrics such as mean-reciprocal-rank and recall$@k$of human response. We quantify the gap between machine and human performance on the Visual Dialog task via human studies. Putting it all together, we demonstrate the first ‘visual chatbot’! Our dataset, code, pretrained models and visual chatbot are available onhttps://visualdialog.org.

We consider the problem of detecting a random walk on a graph, based on observations of the graph nodes. When visited by the walk, each node of the graph observes a signal of elevated mean, which we assume can be different across different nodes. Outside of the path of the walk, and also in its absence, nodes measure only noise. Assuming the Neyman-Pearson setting, our goal then is to characterize detection performance by computing the error exponent for the probability of a miss, under a constraint on the probability of false alarm. Since the exact computation of the error exponent is known to be difficult, equivalent to the computation of the Lyapunov exponent, we approximate its value by finding a tractable lower bound. The bound reveals an interesting detectability condition: the walk is detectable whenever the entropy of the walk is smaller than one half of the expected signal-to-noise ratio. We derive the bound by extending the notion of Markov types to Gauss-Markov types. These are sequences of the state-observation pairs with a given number of node-to-node transition counts and the same average signal values across nodes, computed from the measurements made during the times the random walk visited each node's respective location. The lower bound has an intuitive interpretation: among all Gauss-Markov types that are asymptotically feasible in the absence of the walk, the bound finds the most typical one under the presence of the walk. Finally, we show by a sequence of judicious problem reformulations that computing the bound reduces to solving a convex optimization problem, which is a result of in its interest own right.

While many approaches have been proposed to estimate and remove blur in a photo, few efforts were made to have an algorithm automatically understand the blur desirability: whether the blur is desired or not, and how it affects the quality of the photo. Such a task not only relies on low-level visual features to identify blurry regions, but also requires high-level understanding of the image content as well as user intent during photo capture. In this paper, we propose a unified framework to estimate a spatially-varying blur map and understand its desirability in terms of image quality at the same time. In particular, we use a dilated fully convolutional neural network with pyramid pooling and boundary refinement layers to generate high-quality blur response maps. If blur exists, we classify its desirability to three levels ranging from good to bad, by distilling high-level semantics and learning an attention map to adaptively localize the important content in the image. The whole framework is end-to-end jointly trained with both supervisions of pixel-wise blur responses and image-wise blur desirability levels. Considering the limitations of existing image blur datasets, we collected a new large-scale dataset with both annotations to facilitate training. The proposed methods are extensively evaluated on two datasets and demonstrate state-of-the-art performance on both tasks.

Network-based epidemics models try to characterize the impact of network topology, which represents contagion pathways, on the spread of infection. Although these models explicitly consider the dynamics of individuals in the given network (i.e., the state of the system is x(t)=[x1(t), x2(t), ..., xN(t)]T), analysis has focused on characterizing the vulnerability of the entire population rather than the vulnerability of the individuals in the population. We focus on characterizing the vulnerability of the ith individual in the network by studying the marginal probability of infection, P(xi=1), of the scaled SIS process. Studying the vulnerability of individuals is important because it may be tempting to assume that P(xi=1) is related to the degree of the ith. node. Since infection rate is usually assumed to be dependent on the number of infected neighbors, then it seems reasonable that nodes with more connections (i.e., higher degree) would be more at risk. We show that this is not always true. Further, with a closed-form approximation of P(xi=1), as solving for the exact probability requires the summation of 2Nterms, we characterize the conditions for when degree distribution is a good indicator of how susceptible an individual is to infection.

At its peak, the Internet-of-Things will largely be composed of low-power devices with wireless radios attached. Yet, secure authentication of these devices amidst adversaries with much higher power and computational capability remains a challenge, even for advanced cryptographic and wireless security protocols. For instance, a high-power software radio could simply replay chunks of signals from a low-power device to emulate it. This paper presents a deep-learning classifier that learns hardware imperfections of low-power radios that are challenging to emulate, even for high- power adversaries. We build an LSTM framework, specifically sensitive to signal imperfections that persist over long durations. Experimental results from a testbed of 30 low-power nodes demonstrate high resilience to advanced software radio adversaries.

Teaching a robot to predict and mimic how a human moves or acts in the near future by observing a series of historical human movements is a crucial first step in human-robot interaction and collaboration. In this paper, we instrument a robot with such a prediction ability by leveraging recent deep learning and computer vision techniques. First, our system takes images from the robot camera as input to produce the corresponding human skeleton based on real-time human pose estimation obtained with the OpenPose library. Then, conditioning on this historical sequence, the robot forecasts plausible motion through a motion predictor, generating a corresponding demonstration. Because of a lack of high-level fidelity validation, existing forecasting algorithms suffer from error accumulation and inaccurate prediction. Inspired by generative adversarial networks (GANs), we introduce a global discriminator that examines whether the predicted sequence is smooth and realistic. Our resulting motion GAN model achieves superior prediction performance to state-of-the-art approaches when evaluated on the standard H3.6M dataset. Based on this motion GAN model, the robot demonstrates its ability to replay the predicted motion in a human-like manner when interacting with a person.

While domain adaptation has been actively researched, most algorithms focus on the single-source-single-target adaptation setting. In this paper we propose new generalization bounds and algorithms under both classification and regression settings for unsupervised multiple source domain adaptation. Our theoretical analysis naturally leads to an efficient learning strategy using adversarial neural networks: we show how to interpret it as learning feature representations that are invariant to the multiple domain shifts while still being discriminative for the learning task. To this end, we propose multisource domain adversarial networks (MDAN) that approach domain adaptation by optimizing task-adaptive generalization bounds. To demonstrate the effectiveness of MDAN, we conduct extensive experiments showing superior adaptation performance on both classification and regression problems: sentiment analysis, digit classification, and vehicle counting.

Deep convolutional neural networks (CNNs) have recognized promise as universal representations for various image recognition tasks. One of their properties is the ability to transfer knowledge from a large annotated source dataset (e.g., ImageNet) to a (typically smaller) target dataset. This is usually accomplished through supervised fine-tuning on labeled new target data. In this work, we address "unsupervised fine-tuning" that transfers a pre-trained network to target tasks with unlabeled data such as image clustering tasks. To this end, we introduce group-sparse non-negative matrix factorization (GSNMF), a variant of NMF, to identify a rich set of high-level latent variables that are informative on the target task. The resulting "factorized convolutional network" (FCN) can itself be seen as a feed-forward model that combines CNN and two-layer structured NMF. We empirically validate our approach and demonstrate state-of-the-art image clustering performance on challenging scene (MIT-67) and fine-grained (Birds-200, Flowers-102) benchmarks. We further show that, when used as unsupervised initialization, our approach improves image classification performance as well.

In this paper, we address the question of how to automatically map computational kernels to highly efficient code for a wide range of computing platforms and establish the correctness of the synthesized code. More specifically, we focus on two fundamental problems that software developers are faced with: performance portability across the ever-changing landscape of parallel platforms and correctness guarantees for sophisticated floating-point code. The problem is approached as follows: We develop a formal framework to capture computational algorithms, computing platforms, and program transformations of interest, using a unifying mathematical formalism we call operator language (OL). Then we cast the problem of synthesizing highly optimized computational kernels for a given machine as a strongly constrained optimization problem that is solved by search and a multistage rewriting system. Since all rewrite steps are semantics preserving, our approach establishes equivalence between the kernel specification and the synthesized program. This approach is implemented in the SPIRAL system, and we demonstrate it with a selection of computational kernels from the signal and image processing domain, software-defined radio, and robotic vehicle control. Our target platforms range from mobile devices, desktops, and server multicore processors to large-scale high-performance and supercomputing systems, and we demonstrate performance comparable to expertly hand-tuned code across kernels and platforms.

Computer architectures and systems are becoming ever more powerful but increasingly more complex. With the end of frequency scaling (about 2004) and the era of multicores/manycores/accelerators, it is exceedingly hard to extract the promised performance, in particular, at a reasonable energy budget. Only highly trained and educated experts can hope to conquer this barrier that, if not appropriately dealt with, can translate into multiple orders of magnitude of underutilization of computer systems when programmed by less specialized programmers or domain scientists. To overcome this challenge, the last ten years have seen a flurry of activity to automate the design and generation of highly efficient implementations for these multicore/ manycore architectures, and to translate high level descriptions of programs into high performance and power efficiency

Research in graph signal processing (GSP) aims to develop tools for processing data defined on irregular graph domains. In this paper, we first provide an overview of core ideas in GSP and their connection to conventional digital signal processing, along with a brief historical perspective to highlight how concepts recently developed in GSP build on top of prior research in other areas. We then summarize recent advances in developing basic GSP tools, including methods for sampling, filtering, or graph learning. Next, we review progress in several application areas using GSP, including processing and analysis of sensor network data, biological data, and applications to image processing and machine learning.

Fifth-generation (5G) networks providing much higher bandwidth and faster data rates will allow connecting vast number of stationary and mobile devices, sensors, agents, users, machines, and vehicles, supporting Internet-of-Things (IoT), real-time dynamic networks of mobile things. Positioning and location awareness will become increasingly important, enabling deployment of new services and contributing to significantly improving the overall performance of the 5G system. Many of the currently talked about solutions to positioning in 5G are centralized, mostly requiring direct communication to the access nodes (or anchors, i.e., nodes with known locations), which in turn requires a high density of anchors. But such centralized positioning solutions may become unwieldy as the number of users and devices continues to grow without limit in sight. As an alternative to the centralized solutions, this paper discusses distributed localization in a 5G-enabled IoT environment where many low power devices, users, or agents are to locate themselves without a direct access to anchors. Even though positioning is essentially a nonlinear problem (solving circle equations by trilateration or triangulation), we discuss a cooperative linear distributed iterative solution with only local measurements, local communication, and local computation needed at each agent. Linearity is obtained by reparametrization of the agent location through barycentric coordinate representations based on local neighborhood geometry that may be computed in terms of certain Cayley-Menger determinants involving relative local inter-agent distance measurements. After a brief introduction to the localization problem, and other available distributed solutions primarily based on directly addressing the nonlinear formulation, we present the distributed linear solution for stationary agent networks and study its convergence, its robustness to noise, and extensions to mobile scenarios, in which agents, users, and (possibly) anchors are dynamic.

We introduce the task of Visual Dialog, which requires an AI agent to hold a meaningful dialog with humans in natural, conversational language about visual content. Specifically, given an image, a dialog history, and a question about the image, the agent has to ground the question in image, infer context from history, and answer the question accurately. Visual Dialog is disentangled enough from a specific downstream task so as to serve as a general test of machine intelligence, while being grounded in vision enough to allow objective evaluation of individual responses and benchmark progress. We develop a novel two-person chat data-collection protocol to curate a large-scale Visual Dialog dataset (VisDial). VisDial contains 1 dialog (10 question-answer pairs) on ~140k images from the COCO dataset, with a total of ~1.4M dialog question-answer pairs. We introduce a family of neural encoder-decoder models for Visual Dialog with 3 encoders (Late Fusion, Hierarchical Recurrent Encoder and Memory Network) and 2 decoders (generative and discriminative), which outperform a number of sophisticated baselines. We propose a retrieval-based evaluation protocol for Visual Dialog where the AI agent is asked to sort a set of candidate answers and evaluated on metrics such as mean-reciprocal-rank of human response. We quantify gap between machine and human performance on the Visual Dialog task via human studies. Our dataset, code, and trained models will be released publicly at https://visualdialog.org. Putting it all together, we demonstrate the first visual chatbot!.

A number of recent works have proposed techniques for end-to-end learning of communication protocols among cooperative multi-agent populations, and have simultaneously found the emergence of grounded human-interpretable language in the protocols developed by the agents, learned without any human supervision!In this paper, using a Task & Talk reference game between two agents as a testbed, we present a sequence of 'negative' results culminating in a 'positive' one -showing that while most agent-invented languages are effective (i.e.achieve near-perfect task rewards), they are decidedly not interpretable or compositional.In essence, we find that natural language does not emerge 'naturally', despite the semblance of ease of natural-language-emergence that one may gather from recent literature.We discuss how it is possible to coax the invented languages to become more and more human-like and compositional by increasing restrictions on how two agents may communicate.

Gaussian belief propagation (BP) has been widely used for distributed estimation in large-scale networks such as the smart grid, communication networks, and social networks, where local meansurements/observations are scattered over a wide geographical area. However, the convergence of Gaussian BP is still an open issue. In this paper, we consider the convergence of Gaussian BP, focusing in particular on the convergence of the information matrix. We show analytically that the exchanged message information matrix converges for arbitrary positive semidefinite initial value, and its distance to the unique positive definite limit matrix decreases exponentially fast.

Design of filters for graph signal processing benefits from knowledge of the spectral decomposition of matrices that encode graphs, such as the adjacency matrix and the Laplacian matrix, used to define the shift operator. For shift matrices with real eigenvalues, which arise for symmetric graphs, the empirical spectral distribution captures the eigenvalue locations. Under realistic circumstances, stochastic influences often affect the network structure and, consequently, the shift matrix empirical spectral distribution. Nevertheless, deterministic functions may often be found to approximate the asymptotic behavior of empirical spectral distributions of random matrices. This paper uses stochastic canonical equation methods developed by Girko to derive such deterministic equivalent distributions for the empirical spectral distributions of random graphs formed by structured, non-uniform percolation of a D-dimensional lattice supergraph. Included simulations demonstrate the results for sample parameters.

We introduce the first goal-driven training for visual question answering and dialog agents. Specifically, we pose a cooperative `image guessing' game between two agents - Q-BOT and A-BOT- who communicate in natural language dialog so that Q-BOT can select an unseen image from a lineup of images. We use deep reinforcement learning (RL) to learn the policies of these agents end-to-end - from pixels to multi-agent multi-round dialog to game reward.,,We demonstrate two experimental results.,,First, as a `sanity check' demonstration of pure RL (from scratch), we show results on a synthetic world, where the agents communicate in ungrounded vocabularies, i.e., symbols with no pre-specified meanings (X, Y, Z). We find that two bots invent their own communication protocol and start using certain symbols to ask/answer about certain visual attributes (shape/color/style). Thus, we demonstrate the emergence of grounded language and communication among `visual' dialog agents with no human supervision.,,Second, we conduct large-scale real-image experiments on the VisDial dataset [5], where we pretrain on dialog data with supervised learning (SL) and show that the RL finetuned agents significantly outperform supervised pretraining. Interestingly, the RL Q-BOT learns to ask questions that A-BOT is good at, ultimately resulting in more informative dialog and a better team.

In this paper, we develop deep spatio-temporal neural networks to sequentially count vehicles from low quality videos captured by city cameras (citycams). Citycam videos have low resolution, low frame rate, high occlusion and large perspective, making most existing methods lose their efficacy. To overcome limitations of existing methods and incorporate the temporal information of traffic video, we design a novel FCN-rLSTM network to jointly estimate vehicle density and vehicle count by connecting fully convolutional neural networks (FCN) with long short term memory networks (LSTM) in a residual learning fashion. Such design leverages the strengths of FCN for pixel-level prediction and the strengths of LSTM for learning complex temporal dynamics. The residual learning connection reformulates the vehicle count regression as learning residual functions with reference to the sum of densities in each frame, which significantly accelerates the training of networks. To preserve feature map resolution, we propose a Hyper-Atrous combination to integrate atrous convolution in FCN and combine feature maps of different convolution layers. FCN-rLSTM enables refined feature representation and a novel end-to-end trainable mapping from pixels to vehicle count. We extensively evaluated the proposed method on different counting tasks with three datasets, with experimental results demonstrating their effectiveness and robustness. In particular, FCN-rLSTM reduces the mean absolute error (MAE) from 5.31 to 4.21 on TRANCOS; and reduces the MAE from 2.74 to 1.53 on WebCamT. Training process is accelerated by 5 times on average.

Hierarchical Bayesian models often capture distributions over a very large number of distinct atoms. The need for these models arises when organizing huge amount of unsupervised data, for instance, features extracted using deep convnets that can be exploited to organize abundant unlabeled images. Inference for hierarchical Bayesian models in such cases can be rather nontrivial, leading to approximate approaches. In this work, we propose Canopy, a sampler based on Cover Trees that is exact, has guaranteed runtime logarithmic in the number of atoms, and is provably polynomial in the inherent dimensionality of the underlying parameter space. In other words, the algorithm is as fast as search over a hierarchical data structure. We provide theory for Canopy and demonstrate its effectiveness on both synthetic and real datasets, consisting of over 100 million images.

We seek to extract and explore statistics that characterize New York City traffic flows based on 700 million taxi trips in the 2010-2013 New York City taxi data. This paper presents a two-part solution for intensive computation: space and time design considerations for estimating taxi trajectories with Dijkstra's algorithm, and job parallelization and scheduling with HTCondor. Our contribution is to present a solution that reduces execution time from 3,000 days to less than a day with detailed analysis of the necessary design decisions.

We propose a model to learn visually grounded word embeddings (vis-w2v) to capture visual notions of semantic relatedness. While word embeddings trained using text have been extremely successful, they cannot uncover notions of semantic relatedness implicit in our visual world. For instance, although "eats" and "stares at" seem unrelated in text, they share semantics visually. When people are eating something, they also tend to stare at the food. Grounding diverse relations like "eats" and "stares at" into vision remains challenging, despite recent progress in vision. We note that the visual grounding of words depends on semantics, and not the literal pixels. We thus use abstract scenes created from clipart to provide the visual grounding. We find that the embeddings we learn capture fine-grained, visually grounded notions of semantic relatedness. We show improvements over text-only word embeddings (word2vec) on three tasks: common-sense assertion classification, visual paraphrasing and text-based image retrieval. Our code and datasets are available online.

A class of models for describing sets of time series generated by interacting agents using directed, weighted graphs is introduced. A computationally tractable algorithm for estimating the graph adjacency matrix of this model from observed time series data is presented. The performance guarantees of this algorithm for prediction are outlined under several assumptions on the properties of the dynamics of the system of agents and on the true values of the parameters. These guarantees are tested empirically through simulation studies using several random graph models.

Finding densely connected subgraphs, also called communities, in networks are of interest for many applications. In previous work, we showed an optimization method for efficiently finding subgraphs denser than the overall network [1]. This result is derived from our studies of network processes, dynamical processes that model interactions between individual agents in networks (i.e., spread of infection or cascading failures). In this paper, we prove that these subgraphs are also unique in the sense that there are no other subgraphs in the network isomorphic to these subgraphs.

We study cyber-physical systems subject to dynamic sensor attacks, relating them to the system's strong observability. First, we find necessary and sufficient conditions for an attacker to create a dynamically undetectable sensor attack and relate these conditions to properties of the system dynamics eigenvectors. Next, we provide an index that gives the minimum number of sensors that must be attacked in order for an attack to be undetectable. Finally, we illustrate our results with a numerical example on the Quadruple Tank Process.

This paper presents a computationally tractable algorithm for estimating the graph structure of graph signals is presented. The algorithm is demonstrated on simulated and real network time series datasets, and the performance of the new method is compared to that of related methods for estimating graph structure. The adjacency matrices estimated using the new method are shown to be close to the true graph in the simulated data and consistent with prior physical knowledge in the real dataset.

Traffic flow in a city is a rich source of information about the city. Cities are being instrumented with video cameras. They can potentially generate continuously large datasets to be processed (big data). This paper reports on our current work to detect traffic flow from an on-line low quality, low frame rate city video camera. The paper details a pipeline of four main steps - background subtraction, scene geometry, car detection, and car counting, and it illustrates results obtained with processing video from a single camera.

This paper studies the convergence of the estimation error process and the characterization of the corresponding invariant measure in distributed Kalman filtering for potentially unstable and large linear dynamic systems. A gossip network protocol termed modified gossip interactive Kalman filtering (M-GIKF) is proposed, where sensors exchange their filtered states (estimates and error covariances) and propagate their observations via intersensor communications of rate$\bar {\gamma }$;$\bar {\gamma }$is defined as the averaged number of intersensor message passages per signal evolution epoch. The filtered states are interpreted as stochastic particles swapped through local interaction. This paper shows that the conditional estimation error covariance sequence at each sensor under M-GIKF evolves as a random Riccati equation (RRE) with Markov modulated switching. By formulating the RRE as a random dynamical system, it is shown that the network achieves weak consensus, i.e., the conditional estimation error covariance at a randomly selected sensor converges weakly (in distribution) to a unique invariant measure. Further, it is proved that as$\bar {\gamma } \rightarrow \infty $this invariant measure satisfies the large deviation (LD) upper and lower bounds, implying that this measure converges exponentially fast (in probability) to the Dirac measure$\delta _{P^{*}}$, where$P^{*}$is the stable error covariance of the centralized (Kalman) filtering setup. The LD results answer a fundamental question on how to quantify the rate at which the distributed scheme approaches the centralized performance as the intersensor communication rate increases.

We propose a novel recovery algorithm for signals with complex, irregular structure that is commonly represented by graphs. Our approach is a generalization of the signal inpainting technique from classical signal processing. We formulate corresponding minimization problems and demonstrate that in many cases they have closed-form solutions. We discuss a relation of the proposed approach to regression, provide an upper bound on the error for our algorithm and compare the proposed technique with other existing algorithms on real-world datasets.

Anomaly detection on dynamic real-world networks such as large caller networks and online social networks is a very difficult problem, analogous to looking for a needle in a haystack. This paper considers detecting churners in a 3.7 million mobile phone network. The two main issues are designing fast and efficient features and classifiers. We discuss both in this paper. We associate every caller in the network with an activity vector and an affinity graph, and our features are derived from activity levels computed from subgraphs of the affinity graph. These features reflect the graph-dependent nature of the problem. To compute these networks expeditiously, we extend as integral affinity graphs the concept of integral images. Our anomaly classifier is a cascaded classifier with stages that combine naive Bayes and decision tree classifiers. Simulations with a 3.7 million cell phone user network illustrate an anomaly classifier that reaches a false alarm rate of 0.8% with a churn detection rate of 71%.

One of the largest challenges for multichannel localization systems is developing methodologies that are robust to interference. Unlike noise, interference is not random and often has characteristics resembling the true signals of interest. Interference often originates from multipath propagation, jamming signals, or other sources. In this paper, we demonstrate that we can significantly improve localization performance in the presence of interference through the use of a random sensor topology and matched field processing. To show this, we apply concepts and results from random matrix theory and compressed sensing. We demonstrate theoretically that random sensor topologies allow us to achieve performance characteristics similar to those of random noise. Specifically, we show that the localization performance improves, with a high probability, at a rate proportional to the number of sensors in the system. We verify these results through simulation.

We consider distributed optimization where N nodes in a generic, connected network minimize the sum of their individual, locally known, convex costs. Existing literature proposes distributed gradient-like methods that are attractive due to computationally cheap iterations and provable resilience to random inter-node communication failures, but such methods have slow theoretical and empirical convergence rates. Building from the centralized Nesterov gradient methods, we propose accelerated distributed gradient-like methods and establish that they achieve strictly faster rates than existing distributed methods. At the same time, our methods maintain cheap iterations and resilience to random communication failures. Specifically, for convex, differentiable local costs with Lipschitz continuous and bounded derivative, we establish (with respect to the cost function optimality) convergence in probability and convergence rates in expectation and in second moment.

We propose a new framework for distributed computation of average consensus. The presented framework leads to a systematic design of iterative algorithms that compute the consensus exactly, are guaranteed to converge in finite time, are computationally efficient, and require no online memory. We demonstrate that our approach is applicable to a broad class of networks. For remaining networks, our framework leads to the construction of approximating algorithms for consensus that are also guaranteed to compute in finite time. Our approach is inspired by graph filters introduced by the theoretical framework of signal processing on graphs.

We model a SIS (susceptible-infected-susceptible) epidemics over a static, finite-sized network as a continuous-time Markov process using the scaled SIS epidemics model. In our previous work, we derived the closed form description of the equilibrium distribution that explicitly accounts for the network topology and showed that the most probable equilibrium state demonstrates threshold behavior. In this paper, we will show how subgraph structures in the network topology impact the most probable state of the long run behavior of a SIS epidemics (i.e., stochastic diffusion process) over any static, finite-sized, network.

This paper studies the problem of distributed parameter estimation in multiagent networks with exponential family observation statistics. A certainty-equivalence type distributed estimator of the consensus-plus-innovations form is proposed in which, at each observation sampling epoch, agents update their local parameter estimates by appropriately combining the data received from their neighbors and the locally sensed new information (innovation). Under global observability of the networked sensing model, i.e., the ability to distinguish between different instances of the parameter value based on the joint observation statistics, and mean connectivity of the inter-agent communication network, the proposed estimator is shown to yield consistent parameter estimates at each network agent. Further, it is shown that the distributed estimator is asymptotically efficient, in that, the asymptotic covariances of the agent estimates coincide with that of the optimal centralized estimator, i.e., the inverse of the centralized Fisher information rate. From a technical viewpoint, the proposed distributed estimator leads to non-Markovian mixed time-scale stochastic recursions and the analytical methods developed in this paper contribute to the general theory of distributed stochastic approximation.

In this paper, we consider the problem of state estimation of a dynamical system in a multi-agent network. The agents are sparsely connected and each of them observes a strict subset of the state vector. The distributed algorithm that we propose enables each agent to estimate any arbitrary linear dynamical system with bounded mean-squared error. To achieve this, the ratio of the algebraic connectivity and the largest eigenvalue of the graph Laplacian has to be larger than a lower bound determined by the spectral radius of the system's dynamics matrix. This extends the notion of Network Tracking Capacity introduced by other authors in prior work. We accomplish this by introducing a new class of estimation algorithm of dynamical systems that, besides a (consensus + innovations) term, also includes consensus on the innovations.

Online social networks and the World Wide Web lead to large underlying graphs that might not be completely known because of their size. To compute reliable statistics, we have to resort to sampling the network. In this paper, we investigate four network sampling methods to estimate the network degree distribution and the so-called biased degree distribution of a 3.7 million wireless subscriber network. We measure the quality of our estimates of the degree distributions by using the Kolmogorov-Smirnov statistic. Among all four sampling methods, node sampling yields Pareto optimal sample sizes in terms of the Kolomogorov-Smirnov statistic for the degree distribution, while node-by-edge sampling yields optimal sample sizes for the biased distribution. We also find that random walk sampling performs better than the Metropolis-Hastings random walk.

Matched field processing is a powerful tool for accurately localizing targets in dispersive media. However, matched field processing requires a precise model of the medium under test. In underwater acoustics, where matched field processing has been extensively studied, authors often resort to extremely detailed numerical models of the propagation medium, which are computationally expensive and impractical for many applications. As an alternative, this paper uses convex sparse recovery techniques to construct, directly from measured data, an accurate model of a plate medium based on its dispersion characteristics. From this data-driven model, the Green's function between two points can be readily predicted. We demonstrate the effectiveness of this model by localizing a source in a dispersive plate medium. The results visually illustrate our approach to significantly improve localization accuracy and reduce artifacts when compared to a conventional narrowband technique.

We propose a novel discrete signal processing framework for structured datasets that arise from social, economic, biological, and physical networks. Our framework extends traditional discrete signal processing theory to datasets with complex structure that can be represented by graphs, so that data elements are indexed by graph nodes and relations between elements are represented by weighted graph edges. We interpret such datasets as signals on graphs, introduce the concept of graph filters for processing such signals, and discuss important properties of graph filters, including linearity, shift-invariance, and invertibility. We then demonstrate the application of graph filters to data classification by demonstrating that a classifier can be interpreted as an adaptive graph filter. Our experiments demonstrate that the proposed approach achieves high classification accuracy.

We propose a novel discrete signal processing framework for the representation and analysis of datasets with complex structure. Such datasets arise in many social, economic, biological, and physical networks. Our framework extends traditional discrete signal processing theory to structured datasets by viewing them as signals represented by graphs, so that signal coefficients are indexed by graph nodes and relations between them are represented by weighted graph edges. We discuss the notions of signals and filters on graphs, and define the concepts of the spectrum and Fourier transform for graph signals. We demonstrate their relation to the generalized eigenvector basis of the graph adjacency matrix and study their properties. As a potential application of the graph Fourier transform, we consider the efficient representation of structured data that utilizes the sparseness of graph signals in the frequency domain.

Current research is interested in identifying how topology impacts epidemics in networks. In this paper, we model SIS (susceptible-infected-susceptible) epidemics as a continuous-time Markov process and for which we can obtain a closed form description of the equilibrium distribution. Such distribution describes the long-run behavior of the epidemics. The adjacency matrix of the network topology is reflected explicitly in the formulation of the equilibrium distribution. Secondly, we are interested in analyzing the model in the regime where the topology dependent infection process opposes the topology independent healing process. Specifically, how will network topology affect the most probable long-run network state? We show that for k-regular graph topologies, the most probable network state transitions from the state where everyone is healthy to one where everyone is infected at a threshold that depends on k but not on the size of the graph.

We present the complex Double Gaussian distribution that describes the product of two independent, non-zero mean, complex Gaussian random variables, a doubly-infinite summation of terms. This distribution is useful in a wide array of problems. We discuss its application to blind TR detection systems by deriving the Neyman-Pearson optimal detector when the channel is modeled as the product of two independent complex Gaussian random variables, such as in a Time Reversal scenario. We show that near-optimal detection performance can be achieved with as few as 25 summation terms. Theoretical analysis and Monte Carlo simulations illustrate our results.

We study the use of distributed average consensus and compressed sensing to perform decentralized estimation of a field measured by networked sensors. We examine field reconstruction of multiple acoustic sources from isotropic magnitude measurements. Compressed projections of global network observations are spread throughout the network using consensus, after which all nodes may invert the source field using ℓ1recovery methods. To approximate the problem as a discrete linear system, the space of source locations is quantized, introducing model error. We propose a model-robust adaptation to basis pursuit to control for the error arising from the spatial quantization. We show conditions for stability of the robust estimator, providing bounds on the reconstruction error based on perturbation constants, source magnitudes, and mutual coherence. Experiments show that the two types of robust estimators successfully address infeasibility and consistency issues that arise in basis pursuit for spatially quantized acoustic sources.

We are interested in investigating the spread of contagion in a network, G, which describes the interactions between the agents in the system. The topology of this network is often neglected due to the assumption that each agent is connected with every other agents; this means that the network topology is a complete graph. While this allows for certain simplifications in the analysis, we fail to gain insight on the diffusion process for non-complete network topology. In this paper, we offer a continuous-time Markov chain infection model that explicitly accounts for the network topology, be it complete or non-complete. Although we characterize our process using parameters from epidemiology, our approach can be applied to many application domains. We will show how to generate the infinitesimal matrix that describes the evolution of this process for any topology. We also develop a general methodology to solve for the equilibrium distribution by considering symmetries in G. Our results show that network topologies have dramatic effect on the spread of infections.

As feature-based image matching is applied to increasing larger scale problems, it becomes necessary to match features across increasingly larger databases. Current approaches are able to conduct such feature matching, but are not flexible enough to be applied to databases that may grow at runtime. As a solution to this problem, we present the Iterative k-d tree that allows for the insertion of new features into the database at any time and stores information about previous queries so that previously searched features can updated without having to be re-run. This new data structure was successfully used in the Spry algorithm to achieve better and faster results in situations where there is large movement between images. Additionally, experimental results show that the proposed method is significantly faster than the current state of the art algorithms when the database of features grows at runtime.

Monitoring electricity consumption in the home is an important way to help reduce energy usage and Non-Intrusive Load Monitoring (NILM) techniques are a promising approach to obtain estimates of the electrical power consumption of individual appliances from aggregate measurements of voltage and/or current in the distribution system. In this paper, we discuss event detection algorithms used in the NILM literature and propose new metrics for evaluating them. In particular, we introduce metrics that incorporate information contained in the power signal instead of strict detection rates. We show that this information is important for NILM applications with the goal of improving appliance energy disaggregation. Our work was carried out on a publicly-available week-long dataset of real residential power usage.

The paper studies distributed static parameter (vector) estimation in sensor networks with nonlinear observation models and noisy intersensor communication. It introduces 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, theNU(with its linear counterpartLU) and theNLU. Their update rule combines a consensus step (where each sensor updates the state by weight averaging it with its neighbors' states) and an innovation step (where each sensor processes its local current observation). This makes the three algorithms of the consensus + innovations type, very different from traditional consensus. This paper proves consistency (all sensors reach consensus almost surely and converge to the true parameter value), efficiency, and asymptotic unbiasedness. ForLUandNU, it proves asymptotic normality and provides convergence rate guarantees. The three algorithms are characterized by appropriately chosen decaying weight sequences. AlgorithmsLUandNUare analyzed in the framework of stochastic approximation theory; algorithmNLUexhibits mixed time-scale behavior and biased perturbations, and its analysis requires a different approach that is developed in this paper.

We show that distributed detection over random networks, or using a random protocol, e.g., of the gossip type, is asymptotically optimal, if the rate of information flow across the random network is large enough. Asymptotic optimality is in the sense of Chernoff information; in other words, we determine when the exponential rate of decay of the error probability for distributed detection is the best possible and equal to the rate of decay of the best centralized detector. The rate of information flow is defined by |log r|, where r is the second largest eigenvalue of the second moment of the random, consensus weight matrix. We quantify interesting tradeoffs in distributed detection, between the rate of information flow and the achievable detection performance.

The paper studies the convergence properties of the estimation error processes in distributed Kalman filtering for potentially unstable linear dynamical systems. In particular, it is shown that, in a weakly connected communication network, there exist (randomized) gossip based information dissemination schemes leading to a stochastically bounded estimation error at each sensor for any non-zero rate γ̄ of inter-sensor communication (the rate γ̄ is defined to be the average number of inter-sensor communications per signal evolution epoch). A gossip-based information exchange protocol, the M-GIKF, is presented, in which sensors exchange estimates and aggregate observations at a rate γ̄ > 0, leading to desired convergence properties. Under the assumption of global (centralized) detectability of the signal/observation model (necessary for a centralized estimator having access to all sensor observations at all times to yield bounded estimation error), it is shown that the distributed M-GIKF leads to a stochastically bounded estimation error at each sensor. The conditional estimation error covariance sequence at each sensor is shown to evolve as a random Riccati equation (RRE) with Markov modulated switching. The RRE is analyzed through a random dynamical system (RDS) formulation, and the asymptotic estimation error at each sensor is characterized in terms of an associated invariant measure µγ̄ of the RDS.

Networks of biological agents (for example, ants, bees, fish, birds) and complex man-made cyberphysical infrastructures (for example, the power grid, transportation networks) exhibit one thing in common - the emergence of collective global phenomena from apparently random local interactions. This paper proposes a distributed graphical model of interacting agents (a stochastic network type model) and studies its appropriate asymptotics. We show that metastability may occur - i.e., under certain conditions, the agents act in synchrony and may exhibit collectively possibly different stable equilibria - these are the global emergent behaviors of the cloud of interacting agents. We characterize these global behaviors as synchronous fixed points determined from ordinary differential equations that arise as mean field limits of the adopted stochastic model.

Detection of targets in complex environments is of importance in both radar and sonar applications. Recent work has shown that the use of Time Reversal (TR) techniques improves the performance of systems operating in deterministic channels with a significant multipath return. This paper extends those results to stationary random channels with significant multipath. We develop a TR-based approach and derive the Likelihood Ratio Test (LRT) for this approach. We compare this TR-LRT to an LRT derived through a “water filling” approach. We derive theoretical performance curves for the water filling LRT, and evaluate both the water filling and TR detectors with Monte Carlo simulations. For the scenarios tested, we show that TR achieves an SNR gain of 1–2dB over the water filling detector.

Traditional binary hypothesis testing relies on the precise knowledge of the probability density of an observed random vector conditioned on each hypothesis. However, for many applications, these densities can only be approximated due to limited training data or dynamic changes affecting the observed signal. A classical approach to handle such scenarios of imprecise knowledge is via minimax robust hypothesis testing (RHT), where a test is designed to minimize the worst case performance for all models in the vicinity of the approximated imprecise density. Despite the promise of RHT for robust classification problems, its applications have remained rather limited because RHT in its native form does not scale gracefully with the dimension of the observed random vector. In this paper, we use approximations via probabilistic graphical models, in particular block-tree graphs, to enable computationally tractable algorithms for realizing RHT on high-dimensional data. We quantify the reductions in computational complexity. Experimental results on simulated data and a target recognition problem show minimal loss over a true RHT.

Box filters have been used to speed up many computation-intensive operations in Image Processing and Computer Vision. They have the advantage of being fast to compute, but their adoption has been hampered by the fact that they present serious restrictions to filter construction. This paper relaxes these restrictions by presenting a method for automatically approximating an arbitrary 2-D filter by a box filter. To develop our method, we first formulate the approximation as a minimization problem and show that it is possible to find a closed form solution to a subset of the parameters of the box filter. To solve for the remaining parameters of the approximation, we develop two algorithms: Exhaustive Search for small filters and Directed Search for large filters. Experimental results show the validity of the proposed method.

Graphical model selection, where the goal is to estimate the graph underlying a distribution, is known to be an NP-hard problem. An important issue is to study theoretical limits on the performance of graphical model selection algorithms. In particular, given parameters of the underlying distribution, we want to find a lower bound on the number of samples required for accurate graph estimation. When deriving these theoretical bounds, it is common to treat the learning problem as a communication problem where the observations correspond to noisy messages and the decoding problem infers the graph from the observations. Current analysis of graphical model selection algorithms is limited to studying graph estimators that output a unique graph. In this paper, we consider graph estimators that output a set of graphs, leading to set-based graphical model selection (SB-GMS). This has connections to list-decoding where a decoder outputs a list of possible codewords instead of a single codeword. Our main contribution is to derive necessary conditions for accurate SB-GMS for various classes of graphical models and show reduction in the number of samples required for consistent estimation. Further, we derive necessary conditions on the cardinality of the set-based estimates given graph parameters.

We present telescoping recursive representations for both continuous and discrete indexed noncausal Gauss-Markov random fields. Our recursions start at the boundary (a hypersurface in ) and telescope inwards. For example, for images, the telescoping representation reduce recursions from to , 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.

We consider the weight design problem for the consensus algorithm under a finite time horizon. We assume that the underlying network is random where the links fail at each iteration with certain probability and the link failures can be spatially correlated. We formulate a family of weight design criteria (objective functions) that minimize n, n = 1, …,N (out of N possible) largest (slowest) eigenvalues of the matrix that describes the mean squared consensus error dynamics. We show that the objective functions are convex; hence, globally optimal weights (with respect to the design criteria) can be efficiently obtained. Numerical examples on large scale, sparse random networks with spatially correlated link failures show that: 1) weights obtained according to our criteria lead to significantly faster convergence than the choices available in the literature; 2) different design criteria that corresponds to different n, exhibits very interesting tradeoffs: faster transient performance leads to slower long time run performance and vice versa. Thus, n is a valuable degree of freedom and can be appropriately selected for the given time horizon.

This paper is concerned with a moving target detection using time reversal in dense multipath environments. We show that the Doppler shift in the time reversal re-transmission simplifies the detector design, yet still achieves the focusing effect. Thus, the Doppler diversity is utilized to achieve high target detectability by time reversal.

In this paper, we study the synthesis problem in linear high dimensional consensus (HDC) algorithms for large-scale networks. In HDC, we partition the network nodes into leaders and followers. Each follower updates its state as a linear combination of its neighboring states, whereas, the state of the leaders remains fixed. Hence, linear HDC can be thought of as a linear time-invariant (LTI) system. The synthesis problem for this LTI system is to design its parameters such that the system converges to a desired pre-specified state. We cast this synthesis problem as a multi-objective optimization problem (MOP) to which we apply Pareto-optimality. We show that the optimal solution of the synthesis problem is a Pareto-optimal (P.O.) solution of the MOP. We then provide a graphical method to extract the optimal MOP solution from the set of all P.O. solutions. Casting the synthesis problem as an MOP naturally lends itself to interesting performance vs speed trade-offs in HDC.

Images are well modeled as noncausal random fields, i.e., fields where a pixel value depends on say, its four nearest neighbors. This noncausality creates problems when processing images since it preludes the application of recursive estimators, like the Kalman filter. This paper presents a new approach that allows the application of optimal Kalman filtering to random fields, while preserving the noncausality of the image random field model. The recursions in our approach are telescoping: they initiate at the periphery (or boundary) of the random field and telescope inwards. We show how to apply the new optimal recursive Kalman filter to enhancement of noisy images.

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 paper 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.

In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method ¿label-and-decide.¿ We prove that the ¿label-and-decide¿ method is applicable to Tanner graphs with a hierarchical structure-pseudo-trees-and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs-the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm-the ¿label-decide-recompute.¿ Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than4 ·M·((k¿- 1), whereMis the number of independent rows in the parity-check matrix andk¿represents the mean row weight of the parity-check matrix.

This paper proposes modeling the rapidly evolving energy systems as cyber-based physical systems. It introduces a novel cyber-based dynamical model whose mathematical description depends on the cyber technologies supporting the physical system. This paper discusses how such a model can be used to ensure full observability through a cooperative information exchange among its components; this is achieved without requiring local observability of the system components. This paper also shows how this cyber-physical model is used to develop interactive protocols between the controllers embedded within the system layers and the network operator. Our approach leads to a synergistic framework for model-based sensing and control of future energy systems. The newly introduced cyber-physical model has network structure-preserving properties that are key to effective distributed decision making. The aggregate load modeling that we develop using data mining techniques and novel sensing technologies facilitates operations of complex electric power systems.

A botnet is a large network of bots that are under the control of a bot herder. Botnets have become a significant threat to network communications and applications. Botnets' execution relies on Command and Control (C2) communication channels traffic, which occur prior to the attack activity itself. Therefore, the detection of C2 communication channels traffic enables the detection of the members of a botnet before any target is attacked. We study the periodic behavior of C2 traffic that is caused by the pre-programmed behavior of bots to check for and download updates every T seconds. We use this periodic behavior of the C2 traffic to detect bots. This involves evaluating the periodogram of traffic in the monitored network. Then applying Walker's large sample test to the maximum ordinate of the periodogram to determine if it is due to a high periodic component in the traffic or not, and, if it is, then it is bot traffic. We apply the test to a TinyP2P botnet generated by SLINGbot and show a strong periodic behavior in the bots traffic. We study the effect of the period's length and duty cycle of the C2 traffic on the test performance and find that it increases with the increase of the duty cycle and/or the decrease of the period length. We analyze the test's performance in the presence of injected random noise traffic and develop a lower and an upper bounds for the test performance.

Conventional SAR images under rich scattering suffer degradation because of ghost images caused by multipath propagation. In this paper, we develop a time reversal SAR (TR-SAR) imaging algorithm for extended (nonpoint-like) targets in rich multipath scattering. We test the TR-SAR algorithm using experimental electromagnetic data collected in a laboratory environment where the extended target (a galvanized steel sheet) is surrounded by a large amount of PVC rods. Our experiments show that the collected EM data in frequency and aperture after TR-SAR processing produces a higher resolution, cleaner target map compared with conventional SAR images.

The paper considers the algorithm NLU for distributed (vector) parameter estimation in sensor networks, where, the local observation models are nonlinear, and inter-sensor communication is imperfect, in the sense, that the network links fail randomly and inter-sensor transmission is quantized. The paper introduces the class of separably estimable observation models, which generalizes the notion of observability in centralized linear estimation to distributed nonlinear estimation. We show that the NLU algorithm leads to consistent and asymptotically unbiased estimates of the parameter at each sensor for separably estimable observation models. In other words, the sensors reach consensus almost sure (a.s.) to the true parameter value. The algorithm NLU is a mixed time scale stochastic algorithm, characterized by two different decreasing weight sequences associated with the consensus and innovation updates. The analysis of the NLU algorithm, thus, does not follow under the purview of standard stochastic approximation, making the analysis developed in the paper of independent theoretical interest.

This paper introduces higher dimensional consensus, a framework to capture a number of different, but, related distributed, iterative, linear algorithms of interest in sensor networks. We show that, by suitably choosing the iteration matrix of the higher dimensional consensus, we can capture, besides the standard average-consensus, a broad range of applications, including sensor localization, leader-follower, and distributed Jacobi algorithm. We work with the concept of anchors and explicitly derive the consensus subspace and provide the dimension of the limiting state of the sensors.

We study the inversion of a random field from pointwise measurements collected by a sensor network. We assume that the field has a sparse representation in a known basis. To illustrate the approach, consider the inversion of an acoustic field created by the superposition of a discrete number of propagating noisy acoustic sources. Our method combines compressed sensing (sparse reconstruction by lscr1-constrained optimization) with distributed average consensus (mixing the pointwise sensor measurements by local communication among the sensors). The paper describes the approach and demonstrates its good performance with synthetic data for several scenarios of practical interest.

We address the problem of shape based classification. We interpret the shape of an object as a probability distribution governing the location of the points of the object. An image of the object, represented as an arbitrary set of unlabeled points, corresponds to a random drawing from the shape probability distribution and can thus be analyzed as an empirical distribution. Using this framework, classification of shapes is robust to the number of points in the image and there is no need to solve the correspondence problem when comparing two images. The framework allows us to estimate geometrical transformations between images in a statistically meaningful way using maximum likelihood. We formulate the decision problem associated with shape classification as a hypothesis test for which we can characterize the performance. We particularize this framework to two-dimensional shapes related by an affine transformation. Under this assumption, we develop a descriptor invariant to affine movement, permutations, and sampling density, and robust to noise, occlusion, and reasonable non-linear deformations. Experimental results demonstrate the quality of our approach.

In this paper, we study continuous index Gaussian reciprocal processes (Grp's) (or two-point boundary valued processes) with Dirichlet boundary conditions. Our main contributions are 1) deriving first order white noise driven representations from the second order correlated noise driven representations of Grp's given by Krener, Frezza, and Levy; 2) deriving Kalman-Bucy like recursive filtering equations for Grp's with continuous indices; and 3) deriving recursive smoothing equations for Grp's with continuous indices.

Botnets pose a significant threat to network-based applications and communications; it is believed that 16-25% of the computers connected to the Internet are members of a botnet. The detection of botnets is essential to prevent further damages. We approach this problem by monitoring the command and control (C2) communication traffic, as this reveals the botnet structure before any real harm is caused.We observe that C2 traffic exhibits a repeated pattern behavior. This is due to the nature of the pre-programmed behavior of bots. We explore this behavior and look for periodic components in C2 traffic. We use periodograms to study the periodic behavior, and apply Walker's large sample test to detect whether the traffic has a significant periodic component or not, and, if it does, then it is bot traffic. This test is independent of the structure and communication protocol used in the botnet, and does not require any a priori knowledge of a certain botnet behavior. Since we only look at the aggregate traffic behavior, it is also more scalable than other techniques that examine individual packets or track the communication flows of different hosts.We apply this test to two variants of botnet C2 communication traffic generated by SLINGbot, and show that the traffic in both variants exhibits periodic behavior. We compare the results we get on botnet C2 communication traffic to the ones we get on real traffic that is obtained from a secured enterprise network packet trace.

Multipath effects are significant in urban or indoor communications. Current position location techniques such as TDOA suffer from multipath effects, which reduces the estimation accuracy. In this paper we propose time-reversal in a wireless communication network, where a mobile terminal wants to determine, through feedback, its own position in the request of the base station. The proposed method improves the estimation accuracy and reduces the estimation variance compared with correlation based method. We derive the closed form of the Cramer-Rao bound (CRB) on the time reversal estimation and the correlation estimation, showing that time reversal achieves a smaller CRB than the correlation method. Numerical examples are presented to illustrate the behavior of these bounds.

The paper studies distributed average consensus in sensor networks, when the sensors exchange quantized data at each time step. We show that randomizing the exchanged sensor data by adding a controlled amount of dither results in almost sure (a.s.) convergence of the protocol, if the network is connected. We explicitly characterize the mean-squared error (with respect to the desired consensus average) and show that, by tuning certain parameters associated with the protocol, the mean-squared error can be made arbitrarily small. We study the trade-offs between the rate of convergence and the resulting mean-squared error. The sensor network topology plays an important role in determining the convergence rate of the algorithm. Our approach, based on the convergence of controlled Markov processes, is very generic and can be applied to many other situations of imperfect communication. Finally, we present numerical studies, which verify our theoretical results.

In this paper, we present a distributed algorithm to invert L-banded matrices that are symmetric positive definite (SPD), when the sub-matrices in the band are distributed among several processing nodes. We provide a distributed iterate-collapse inversion (DICI) algorithm that converges, at each node, to the corresponding submatrices in the inverse of the L-banded matrix. The computational complexity of the DICI algorithm to invert an SPD L-banded n x n matrix can be shown at each node to be independent of the size, n, of the matrix. Local information exchange is carried out after each iteration to guarantee convergence. We apply this algorithm to invert the information matrices in a computationally efficient distributed implementation of the Kalman filter and show its application towards inverting arbitrary sparse SPD matrices.

In this paper we address two closely related problems. The first is the object detection problem, i.e., the automatic decision of whether a given image represents a known object or not. The second is the correspondence problem, i.e., the automatic matching of points of an object in two views. In the first problem, we assume object rigidity and model the distortions by a linear shape model. To solve the decision problem, we derive the uniformly most powerful (UMP) hypothesis test that is invariant to the linear shape model. We use the UMP statistic to formulate the correspondence problem in a model invariant framework. We show that it is equivalent to a quadratic maximization on the space of permutation matrices. We derive LASIC, an iterative computationally feasible solution to the quadratic maximization problem for the particular case where the linear shape model is the affine model. Simulations benchmark LASIC against two standard algorithms.

In this paper, we analyze network traffic behavior by decomposing header traffic into control and data planes to study the relationship between the two planes. By computing the cross-correlation between the control and data traffics, we observe a general ‘similar’ behavior between the two planes during normal behavior, and that this similarity is affected during abnormal behaviors. This allows us to focus on abnormal changes in network traffic behavior. We test our approach on the Network Intrusion Dataset provided by the Information Exploration Shootout (IES) project and the 1999 DARPA Intrusion detection Evaluation Dataset from the MIT Lincoln Lab. We find that TCP control and data traffic have high correlation levels during benign normal applications. This correlation is reduced when attacks that affect the aggregate traffic are present in the two datasets.

We overview a library generation framework called Spiral. For the domain of linear transforms, Spiral automatically generates implementations for parallel platforms including SIMD vector extensions, multicore processors, field-programmable gate arrays (FPGAs) and FPGA accelerated processors. The performance of the generated code is competitive with the best available hand-written libraries.

Contrast-enhanced magnetic resonance imaging (MRI) is useful to study the infiltration of cells in vivo. This research adopts ultrasmall superparamagnetic iron oxide (USPIO) particles as contrast agents. USPIO particles administered intravenously can be endocytosed by circulating immune cells, in particular, macrophages. Hence, macrophages are labeled with USPIO particles. When a transplanted heart undergoes rejection, immune cells will infiltrate the allograft. Imaged by T(2)(*)-weighted MRI, USPIO-labeled macrophages display dark pixel intensities. Detecting these labeled cells in the image facilitates the identification of acute heart rejection. This paper develops a classifier to detect the presence of USPIO-labeled macrophages in the myocardium in the framework of spectral graph theory. First, we describe a USPIO-enhanced heart image with a graph. Classification becomes equivalent to partitioning the graph into two disjoint subgraphs. We use the Cheeger constant of the graph as an objective functional to derive the classifier. We represent the classifier as a linear combination of basis functions given from the spectral analysis of the graph Laplacian. Minimization of the Cheeger constant based functional leads to the optimal classifier. Experimental results and comparisons with other methods suggest the feasibility of our approach to study the rejection of hearts imaged by USPIO-enhanced MRI.

We present a domain-specific approach to generate high-performance hardware-software partitioned implementations of the discrete Fourier transform (DFT) in fixed point precision. The partitioning strategy is a heuristic based on the DFT's divide-and-conquer algorithmic structure and fine tuned by the feedback-driven exploration of candidate designs. We have integrated this approach in the Spiral linear-transform code-generation framework to support push-button automatic implementation. We present evaluations of hardware-software DFT implementations running on the embedded PowerPC processor and the reconfigurable fabric of the Xilinx Virtex-II Pro FPGA. In our experiments, the 1D and 2D DFT's FPGA-accelerated libraries exhibit between 2 and 7.5 times higher performance (operations per second) and up to 2.5 times better energy efficiency (operations per Joule) than the software-only version.

In this paper we study the multiple antenna time reversal downlink transmission in an ultra-wideband (UWB) communication system which consists of access points and users. The access point has multiple antennas and the user has a single antenna. We design the UWB beamformer that focuses on the intended user while minimizing its interference on unintended users and eavesdropping access points. We show that the designed UWB beamformer is equivalent to the time reversal focusing and nulling schemes and yields better performance than the conventional delay line wideband beamformer. We verify our results using experimentally measured electromagnetic data in an indoor environment.

We develop time reversal spotlight synthetic aperture radar (TR-SAR) for target focusing and ghost images removal in SAR. Conventional SAR is not designed for imaging targets in a rich scattering environment. In this case, ghost images due to secondary reflections appear in the SAR images. We show in this paper, how, from a rough estimate of the target location obtained from a conventional SAR image and using time reversal, TR-SAR focuses on the target with improved resolution, and reduces or removes ghost images. Verification with experimentally measured electromagnetic data demonstrates the success of TR-SAR.

We study the impact of the topology of a sensor network on distributed average consensus algorithms when the network links fail at random. We derive convergence results. In particular, we determine a sufficient condition for mean-square convergence of the distributed average consensus algorithm in terms of a moment of the distribution of the norm of a function of the network graph Laplacian matrix L (which is a random matrix, because the network links are random.) Further, because the computation of this moment involves costly simulations, we relate the mean-square convergence to the second eigenvalue of the mean Laplacian matrix, λ2(L̅), which is much easier to compute. We derive bounds on the convergence rate of the algorithm, which show that both the expected algebraic connectivity of the network, E[λ2(L)], and λ2(L̅) play an important role in determining the actual convergence rate. Specifically, larger values of E[λ2(L)] or λ2(L̅) lead to better convergence rates. Finally, we provide numerical studies that verify the analytical results.

When the scene background is known and the intensity of moving objects contrasts with the intensity of the background, the objects are easily captured by exploiting occlusion, e.g., background-subtraction. However, when processing general scenes, the background is not known and researchers have mostly attempted to segment moving objects by using motion cues rather than occlusion. Since motion can only be accurately computed at highly textured regions, current motion segmentation methods either fail to segment low textured objects, or require expensive regularization techniques. We present a computationally simple algorithm and test it with segmentation of moving objects in low texture / low contrast videos that are obtained in low-light scenes. The images in the sequence are modeled taking into account the rigidity of the moving object and the occlusion of the background. We formulate the problem as the minimization of a penalized likelihood cost. Relaxation of the weight of the penalty term leads to a simple solution to the nonlinear minimization. We describe experiments that illustrate the good performance of our method.

This paper develops a classification algorithm in the framework of spectral graph theory where the underlying manifold of a high dimensional data set is described by a graph. The classification on the data is performed on the graph. The classifier optimizes an objective functional that combines prior information with the Cheeger constant. We interpret this approach as a regularized version of the Cheeger constant based classifier that we introduced recently. Our derivation shows that Cheeger regularization removes noise like a Laplacian based classifier but preserves better sharp boundaries needed for class separation. Experimental results show good performance of our proposed approach for classification applications.

Microwave radiation is well known as a diagnostic imaging method for many medical applications, for example, early stage breast cancer detection. Microwave detection of breast tumors is a non-ionising, potentially low cost, in vivo modality that relies on the dielectric contrast between healthy and malignant breast tissues. The scattering environment in a breast often appears to be inhomogeneous due to changing dielectric properties of the breast tissues. Time reversal (TR) is an adaptive waveform transmission scheme that utilizes the rich scattering medium to best match to the target response. In this paper, we develop the microwave time reversal beamformer for breast tumor detection. The TR beamforming scheme is examined based upon a breast model using the two-dimensional finite-difference time-domain (FDTD) method. We show that time reversal microwave beamforming is a more robust, higher resolution imaging scheme than conventional beamforming schemes.

We consider turbo-structured low-density parity-check (TS-LDPC) codes-structured regular codes whose Tanner graph is composed of two trees connected by an interleaver. TS-LDPC codes with good girth properties are easy to construct: careful design of the interleaver component prevents short cycles of any desired length in its Tanner graph. We present algorithms to construct TS-LDPC codes with arbitrary column weight jges2 and row weight k and arbitrary girth g. We develop a linear complexity encoding algorithm for a type of TS-LDPC codes-encoding friendly TS-LDPC (EFTS-LDPC) codes. Simulation results demonstrate that the bit-error rate (BER) performance at low signal-to-noise ratio (SNR) is competitive with the error performance of random LDPC codes of the same size, with better error floor properties at high SNR

We study the topology of sensor networks. With parallel architectures, the design is trivial - sensors forward their local decisions to a global fusion center. With web architectures, sensors communicate only with 'neighbors' and evolve their local decisions to reach a 'consensus.' In practice, it is important to reach a consensus with minimal communications and processing cost. The convergence rate of the consensus algorithm depends on 1) the weights assigned to the network links; and 2) the connectivity pattern of the network. We apply concepts from small world networks to design the topology and the weights when the local decisions are quantized and study the impact on network performance when we trade number of links for number of bits per decision

In this paper we derive the generalized likelihood ratio test (GLRT) for time reversal detection. We consider a multistatic array configuration with two antenna arrays, one for transmitting and one for receiving. We examine the time reversal GLRT performance with experimental measurements in the electromagnetic domain in a highly cluttered laboratory environment. The experiments show that time reversal provides significant performance gain over the conventional energy detector.

The assumptions underlying linear signal processing (SP) produce more structure than vector spaces. We capture this structure by describing the space of filters as an algebra and the space of signals as the associated module. We formulate an algebraic approach to SP that is axiomatically based on the concept of a signal model. Signal models for time are visualized as directed graphs. We construct corresponding models for undirected graphs, which we hence call space models, and show that, in particular, the 16 DCTs and DSTs are Fourier transforms for these finite space models. Finally, we discuss the extension of our theory to separable and nonseparable 2-DSP

There is much interest into joint runtime and energy optimization of implementations of signal processing algorithms. Applications in domains such as embedded computing, sensor networks, and mobile communications often require processing of signals under simultaneous runtime, energy and/or power constraints. Hence, in addition to runtime, power and energy are first-order design considerations for both hardware and software developers in those domains. This paper studies the automatic generation of software implementations of digital signal processing (DSP) transforms that are optimized with respect to both runtime and energy. We explore the impact of algorithm selection (a software technique) and voltage-frequency scaling (a hardware technique) on the runtime and energy of computing fast linear transforms. We use SPIRAL, a code generation system, to enumerate automatically many alternative algorithms for the discrete Fourier transform. We measure the runtime and energy of these algorithms at different voltage-frequency settings of an Intel Pentium M microprocessor. We report experimental results supporting that algorithm selection and voltage-frequency scaling do achieve the following: (1) have large impact on the runtime and energy of computing the discrete Fourier transform on a microprocessor; and (2) enable the optimization of important joint runtime-energy objectives.

In previous work, we presented a method for constructing dynamic input-output models for real-time state estimation in correlated dynamic fields using wireless sensor networks (WSNs). The input signals correspond to the sensors on the boundary of the physical space under study, reflecting the assumption there are no independent sources in the interior of the region. In this paper, we present a method to identify sensors not on the boundary that should be used as inputs in the dynamic models when there are inner sources, i.e., sources inside the physical space. We extend concepts from the behavioral model theory of Jan Willems to handle noisy time series. We construct a block-Hankel structured matrix based on the sensor data, and then calculate as an independence indicator the angle between each row of the matrix and the subspace determined by the span of the preceding rows. The inner sources are identified based on these angle values. Experimental results with real temperature data collected with a WSN, and including heat sources as inner sources, illustrate the proposed method.

The task of detection optimization in sensor networks is hindered by the large computational cost of evaluating the performance criteria, e.g. the probability of making wrong decisions. We present an approach that avoids these obstacles by considering a rather accurate approximation to computing the detection performance. We propose the saddlepoint approximation and provide results that demonstrate its high accuracy and low complexity. The results are used to show that, for a range of problems, the optimal fusion rule is equivalent to a simple majority rule.

Shape reorientation is a critical step in many image processing and computer vision applications, such as registration, detection, identification, and classification. Shape reorientation is a needed step to restore the correct orientation of a shape when its image is subject to an arbitrary rotation and reflection. We present a robust method to determine the standard "normalized" orientation of two-dimensional (2D) shapes in a blind manner, i.e., without any other information other than the given input shape. We introduce a set of orientation indicator indices (OII) that use low order central moments of the shape to monitor the orientational characteristics of the shape. Because these OIIs use only low (up to third) order moments, they are robust to noise and errors. We show with examples how we bring consistently a given shape with an unknown arbitrary orientation to its standard normalized orientation using the OII.

This paper presents the time reversal adaptive interferer canceller (TRAIC), a novel algorithm that uses time reversal techniques to cancel the presence of interferers. TRAIC is developed for broadband signals and a single emitting antenna. Experimental tests in the electromagnetic domain show the viability and the power of TRAIC.

We investigate performance tradeoffs for a class of filtered backprojection (FBP) image reconstruction algorithms. The recently developed fast hierarchical backprojection asymptotically achieves the same O(N/sup 2/ log N) cost as Fourier-based methods while retaining many advantages of the FBP technique. In this paper, we provide a detailed cost and performance analysis of the algorithm on a general purpose platform. Based on carefully tuned implementations of both the direct and the hierarchical backprojection, we explore the tradeoffs between distortion and runtime by varying several algorithm and implementation choices. Experimental results show that, given the desired performance, the choice of algorithm parameters is not obvious and largely depends on the image properties and the underlying computer platform.

In many sensor networks applications, sensors collect correlated measurements of a physical field, e.g., temperature field in a building or in a data center. However, the locations of the sensors are usually inconsistent with the application requirements. In this paper, we consider the problem of estimating the field at arbitrary positions of interest, where there are possibly no sensors, from the irregularly placed sensors. We map this sensor network on a graph, and, by introducing the concepts of interconnection matrices, system digraphs, and cut point sets, we can pose sensor network tradeoffs and derive real-time field estimation algorithms. The results of temperature field estimation, obtained from simulations and real world experiments, show that the methodology presented in this paper can successfully predict the field values at arbitrary locations, including others than the ones with sensors.

Fast changing, increasingly complex, and diverse computing platforms pose central problems in scientific computing: How to achieve, with reasonable effort, portable optimal performance? We present SPIRAL, which considers this problem for the performance-critical domain of linear digital signal processing (DSP) transforms. For a specified transform, SPIRAL automatically generates high-performance code that is tuned to the given platform. SPIRAL formulates the tuning as an optimization problem and exploits the domain-specific mathematical structure of transform algorithms to implement a feedback-driven optimizer. Similar to a human expert, for a specified transform, SPIRAL "intelligently" generates and explores algorithmic and implementation choices to find the best match to the computer's microarchitecture. The "intelligence" is provided by search and learning techniques that exploit the structure of the algorithm and implementation space to guide the exploration and optimization. SPIRAL generates high-performance code for a broad set of DSP transforms, including the discrete Fourier transform, other trigonometric transforms, filter transforms, and discrete wavelet transforms. Experimental results show that the code generated by SPIRAL competes with, and sometimes outperforms, the best available human tuned transform library code.

Layered video representations are increasingly popular; see [2] for a recent review. Segmentation of moving objects is a key step for automating such representations. Current motion segmentation methods either fail to segment moving objects in low-textured regions or are computationally very expensive. This paper presents a computationally simple algorithm that segments moving objects, even in low-texture/low-contrast scenes. Our method infers the moving object templates directly from the image intensity values, rather than computing the motion field as an intermediate step. Our model takes into account the rigidity of the moving object and the occlusion of the background by the moving object. We formulate the segmentation problem as the minimization of a penalized likelihood cost function and present an algorithm to estimate all the unknown parameters: the motions, the template of the moving object, and the intensity levels of the object and of the background pixels. The cost function combines a maximum likelihood estimation term with a term that penalizes large templates. The minimization algorithm performs two alternate steps for which we derive closed-form solutions. Relaxation improves the convergence even when low texture makes it very challenging to segment the moving object from the background. Experiments demonstrate the good performance of our method.

Shapes provide a rich set of clues on the identity and topological properties of an object. In many imaging environments, however, the same object appears to have different shapes due to distortions such as translation, rotation, reflection, scaling, or skewing. Further, the order by which the object's feature points are scanned changes, i.e., the order of the pixels may be permuted. Relating two-dimensional shapes of the same object distorted by different affine and permutation transformations is a challenge. We introduce a shape invariant that we refer to as the intrinsic shape of an object and describe an algorithm, BLAISER, to recover it. The intrinsic shape is invariant to affine-permutation distortions. It is a uniquely defined representative of the equivalence class of all affine-permutation distortions of the same object. BLAISER computes the intrinsic shape from any arbitrarily affine-permutation distorted image of the object, without prior knowledge regarding the distortions or the undistorted shape of the object. The critical step of BLAISER is the determination of the shape orientation and we provide a detailed discussion on this topic. The operations of BLAISER are based on low-order moments of the input shape and, thus, robust to error and noise. Examples illustrate the performance of the algorithm.

The paper presents a novel stochastic active contour scheme (STACS) for automatic image segmentation designed to overcome some of the unique challenges in cardiac MR images such as problems with low contrast, papillary muscles, and turbulent blood flow. STACS minimizes an energy functional that combines stochastic region-based and edge-based information with shape priors of the heart and local properties of the contour. The minimization algorithm solves, by the level set method, the Euler-Lagrange equation that describes the contour evolution. STACS includes an annealing schedule that balances dynamically the weight of the different terms in the energy functional. Three particularly attractive features of STACS are: 1) ability to segment images with low texture contrast by modeling stochastically the image textures; 2) robustness to initial contour and noise because of the utilization of both edge and region-based information; 3) ability to segment the heart from the chest wall and the undesired papillary muscles due to inclusion of heart shape priors. Application of STACS to a set of 48 real cardiac MR images shows that it can successfully segment the heart from its surroundings such as the chest wall and the heart structures (the left and right ventricles and the epicardium.) We compare STACS' automatically generated contours with manually-traced contours, or the "gold standard," using both area and edge similarity measures. This assessment demonstrates very good and consistent segmentation performance of STACS.

Advances in integrated technologies are making networks of many inexpensive deployable autonomous sensors a reality. Individually, each sensor may not accomplish much, but working cooperatively they have for example the potential to monitor large areas, detect the presence or absence of targets, or track moving objects. These sensors operate under constraints imposed by scarce power and other limited resources like bandwidth or computing capacity. The paper considers detection in such a distributed sensor environment. We investigate the impact on detection performance, as measured by the probability of error, of such parameters as number of sensors, number of quantization levels at each sensor, or signal to noise ratio, under a rate constraint on the common access communications channel. We optimize the local detectors when the number of sensors is large. We show that the performance loss due to quantization decays exponentially fast as the number of bits per sensor increases and that the choice between hard versus soft local detectors depends not only on the noise distribution and the quantization rate, but also on the SNR under which the sensors operate.

Magnetic resonance force microscopy (MRFM) is a technology that will potentially enable microscopy of molecules and proteins at atomic-scale detail. Physicists are pursuing MRFM and single electron spin microscopy (SESM). Many technological challenges exist for MRFM and SESM to deliver on the promise of "visualizing" a single electron spin. The forces of interest are in the subattoneNewton and attoneNewton range (10/sup -18/ N). In this paper we consider the problem in MRFM and SESM of detecting extremely weak signals buried in noise with SNR in the range of -15 dB to -40 dB. We describe a model that, although simplistic, captures the features of the problem. We present a GLRT and bootstrap approach that incorporates a bank of Viterbi algorithms, and show by simulations that, with physically realistic parameter values, the detector can achieve probability of detection /spl beta/ = 0.9 with false alarm rate /spl alpha/ = 0.05, at SNR= -20 dB.

A growing number of performance-critical DSP applications use the discrete wavelet transform (DWT), thus prompting the need for highly efficient DWT software implementations. Unfortunately, the rapid evolution of computing platforms and compiler technology makes carefully hand-tuned code obsolete almost as fast as it is written. In this paper, we describe our work on the automatic generation of DWT implementations that are tuned to a given platform. Our approach captures the various DWT algorithms in a concise mathematical framework that enables the integration of DWTs into the SPIRAL code generation system. Experiments show the quality of our automatically generated code and provide interesting insights; for example, the fastest code differs between platforms and is usually based on a non-obvious combination of DWT algorithms.

In sensor networks, many sensors cooperate and collaborate to monitor overlapping subsets from a set of targets. We consider the important issue of fusing their soft decisions. These soft decisions depend on the sensor measurements and take the form of probability densities. Consequently, data fusion becomes a problem of probabilistic inference on a factor graph of arbitrary topology, which can be accomplished by belief propagation. This paper studies the convergence of belief propagation when the soft decisions are Gaussian densities, that is, studies the convergence of the variances and means computed by belief propagation. We show that if the spectral radius /spl rho/ of a certain matrix is less than one, the means resulting from belief propagation converge to the true means. This extends to general topology sensor networks the results for a fully-connected network of two sensors and m targets in (P. Rusmevichientong et al., IEEE Trans. Inform. Theory, vol.47, no.2, p.745-765, 2001).

A class of structured LDPC codes-turbo-structured LDPC (TS-LDPC) codes-composed of two subtrees connected by an interleaver is introduced in this paper. TS-LDPC codes with good girth properties are easy to design: careful design of the interleaver component prevents short cycles in its Tanner graph. A methodology to design TS-LDPC codes with arbitrary column weight j/spl ges/2 and arbitrary girth is also presented. In addition, a complexity reduced decoding algorithm is described. Simulation results demonstrate the good performance of TS-LDPC codes when compared to random LDPC codes of the similar size and rate.

In this paper we construct three types of low-density parity-check codes with column weight j = 3 based on geometries in graphical models. Low-density parity-check codes with j > 2 are desired because their minimum distance improves linearly with the code block length n. The codes we present here have girth 8 and girth 10. All codes are regular and well-structured. These codes have flexible block lengths and code rates, and may be used in the area of communications and data storage. Our simulation results show that they have better bit-error-rate decoding performance and lower error floors in additive white Gaussian noise channels than randomly constructed low-density parity-check codes.

In this paper, we address the problem of optimizing the detection performance of sensor networks under communication constraints on the common access channel. Our work helps understanding tradeoffs between sensor network para-meters like number of sensors, degree of quantization at each local sensor, and SNR. Traditionally, this problem is tack-led using asymptotic assumptions on the number of sensors, an approach that leads to the abstraction of important details such as the structure of the fusion center. We adopt a non-asymptotic approach and optimize both, the sensing and the fusion sides with respect to the probability of detection error. We show that the optimal fusion rule has an interesting structure similar to themajority-voting rule. In addition, we study the convergence with respect to the number of sensors of the performance of the fusion rule. We show that convergence is SNR dependent and that, in low-SNR environments, asymptotics may require a large number of sensors.

We introduce a method to design structured LDPC codes with large girth and flexible code rates. The method is simple to explain: we divide the nodes in the Tanner graph into groups and connect nodes in these groups according to a set of parameters called shifts. We derive a general theorem on the shifts to prevent small cycles. Simulations show that these codes, GS-LDPC codes, outperform random LDPC codes.

The paper introduces three new classes of structured regular (n, 2, k) LDPC codes with girth 12, 16, and 20, respectively. These codes are systematically constructed, well structured, and have uniform row and column weights, which make them able to simplify greatly the implementation of LDPC coders. Their large girth improves their decoding performance. Simulation results compare their bit error rate (BER) performance over additive white Gaussian noise (AWGN) channels with randomly constructed LDPC codes. When concatenated with error-correcting codes such as Reed-Solomon codes, LDPC codes with j=2 are promising for data storage and other applications.

SPIRAL is a generator for platform-adapted libraries of DSP transform algorithms. SPIRAL represents and automatically generates fast algorithms as mathematical formulas and translates them into programs. Adaptation is achieved by searching in the space of algorithmic and coding alternatives for the fastest implementation. We extend SPIRAL to generate platform-adapted implementations of FIR filters. First, we present various filter algorithms and introduce the mathematical constructs needed to include them into SPIRAL's architecture. Then we use SPIRAL to find fast filter implementations. The results show runtime improvements to a standard loop implementation of up to 70% using different blocking techniques. Further, we show that the usefulness of frequency-domain methods is not determined by the number of operations.

We study the fusion of data collected by multiple heterogeneous sensors that work cooperatively to achieve a common goal. The paper presents fast algorithms to fuse the sensor data. We map the problem into a graphical model and then develop a fast message-passing scheme to fuse the data. We simulate scenarios with 150 sensors and 200 targets that are successfully fused.

In this paper, we study the reorientation of 2D shapes. We describe an algorithm that removes orientational ambiguity from arbitrarily oriented 2D shapes. The algorithm is robust to error in pixel locations as well as in the presence of occluded or added pixels. After reorientation, the resulting shape is in a normalized orientation and can then be used effectively in post-processing stages of such applications as pattern detection, recognition, and registration. The algorithm combines a new measure of shape orientation, the variable-size window orientation indicator index (/spl Delta/-OII), and the point-based reorientation algorithm (PRA) that we presented before. We test the new algorithm against an extensive database of complex 2D shapes.

We develop an energy based automatic image segmentation algorithm using a novel active contour scheme. The algorithm overcomes some unique challenges arising in cardiac MR images. Two features are particularly relevant. The first is that it uses region-based information captured by a stochastic model. As a result, our method is robust to assumed initial conditions and can be applied to a large range of images, particularly when the contrast is low. The second feature is the incorporation of prior knowledge on the shape of the organ to be segmented. For cardiac image segmentation, it is sufficient to assume that the shape resembles an ellipse.

The paper describes the rank 1 weighted factorization solution to the structure from motion problem. This method recovers the 3D structure from the factorization of a data matrix that is rank 1 rather than rank 3. This matrix collects the estimates of the 2D motions of a set of feature points of the rigid object. These estimates are weighted by the inverse of the estimates error standard deviation so that the 2D motion estimates for "sharper" features, which are usually well-estimated, are given more weight, while the noisier motion estimates for "smoother" features are weighted less. We analyze the performance of the rank 1 weighted factorization algorithm to determine what are the most suitable 3D shapes or the best 3D motions to recover the 3D structure of a rigid object from the 2D motions of the features. Our approach is developed for the orthographic camera model. It avoids expensive singular value decompositions by using the power method and is suitable to handle dense sets of feature points and long video sequences. Experimental studies with synthetic and real data illustrate the good performance of our approach.

It is known that the discrete Fourier transform (DFT) used in digital signal processing can be characterized in the framework of the representation theory of algebras, namely, as the decomposition matrix for the regular module ${\mathbb{C}}[Z_n] = {\mathbb{C}}[x]/(x^n - 1)$. This characterization provides deep insight into the DFT and can be used to derive and understand the structure of its fast algorithms. In this paper we present an algebraic characterization of the important class of discrete cosine and sine transforms as decomposition matrices of certain regular modules associated with four series of Chebyshev polynomials. Then we derive most of their known algorithms by pure algebraic means. We identify the mathematical principle behind each algorithm and give insight into its structure. Our results show that the connection between algebra and digital signal processing is stronger than previously understood.

Block banded matrices generalize banded matrices. In this paper, we exploit properties of full matrices whose inverses are L-block banded to derive fast inverses for such matrices, and inverses for matrices that are themselves block banded. We apply these results to design fast implementations for the Kalman-Bucy filter in applications arising often in the physical sciences where the underlying models derive from discretizations of partial differential equations and the observations are sparse.

We present in this paper a clutter adaptive, multiframe Bayesian algorithm for joint detection and tracking of a multiaspect target in cluttered image sequences. The target template is randomly translated, rotated, scaled and sheared from frame to frame. Tracking performance studies with a sequence generated from real data infrared airbone radar (lRAR) imagery show a reduction in the steady-state position estimation error and in the target acquisition time when the Bayes detector/tracker is compared to the association of a bank of matched filter detectors and a linearized Kalman-Bucy tracker.

We introduce a new Bayesian algorithm for joint multiframe detection and tracking of multiaspect targets that move randomly in cluttered digital image sequences. Two versions of the algorithm are derived: a batch Bayes smoother and an on-line Bayes filter. Performance results with a simulated image sequence generated from real infrared airborne radar (IRAR) data show an improvement over the association of a bank of correlation detectors and a Kalman-Bucy tracker in a scenario with a heavily cluttered multiaspect target.

Classic ocean acoustic tomography by Wiener inversion needs good estimates of the noise power affecting the errors between the in situ measurements of the travel times and their estimates obtained by reliable simulations. We investigate the maximum likelihood estimation of a structured covariance matrix, whose subspaces of interest are known, but whose associated powers are unknown. Using the ocean acoustic tomography constraints, we assume that the covariance is the sum of a full rank known matrix and an unknown component. We derive the maximum likelihood estimates for these noise powers and compute the Fisher information matrix to get insight into the geometric properties of the estimators. We verify with a realistic classic ocean acoustic tomography simulation the good quality of our noise power estimates.

This paper develops the two-dimensional (2D) clutter adaptive, multiframe Bayes detector/tracker for targets with random signature. We model the background Clutter and the target signature as samples of two independent, spatially correlated, 2D noncausal Gauss-Markov random fields (GMrfs). The target's motion is modeled by a 2D hidden Markov model (HMM). We study, through Monte Carlo simulations, the performance of the adaptive multiframe detector/tracker, and show that the performance of the adaptive tracker is very close to the performance of the tracker when the clutter model is perfectly known.

We present a two-dimensional wavelet transform that is invariant to affine distortions of the input signal. Affine distortions include geometric effects such as translation, reflection, uniform and anisotropic scaling, rotation, and shearing of the input signal. Invariance of the wavelet transform to affine distortions is achieved in our work by developing an algorithm that reduces replicas of a signal related by affine distortions to a unique prototype signal. The affine invariant wavelet transform is then defined as the two-dimensional wavelet transform of the prototype signal, which provides the wavelet coefficients that are invariant to affine distortions of the input signal. We describe our algorithm and show examples that demonstrate our claims.

The paper computes the reliability of estimates of image motion parameters. The use of such measures of reliability to weight motion estimates improves significantly the performance of motion analysis tasks such as the recovery of 3D structure (see Irani, M. and Anandan, R., ECCV, vol.1, p.539-53, 2000; Aguiar, P.M.Q. and Moura, J.M.F., IEEE ICIP, vol.1, p.549-52, 2000). The paper relates both the estimation error variance and the stability of the estimation algorithm with the spatial gradient of the image brightness pattern. We illustrate the predictions of our expressions with several image brightness patterns.

This paper presents the surface-based factorization method to recover three-dimensional (3-D) structure, i.e., the 3-D shape and 3-D motion, of a rigid object from a two-dimensional (2-D) video sequence. The main ingredients of our approach are as follows: 1) we describe the unknown shape of the 3-D rigid object by polynomial patches; 2) projections of these patches in the image plane move according to parametric 2-D motion models; 3) we recover the parameters describing the 3-D shape and 3-D motion from the 2-D motion parameters by factorizing a matrix that is rank 1 in a noiseless situation. Our method is simultaneously an extension and a simplification of the original factorization method of Tomasi and Kanade (1992). We track regions where the 2-D motion in the image plane is described by a single set of parameters, avoiding the need to track a large number of pointwise features, in general, a difficult task. Then our method estimates the parameters describing the 3-D structure by factoring a rank 1 matrix, not rank 3 as in Tomasi and Kanade. This allows the use of fast iterative algorithms to compute the 3-D structure that best fits the data. Experimental results with real-life video sequences illustrate the good performance of our approach.

Hyperspectral sensors collect hundreds of narrow and contiguously spaced spectral bands of data. Such sensors provide fully registered high resolution spatial and spectral images that are invaluable in discriminating between man-made objects and natural clutter backgrounds. The price paid for this high resolution data is extremely large data sets, several hundred of Mbytes for a single scene, that make storage and transmission difficult, thus requiring fast onboard processing techniques to reduce the data being transmitted. Attempts to apply traditional maximum likelihood detection techniques for in-flight processing of these massive amounts of hyperspectral data suffer from two limitations: first, they neglect the spatial correlation of the clutter by treating it as spatially white noise; second, their computational cost renders them prohibitive without significant data reduction like by grouping the spectral bands into clusters, with a consequent loss of spectral resolution. This paper presents a maximum likelihood detector that successfully confronts both problems: rather than ignoring the spatial and spectral correlations, our detector exploits them to its advantage; and it is computationally expedient, its complexity increasing only linearly with the number of spectral bands available. Our approach is based on a Gauss-Markov random field (GMRF) modeling of the clutter, which has the advantage of providing a direct parameterization of the inverse of the clutter covariance, the quantity of interest in the test statistic. We discuss in detail two alternative GMRF detectors: one based on a binary hypothesis approach, and the other on a "single" hypothesis formulation. We analyze extensively with real hyperspectral imagery data (HYDICE and SEBASS) the performance of the detectors, comparing them to a benchmark detector, the RX-algorithm. Our results show that the GMRF "single" hypothesis detector outperforms significantly in computational cost the RX-algorithm, while delivering noticeable detection performance improvement.

We investigate the properties of block matrices with block banded inverses to derive efficient matrix inversion algorithms for such matrices. In particular, we derive the following: (1) a recursive algorithm to invert a full matrix whose inverse is structured as a block tridiagonal matrix; (2) a recursive algorithm to compute the inverse of a structured block tridiagonal matrix. These algorithms are exact. They reduce the computational complexity respectively by two and one orders of magnitude over the direct inversion of the associated matrices. We apply these algorithms to develop a computationally efficient approximate implementation of the Kalman-Bucy filter (KBf) that we refer to as the local KBf. The computational effort of the local KBf is reduced by a factor of I/sup 2/ over the exact KBf while exhibiting near-optimal performance.

We present a Bayesian algorithm for optimal multiframe detection and tracking of small extended targets in two-dimensional (2D) finite resolution images. The algorithm integrates detection and tracking into a single framework using as data a sequence of cluttered sensor snapshots. Performance studies using Monte Carlo simulations show substantial improvements when the proposed Bayes tracker is compared to the association of a correlation filter and a linearized Kalman-Bucy filter. Likewise, there are significant detection performance gains of up to 6 dB in peak signal-to-noise ratio (PSNR) when the multiframe Bayes detector is compared to a single frame likelihood ratio test (LRT) detector.

The use of hyperspectral imagery for remote sensing detection applications has received attention due to the ability of the hyperspectral sensor to provide registered information in both space and frequency. However, this coupling of spatial and spectral information leads to an immense amount of data for which it has proven difficult to develop an efficient implementation of the maximum-likelihood (ML) detector. We present the Gauss-Markov random field (GMRF) detector which we have developed for detecting man-made anomalies in hyperspectral imagery. The GMRF detector is the first computationally efficient ML-detector for hyperspectral imagery. We compare the detection performance and the computational requirements of our detector implementation to the benchmark RX detection algorithm for hyperspectral imagery.

Factorization methods use linear subspace constraints to recover 3D rigid structures from 2D motion. Usually, these methods give equal weight to the contribution of each region (or feature) to the estimates of the 3D structure. In this paper, we accommodate different confidence weights for the 2D motion parameter estimates of each region, by rewriting the problem as the factorization of a modified matrix. This incurs no additional computational cost.

We present in this paper a multiframe Bayesian algorithm for the detection and tracking of heavily cluttered rigid bodies with random translational and rotational motion. Monte Carlo simulations with synthetic targets and clutter show that the proposed algorithm achieves substantial performance gains over the common association of a maximum likelihood position estimator and a linearized Kalman-Bucy filter.

The Society Best Paper Awards honor the author(s) of manuscripts of exceptional merit dealing with subjects related to the Society's technical scope. The papers have appeared in one of the Transactions or Letters of the IEEE Signal Processing Society. Papers are selected for their novelty and quality. The Best Paper Awards recognize authors irrespective of age. The Young Author Best Paper Awards single out work by individuals who were under 30 years of age at the time the manuscript was submitted for peer review. The criteria for excellence is the same as for the Best Paper Awards. I have also listed the recipients of the IEEE Signal Processing Magazine Award. Manuscripts published in the magazine are "tutorial length," providing a broader description of signal processing or related disciplines. Finally, I include in my list the recipients of the IEEE W.R.G. Baker Prize, the IEEE -wide award for the most outstanding paper, reporting original work, in the transactions, journals, and magazines of the IEEE, or in the PROCEEDINGS OF THE IEEE. This year, the prize was presented to a signal processing paper. So, in the spirit of providing a good read, please find below a list of the citations for the Society’s Best Paper, Young Author Best Paper, and IEEE Signal Processing Magazine Awards.

This work designs sequence detectors for channels with intersymbol interference (ISI) and correlated (and/or signal-dependent) noise. We describe three major contributions. (i) First, by modeling the noise as a finite-order Markov process, we derive the optimal maximum-likelihood sequence detector (MLSD) and the optimal maximum a posteriori (MAP) sequence detector extending to the correlated noise case the Viterbi algorithm. We show that, when the signal-dependent noise is conditionally Gauss-Markov, the branch metrics in the MLSD are computed from the conditional second-order noise statistics. We evaluate the branch metrics using a bank of finite impulse response (FIR) filters. (ii) Second, we characterize the error performance of the MLSD and MAP sequence detector. The error analysis of these detectors is complicated by the correlation asymmetry of the channel noise. We derive upper and lower bounds and computationally efficient approximations to these bounds based on the banded structure of the inverses of Gauss-Markov covariance matrices. An experimental study shows the tightness of these bounds. (iii) Finally, we derive several classes of suboptimal sequence detectors, and demonstrate how these and others available in the literature relate to the MLSD. We compare their error rate performance and their relative computational complexity, and show how the structure of the MLSD and the performance evaluation guide us in choosing a best compromise between several types of suboptimal sequence detectors.

The paper considers the inversion of full matrices whose inverses are L-banded. We derive a nested inversion algorithm for such matrices. Applied to a tridiagonal matrix, the algorithm provides its explicit inverse as an element-wise product (Hadamard product) of three matrices. When related to Gauss-Markov random processes (GMrp), this result provides a closed-form factored expression for the covariance matrix of a first-order GMrp. This factored form leads to the interpretation of a first-order GMrp as the product of three independent processes: a forward independent-increments process, a backward independent-increments process, and a variance-stationary process. We explore the nonuniqueness of the factorization and design it so that the forward and backward factor processes have minimum energy. We then consider the issue of approximating general nonstationary Gaussian processes by Gauss-Markov processes under two optimality criteria: the Kullback-Leibler distance and maximum entropy. The problem reduces to approximating general covariances by covariance matrices whose inverses are banded. Our inversion result is an efficient algorithmic solution to this problem. We evaluate the information loss between the original process and its Gauss-Markov approximation.

Hyperspectral sensors are passive sensors that simultaneously record images for hundreds of contiguous and narrowly spaced regions of the electromagnetic spectrum. Each image corresponds to the same ground scene, thus creating a cube of images that contain both spatial and spectral information about the objects and backgrounds in the scene. In this paper, we present an adaptive anomaly detector designed assuming that the background clutter in the hyperspectral imagery is a three-dimensional Gauss-Markov random field. This model leads to an efficient and effective algorithm for discriminating man-made objects (the anomalies) in real hyperspectral imagery. The major focus of the paper is on the adaptive stage of the detector, i.e., the estimation of the Gauss-Markov random field parameters. We develop three methods: maximum-likelihood; least squares; and approximate maximum-likelihood. We study these approaches along three directions: estimation error performance, computational cost, and detection performance. In terms of estimation error, we derive the Cramer-Rao bounds and carry out Monte Carlo simulation studies that show that the three estimation procedures have similar performance when the fields are highly correlated, as is often the case with real hyperspectral imagery. The approximate maximum-likelihood method has a clear advantage from the computational point of view. Finally, we test extensively with real hyperspectral imagery the adaptive anomaly detector incorporating either the least squares or the approximate maximum-likelihood estimators. Its performance compares very favorably with that of the RX algorithm.

Tomasi and Kanade (1992) introduced the factorization method for recovering 3D structure from 2D video. In their formulation, the 3D shape and 3D motion are computed by using an SVD to approximate a matrix that is rank 3 in a noiseless situation. In this paper we reformulate the problem using the fact that the x and y coordinates of each feature are known from their projection onto the image plane in frame 1. We show how to compute the 3D shape, i.e., the relative depths z, and the 3D motion by a simple factorization of a matrix that is rank 1 in a noiseless situation. This allows the use of very fast algorithms even when using a large number of features and large number of frames. We also show how to accommodate confidence weights for the feature trajectories. This is done without additional computational cost by rewriting the problem as the factorization of a modified matrix.

We propose an optimal nonlinear Bayesian algorithm for joint detection and tracking of targets that move randomly in cluttered environments. We review the derivation of the optimal Bayesian detector/tracker and present Monte Carlo simulations that benchmark the detection and tracking performances in both spatially correlated and non-Gaussian clutter.

This paper presents a new structure for adaptive predistortion of the memoryless, nonlinear saturation effects caused by high power amplifiers (HPA). Timely compensation for HPA distortions is critical for cost-effective prevention of the cliff effect during terrestrial transmission of digital broadcast television. The new structure results from a two-stage approach: The forward model is identified first from measured data, and then the inverse to the forward model is computed. Replacing the analog system by the HPA forward model in the second stage eliminates measurement noise and analog system delays, resulting in faster adaptation and less solution bias. Additionally, block processing reduces noise in the forward modeling stage. In the inverse modeling stage, the use of synthetic data and a closed form expression for the gradient result in more efficient convergence and more accurate solutions. Simulation results using measured HPA data demonstrate an average 5 dB improvement in SINAD for standard SNR operating ranges.

The factorization method is a feature-based approach to recover 3D rigid structure from motion. In 1998, we extended their framework to recover a parametric description of the 3D shape. The 3D shape and 3D motion are computed by using an SVD to approximate a matrix that is rank 3 in a noiseless situation. In this paper, we develop a new algorithm that has two relevant advantages over the previous algorithms. First, instead of imposing a common origin for the parametric representation of the 3D surface patches, we allow the the specification of different origins for different patches. This improves the numerical stability of the image motion estimation algorithm and the accuracy of the 3D structure recovery algorithm. Second, we show how to compute the 3D shape and 3D motion by a simple factorization of a modified matrix that is rank 1 in a noiseless situation, instead of a rank 3 matrix. This allows the use of very fast algorithms even when using a large number of features (or regions) number of frames.

We build 3D models of rigid bodies from video sequences. The algorithm we use is simple and robust. It recovers the 3D shape parameters and the 3D motion parameters by first estimating the parameters of the induced optical flow representation. To estimate the 3D shape and 3D motion from the optical flow, we use a fast algorithm that is based on the factorization of a matrix that is rank 1 in a noiseless situation. We demonstrate our approach with a piecewise planar object shape built from a real life video clip. We highlight some of the potential applications of the 3D models obtained.

In the physical sciences, e.g., meteorology and oceanography, combining measurements with the dynamics of the underlying models is usually referred to as data assimilation. Data assimilation improves the reconstruction of the image fields of interest. Assimilating data with algorithms like the Kalman-Bucy filter (KBf) is challenging due to their computational cost which for two-dimensional (2-D) fields is of O(I(6)) where I is the linear dimension of the domain. In this paper, we combine the block structure of the underlying dynamical models and the sparseness of the measurements (e.g., satellite scans) to develop four efficient implementations of the KBf that reduce its computational cost to O(I(5)) in the case of the block KBf and the scalar KBf, and to O(I(4)) in the case of the local block KBf (lbKBf) and the local scalar KBf (lsKBf). We illustrate the application of the IbKBf to assimilate altimetry satellite data in a Pacific equatorial basin.

Extracting human representations from video has vast applications. In this paper, we present a knowledge-based framework to capture metarepresentations for real-life video with human walkers. The system models the human body as an articulated object and the human walking as a cyclic activity with highly correlated temporal patterns. We extract for each of the body parts its motion, shape, and texture. Once available, this structural information can be used to manipulate or synthesize the original video sequence, or animate the walker with a different motion in a new synthesized video.

One aim of using hyperspectral imaging sensors is in discriminating man-made objects from dominant clutter environments. Sensors like Aviris or Hydice simultaneously collect hundreds of contiguous and narrowly spaced spectral band images for the same scene. The challenge lies in processing the corresponding large volume of data that is collected by the sensors. Usual implementations of the maximum-likelihood (ML) detector are precluded because they require the inversion of large data covariance matrices. We apply a Gauss-Markov random field (GMRF) model to derive a computationally efficient ML-detector implementation that avoids inversion of the covariance matrix. The paper details the structure of the GMRF model, presents an estimation algorithm to fit the GMRF to the hyperspectral sensor data, and finally, develops the structure of the ML-detector.

We present a closed-form algorithm for blind identification of multiple-input/multiple-output (MIMO) finite-impulse response (FIR) systems driven by digital sources. The algorithm is based on second-order statistics and yields an asymptotically exact estimate of the MIMO channel. We assign distinct spectral signatures to each user through transmitter correlative filters, and exploit this spectral asymmetry to derive the closed-form solution. Simulation results illustrate the good performance of the proposed approach. We compare the mean-square error (MSE) of the MIMO channel estimate against the Cramer-Rao bound, and assess the algorithm capability in rejecting inter-user crosstalk interference.

By applying the Euclidian branch metric in a Viterbi-like detector when the noise is signal-dependent and correlated, the receiver falls short of the maximum likelihood sequence detector (MLSD). We introduce new signal-dependent correlation-sensitive branch metrics for Viterbi-like implementations of the MLSD. We also provide an analytic analysis that calculates the probability of error of such a detector and compares it to the performance of the Euclidian detector. The new metric is well suited for magnetic recording applications where, especially at high recording densities, the noise is both correlated and signal-dependent.

We generalize to 3D shaped mosaics the generative video representation of video sequences introduced by Jasinschi and Moura (see Proceedings of the IEEE International Conference on Image Processing, Washington DC, USA, October 1995). Using a parametric representation of the 3D shape, we recover the 3D shape and 3D motions from the 2D motions in the video sequence. We consider piecewise planar object shapes under orthography and demonstrate our approach with a real life video clip.

We present a knowledge-based framework to capture and represent human walkers in video. The system models the human body as an articulated object of twelve rigid body-parts whose motions are almost periodic and subject to dynamic constraints. The resulting representation is compact and composed of the motion, shape, and texture for each of the body-parts. We apply the representation to regenerate the original sequence and to synthesize articulated 3D human actions.

Very low bit-rate coding requires new paradigms that go well beyond pixel- and frame-based video representations. We introduce a novel content-based video representation using tridimensional entities: textured object models and pose estimates. The multiproperty object models carry stochastic information about the shape and texture of each object present in the scene. The pose estimates define the position and orientation of the objects for each frame. This representation is compact. It provides alternative means for handling video by manipulating and compositing three-dimensional (3-D) entities. We call this representation tridimensional video compositing, or 3DVC for short. We present the 3DVC framework and describe the methods used to construct incrementally the object models and the pose estimates from unregistered noisy depth and texture measurements. We also describe a method for video frame reconstruction based on 3-D scene assembly, and discuss potential applications of 3DVC to video coding and content-based handling. 3DVC assumes that the objects in the scene are rigid and segmented. By assuming segmentation, we do not address the difficult questions of nonrigid segmentation and multiple object segmentation. In our experiments, segmentation is obtained via depth thresholding. It is important to notice that 3DVC is independent of the segmentation technique adopted. Experimental results with synthetic and real video sequences where compression ratios in the range of 1:150-1:2700 are achieved demonstrate the applicability of the proposed representation to very low bit-rate coding.

We address the problem of blind identification of multiuser multiple-input multiple-output (MIMO) finite-impulse response (FIR) digital systems. This problem arises in spatial division multiple access (SDMA) architectures for wireless communications. We present a closed-form, i.e., noniterative, consistent estimator for the MIMO channel based only on second-order statistics. To obtain this closed form we introduce spectral/correlation asymmetry between the sources by filtering each source output with adequate correlative filters. Our algorithm uses the closed form MIMO channel estimate to cancel the intersymbol interference (ISI) due to multipath propagation and to discriminate between the sources at the wireless base station receiver. Simulation results show that, for single-user channels, this technique yields better channel estimates in terms of mean-square error (MSE) and better probability of error than a well-known alternative method. Finally, we illustrate its performance for MIMO channels in the context of the global system for mobile communications (GSM) system.

We develop computationally fast and storage efficient implementations for the Kalman-Bucy filter (KBf) for data assimilation problems with large time varying multidimensional fields. We refer to them as the block KBf (bKBf) and the localized block KBf (lbKBf). For fields defined on a 2D lattice of linear dimension I, the bKBf reduces the computational complexity of the KBf by O(I). The lbKBf saves further on computations by a factor of I and decreases the storage requirements by O(I). We illustrate the IbKBf in assimilating satellite measurements in physical oceanography, presenting simulations for an equatorial beta plane.

In our earlier work, we developed a robust detector for multipath constrained environments when the transmitted signal is known. In this paper, we extend these results to the case where the transmitted signal is a random process. The approach of Chaung He et al. (see ICASSP, p.V-2650-53, 1996 and IEEE Trans. Signal Processing, 1996) is to replace the orthogonal projection on the multipath signal subspace /spl Sscr/ by the orthogonal projection on a representation subspace /spl Gscr/, such that /spl Gscr/ and /spl Sscr/ are close in the gap metric sense. When the signal is random, /spl Sscr/ is no longer a linear subspace but a set with a given structure. The gap metric applies only when /spl Sscr/ and /spl Gscr/ are subspaces. In this paper, we introduce the modified deflection as the appropriate measure to be used in the random signal case. We design the representation subspace /spl Gscr/ to match the multipath signal set /spl Sscr/ in the modified deflection sense. Wavelet multiresolution tools are used to facilitate the design.

POL-SAR data acquired from the two 1994 flights of the SIR-C/X-SAR platform has illustrated the variability of measurements due to seasonal, spectral, and angular changes. Consequently statistical techniques for terrain classification make robust, unsupervised classification problematic. We present an algorithm for classifying terrain that accounts for variability in terrain signatures by deriving a single representative process for each terrain from a family of stochastic scattering models. A best-basis search through a wavelet packet tree, using the Bhattacharyya coefficient as a cost measure, determines the optimal unitary basis of eigenvectors for the representative process and offers a scale-based interpretation of the scattering phenomena. The associated eigenvalues and means are determined through iterative algorithms. The technique is illustrated with a simple example.

When the color or gray level of a moving object is very similar to that of the background, motion-based segmentation methods fail. This leads to ambiguous templates for the moving objects. We propose a method that segments unambiguously from motion the templates of the moving objects. Our method, which we call incremental motion segmentation integrates over time the small differences between the gray level of the moving object and that of the background. Our experiments with segmenting a robot soccer video clip show the quality of our results.

Extracting from a video sequence a representation for humans in motion has numerous applications. This task is difficult due to the complex nature of the human body which is non-rigid and capable of performing a wide variety of actions. We propose a model-based approach to tracking human walking in dynamic scenes. We model the human body as an articulated object connected by joints and rigid parts, and describe the human walking process as a periodic motion. The posture of the walker is determined by a recognition scheme that estimates the period and phase of walking. This result is then used to establish dynamic constraints for the human posture. These constraints along with kinematic constraints that govern the linkage of the articulated human body are then adopted to facilitate the tracking of the body parts of the human. The paper illustrates the results of testing our algorithm with real video.

In numerous content-based video applications, it is important to extract from a video sequence a representation for humans in motion. For example, in generative video (GV), one needs to construct accurate world images for moving objects. Because humans are not rigid objects, this task is difficult. We propose here a model-based recognition of human walking in dynamic scenes. We model the human body as an articulated object connected by joints and rigid parts, and the human walking as a periodic motion. We determine the posture by using a recognition algorithm that estimates the period and phase of walking. We obtain promising results when testing our algorithm with real video.

Gauss-Markov random fields (GMrfs) play an important role in the modeling of physical phenomena. The paper addresses the second-order characterization and the sample path description of GMrf's when the indexing parameters take values in bounded subsets of /spl Rfr//sup d/, d/spl ges/1. Using results of Pitt (1994), we give conditions for the covariance of a GMrf to be the Green's function of a partial differential operator and, conversely, for the Green's function of an operator to be the covariance of a GMrf. We then develop a minimum mean square error representation for the field in terms of a partial differential equation driven by correlated noise. The paper establishes for GMrf's on /spl Rfr//sup d/ second-order characterizations that parallel the corresponding results for GMrf's on finite lattices.

In a multipath communication channel, the optimal receiver is matched to the maximum likelihood (ML) estimate of the multipath signal. In general, this leads to a computationally intensive multi-dimensional nonlinear optimisation problem. We develop a detection algorithm that avoids the ML estimation while still achieving good performance. Our approach is based on a geometric interpretation of the problem. The ML estimate of the multipath signal is the orthogonal projection of the received signal on a suitable signal subspace S. We design a second subspace G, the representation subspace, that is close to S, but whose orthogonal projection is easily computed. The "closeness" is measured by the gap metric. The subspace G is designed by using wavelet multiresolution analysis tools coupled with a reshaping algorithm in the Zak transform domain. We show an example where our approach significantly outperforms the correlator receiver and an alternative suboptimal approach.

Nonlinear video editors manipulate video sequences by contents irrespective of frame order. These are computer based tools that contrast with analogue linear tape editing technologies. The latter are extremely taxing of videographers time and resources. Current computerized editing methods represent video in terms of individual images. This poses a formidable task to the manipulation task due to the large data volumes associated with them. We discuss a framework-Generative Video, which deals with this problem in an efficient way. Generative Video represents video sequences in terms of constructs-compact models. These are world images and generative operators. World images are augmented images, which contain the non-redundant information in the video sequence, and they describe video contents information. For each independently moving object we have a different world image. World images are stratified in layers according to occlusion information. The generative operators access video contents information, such as the shape and motion of objects moving in the sequence. Nonlinear video editing is realized by applying generative operators to world images. This approach to nonlinear editing facilitates the access, storage, and manipulation of video contents information. We describe the main properties of Generative Video and demonstrate nonlinear editing on a real video sequence.

The paper studies segmentation of moving objects with low texture in a low textured background. We describe an algorithm that resolves the difficulties associated with other approaches by integrating over time the information in the video sequence. We motivate and demonstrate our approach by building the background and moving object world images, important constructs in generative video.

We describe a technique for still image compression that combines (i) noncausal optimal recursive prediction, (ii) residual quadtree mean removal, and (iii) a modification of cascaded vector quantization. We refer to this image codec as noncausal prediction with residual mean removal, and cascaded vector quantization (NRQ/CVQ). We provide examples that illustrate the performance of NRQ/CVQ up to compression ratios of 42.5:1. We show that NRQ/CVQ outperforms alternative algorithms that we tested including the conventional causal prediction differential pulse code modulation (DPCM) with quadtree mean removal cascaded vector quantization and the Joint Photographic Experts Group (JPEG) baseline standard algorithm.

The paper describes a lossy image codec that uses a noncausal (or bilateral) prediction model coupled with vector quantization. The noncausal prediction model is an alternative to the causal (or unilateral) model that is commonly used in differential pulse code modulation (DPCM) and other codecs with a predictive component. We show how to obtain a recursive implementation of the noncausal image model without compromising its optimality and how to apply this in coding in much the same way as a causal predictor. We report experimental compression results that demonstrate the superiority of using a noncausal model based predictor over using traditional causal predictors. The codec is shown to produce high-quality compressed images at low bit rates such as 0.375 b/pixel. This quality is contrasted with the degraded images that are produced at the same bit rates by codecs using causal predictors or standard discrete cosine transform/Joint Photographic Experts Group-based (DCT/JPEG-based) algorithms.

The paper discusses a scheme based on Kalman-Bucy filters for the assimilation of satellite data in equatorial beta plane ocean circulation models. The state equation of the Kalman-Bucy filter is obtained by decoupling the nonlinearities from the Navier-Stokes equations by assuming an inviscid isentropic shallow water motion. Direct application of the Kalman-Bucy filter leads to a computationally intensive algorithm which precludes its application to meaningful sized domains. By imposing a Gauss Markov random field (GMRF) structure on the error covariance matrix, the authors obtain an efficient recursive algorithm, capable of estimating the velocity fields and the sea surface height.

The goal of the paper is to derive an approach for designing nearly shiftable scaling functions for multiresolution analyses (MRAs). Because this method does not increase the sampling density, the sparseness and efficiency of a dyadic grid is preserved. It contrasts with other attempts for the same problem which suffer either from oversampling or from being computationally expensive and data dependent. The algorithm reshapes a starting scaling function by modifying the Zak transform of its energy spectral density (ESD). The paper shows that although the modified signal does not strictly satisfy the 2-scale equation, the approximation error is sufficiently small. The result is a wavelet representation whose subband energy is "nearly" invariant to translations of its input. The paper illustrates this property with specific examples.

Current video compression standards compress video sequences at NTSC quality with factors in the range of 10-100, like in MPEG-1 and MPEC-2. To operate beyond this range, that is, MPEG-4, radically new techniques are needed. We discuss one such technique called generative video (GV). Video compression is realized in GV in two steps. First, the video sequence is reduced to constructs. Constructs are world images, corresponding to augmented images containing the non-redundant information on the sequence, and window, figure, motion, and signal processing operators, representing video sequence properties. Second, the world images are spatially compressed. The video sequence is reconstructed by applying the various operators to the decompressed world images. We apply GV to a 10 sec video sequence of a real 3-D scene and obtain compression ratios of about 2260 and 4520 for two experiments done with different quantization codebooks. The reconstructed video sequence exhibits very good perceptual quality.

Extension of the operational range of underwater location techniques has been related to the incorporation of reliable acoustic propagation models, that closely predict the behaviour of oceans. In this paper, the performance of ocean tomography and passive localization of underwater acoustic sources is studied, by analyzing the coupling of performance degradations imposed by modeling mismatches on the ability to estimate the position of acoustic sources.

In this paper we investigate algorithms to adaptively adjust the coefficients of memoryless polynomial structures used to precompensate for the nonlinear amplitude and phase distortion of the high-power amplifier in a terrestrial digital television transmitter. The results of the investigation are twofold. First the phase error is a non-Euclidean measure of the absolute symbol error. For small inputs, noise causing a small Euclidean change can create a large phase error. We compensate for this heuristically by not updating the predistorter coefficients for small inputs. This thresholding is shown to decrease the residual error of the phase predistorter. Second, the pre-compensation nature of the amplitude correction requires a modification to the traditional LMS algorithm. This modification will be seen to produce a smaller residual error than traditional LMS. We demonstrate the superior performance of our algorithms via simulations based on the measured characteristics of production high-power amplifiers.

The compact representation of video sequences is important for many applications, including very low bit-rate video compression and digital image libraries. We discuss here a novel approach, called generative video, by which video sequences are compactly represented in terms of their contents. This is achieved by reducing the video sequence to constructs. Constructs encode video sequence contents, such as, the shape and the velocity of independently moving objects, and the camera motion. Constructs are of two types: world images and generative operators. World images are augmented images incrementally generated. Generative operators, access video sequence contents and reconstruct the sequence from the world images. The reduction of a video sequence to constructs proceeds in steps. First, the shape of independently moving regions in the image is tessellated into rectangles. Second, world images are generated using the tessellated shape representation. This is described with an experiment using a real video sequence.

In order to achieve good quality very low bit rate video coding, new techniques leading to highly compact representations for video sequences must be investigated. We present a novel video codec framework, where video sequences are represented in terms of stochastic nonparametric 3-D object models and motion script estimates. Multi-property object models, carrying both shape and color information, are incrementally built from video and range sequences. Motion estimates are obtained by depth map registration. We refer to this framework as 3-D video compositing, or 3DVC for short. In this paper, we will describe 3DVC in detail, and present experimental results where interframe compression ratios in the range of 10/sup 2/ to 10/sup 3/ have been achieved.

This paper considers the design of phase estimators by combining concepts of stochastic nonlinear filtering and information theory. To propagate the involved probability density functions, adequate finite representations are needed. This is accomplished in this work by adopting minimum Kullback (1978) distance criteria. Applied to the important and paradigmatic cyclic phase estimation problem, our approach leads to consistent and systematic design methods. The resulting simple and parallelizable structure outperforms the commonly used extended Kalman-Bucy filter in tracking and acquisition situations. These features make the developed nonlinear filter suited to digital communications (carrier synchronization).>

The parameter structure of noncausal homogeneous Gauss Markov random fields (GMRF) defined on finite lattices is studied. For first-order (nearest neighbor) and a special class of second-order fields, a complete characterization of the parameter space and a fast implementation of the maximum likelihood estimator of the field parameters are provided. For general higher order fields, tight bounds for the parameter space are presented and an efficient procedure for ML estimation is described. Experimental results illustrate the application of the approach presented and the viability of the present method in fitting noncausal models to 2-D data.>

The problem of estimating the parameters of noncausal finite lattice Gauss Markov random fields is addressed. It is shown how the structure of the potential matrix (the inverse of the field covariance matrix) can be used to specify the valid parameter space and formulate a computationally practical maximum likelihood estimation procedure. A modification that enables this to generate accurate parameter estimates from noisy data is provided.>

The problem of simultaneous detection of outliers and localization of multiple sources is addressed. This is motivated by the performance degradation observed when quadratic beamformers operate under those conditions. The approach relies on maximum likelihood (ML) methods where outliers are modeled as a space/time impulsive noise process with unknown statistics. The maximization algorithm follows a strategy based on sequential estimation and detection schemes, and it is initialized by an I/sub 1/ beamformer, yielding efficient detection of spikes and accurate estimates of their statistics. This makes it possible to design a model-based beamformer for bearing estimation. The derivation of the algorithm is presented, and its efficiency is discussed using the results obtained from computer simulations.>

Using a recently proposed definition, the authors characterize the ambiguity function of the multipath underwater acoustic channel for passive localization. They study the impact of two factors not considered by previous definitions: uncertainty about the signal spectrum and existence of multiple paths between the source and the receiver. The importance of accurate channel modeling is addressed by comparing the ambiguity surfaces of methods that use a complete model of the channel and methods that rely only on the information contained in the spatial structure of the incoming wavefield. It is shown that the difference in global behavior can be explained by a virtual array, whose geometry is determined by the set of temporal interpath delays.>

Continuous media communication requires timely delivery of data such as digital video and audio packets. Quality of Service (QOS) parameters specify the temporal and spatial characteristic of such continuous media data. To insure timely delivery of continuous media data, the system needs to minimize the communication delay by securing required processor and network resources. We have extended the Capacity-Based Session Reservation Protocol(CBSRP), which was proposed to realizing predictable real-time communications, to support dynamic control of QOS. We have implemented a QOS control scheme by which the network dynamically adjusts the allocations of network bandwidth on a Fiber Distributed Data Interface(FDDI) network.

An approach is developed for noncausal Gauss-Markov random fields (GMRFs) that enables the use of recursive procedures while retaining the noncausality of the field. Recursive representations are established that are equivalent to the original field. This is achieved by first presenting a canonical representation for GMRFs that is based on the inverse of the covariance matrix, which is called the potential matrix. It is this matrix rather than the field covariance that reflects in a natural way the MRF structure. From its properties, two equivalent one-sided representations are derived, each of which is obtained as the successive iterates of a Riccati-type equation. For homogeneous fields, these unilateral descriptions are symmetrized versions of each other, the study of only one Riccati equation being required. It is proven that this Riccati equation converges at a geometric rate, therefore the one-sided representations are asymptotically invariant. These unilateral representations make it possible to process the fields with well-known recursive techniques such as Kalman-Bucy filters and two-point smoothers.>

A recursive procedure is implemented for the enhancement of noncausal Gauss Markov random fields. Experimental results for the enhancement of synthetic as well as real images corrupted by additive white Gaussian noise are provided. These are contrasted with equivalent results obtained by processing the images with recursive filters derived by imposing a causality constraint upon the fields. The results show that the noncausal recursors provide considerable reduction in the mean square error (MSE) of the noisy images without the introduction of undesirable visual effects, such as streaking, that are produced when causality constraints are imposed.>

The problem of maximum likelihood beamforming in the presence of outliers is considered. In practice, outliers occur due to malfunctioning of sensors or as a consequence of strong impulsive noise. The performance of beamformers based on maximum likelihood or minimum mean square error type criteria is seriously degraded by outliers. One solution to combat this would be to optimally detect the failed sensors and the presence of impulses. The complexity of this direct solution increases exponentially with the number of array sensors and time samples. The authors propose an alternative method that models outliers as impulsive noise and detects impulses by using the residue of l/sub 1/ beamformer. This technique is developed, and its efficiency is discussed.>

A general definition of an ambiguity function, based in the Kullback-Leibler directed divergence between probability densities, is formulated. The ambiguity function summarizes all the geometric aspects of the problem, measuring the difficulty in distinguishing between two different source locations. It is shown that by considering a particular model the classical RADAR ambiguity function is obtained. The use of the definition is illustrated by applying it to several problems, showing that it is a useful tool for the analysis of passive location systems.>

The problem of detecting a directional random signal in independent non-Gaussian noise is addressed. In particular, a Gauss-Gauss mixture model is assumed for the total noise field. The approach consists of substituting a beamformer whose design is based on a least-absolute-value criterion for the MMSE (minimum mean square error) beamformer included in the optimum quadratic receiver for the Gaussian signal in the independent Gaussian noise problem. The analytical study and the reported simulation experiments show the robustness of the resulting suboptimum receiver in the presence of unexpected impulsive noise.>

Cramer-Rao bounds are established for passive location in a multipath environment with an array of multiple sensors. The source signature is wideband stationary and the background noise is white. General expressions are derived for the bounds, and the performance gain contributed by the interpath delays over location techniques based on wavefront curvature only (i.e. spatial processing across the array of sensors) is shown.>

In previous work, the authors developed a minimum-mean-square-error beamformer (MMSE-BF). When they compared it to the minimum-variance distortionless-response beamformer (MVDR-BF), they concluded that it is especially suited for correlated returns. This improvement is at the cost of some frequency distortion in wideband applications. To circumvent this problem, the minimum-mean-square-error distortionless-response beamformer (MMSEDR-BF) is introduced. Its behavior is compared with the MVDR-BF and the MMSE-BF. Adaptive beamforming is discussed as an inverse problem. Within this framework, the authors suggest the use of alternative norms, e.g. the L/sub 1/ norm. Preliminary results for L/sub 1/ adaptive beamforming are presented.>

A study is made of the sensitivity of range localization to several features, focusing on features recovered by temporal processing, and a metric that plays the role of an ambiguity function, now generalized to the multipath environment, is developed. In contrast with the matched wave-field approaches, which treat the channel as a black box, the modeling strategy effectively provides a manageable tool for understanding the role that different features can play in localization. Contour plots illustrate the sensitivity of ranging to the features and metric adopted.>

An algorithm is presented for estimating the directions of arrival (DOAs) of multiple narrowband (NB) sources (possible completely correlated) from observations by an array of arbitrary geometry. As a preprocessor, the algorithm extends the application of NB high-resolution direction-finding schemes beyond the linear uniform array configuration, which these methods usually assume when handling coherent sources. The novelty of the approach is that both geometrical considerations and results from optimal estimation theory are used.>

Two alternative ARMA (autoregressive moving average) estimators are compared both theoretically and through simulation analysis. The first is a dual algorithm that estimates the MA and the AR components as the solution of two linear and independent systems of equations. For the second estimator, the AR coefficients result from a system of linear equations, while the MA component is obtained from a fast filtering algorithm initialized with the previous AR estimated coefficients.>

The authors report on time-varying delay estimation in a multisource single direct acoustic path environment. The signals are stochastic nonstationary processes. The time delays are deterministic time-varying functions described by a finite dimensional vector theta of unknown parameters. The observation noise is spatially correlated. The observation time interval is arbitrary. The estimation structure, based on maximum-likelihood (ML) techniques, performs the joint estimation of the signals along with the identification of the parameter vector theta . Under stationary, long observation time interval (SLOT), and time-invariant delay assumptions, two special problem categories are discussed. The first assumes signals with no overlapping frequency spectra. The second considers the mixing of strong and weak signals. For both classes of problem, nonoptimal simplified estimation structures are suggested. Monte Carlo simulation results illustrate how the optimal and nonoptimal processors' mean square error performances compare to the Cramer-Rao bound.>

The multipath passive location problem with wideband source signal is considered. Spatio temporally based high resolution algorithms are presented that assume no knowledge of the second order statistics of the emitted signal. With these methods, the restriction on the size of the receiving aperture commonly imposed by spatial-only high resolution algorithms is substituted by a global condition on the total number of spatial and temporal degrees of freedom. This approach shows that the frequency contents of the emitted signal are effectively used to compensate for the eventual deficiency in the number of available sensors, extending the number of detectable paths for an array of a given size.>

The authors study, for an ARMA (autoregressive moving-average) (p/sub 0/, q/sub 0/) process, the joint determination from a finite data sample of its structural parameters p/sub 0/ and q/sub 0/, its AR and MA components, and its innovation power sigma /sup 2/. The order estimation algorithm is based on the minimization of a functional d that measures the mismatch of the assumed model ARMA (p, q) to the data. The functional is evaluated from the estimated reflection coefficient sequence associated with the process. When the orders are decided, the proposed technique simultaneously provides the estimates of the AR and the MA coefficients as well as sigma /sup 2/.>

The three types of parallelism currently available on the Cray are considered, namely, vectorization, microtasking, and macrotasking. Experiences with all three constructs are presented to show the improvements possible with each of them. While a particular machine, the Cray X-MP/48, has been used, many of the observations, comments, and conclusions derived can be generalized to other shared-memory multiprocessor systems.>

The present work describes an ARMA estimation aIgorithm that differs from the known available techniques. It substitutes the autocorrelation estimation sequence by the sequence of estimated reflection coefficients. These are reliably provided by the Burg technique [1]. Then it fits to the process both a sequence of higher order linear predictors (e.g., Levinson algorithm), and a sequence of higher order linear innovations filters (e.g., by recursive inversion). Finally, it obtains the MA coefficients from the linear relations satisfied by the corresponding coefficients of the successive higher order linear predictors, and likewise obtains the AR coefficients from the linear relations satisfied by the corresponding coefficients of the successive higher order innovation filters. We stress that the procedure does not use the sample autocorrelation lags; it uses instead the sequence of sample reflection coefficients, from which it estimates independently of each other and in a dual way, the MA and the AR components of the process.

Time delay determination is an important problem in numerous applications. The approach taken here models the signals via linear differential equations driven by white noise. The time delays are unknown parameters modulating the received signals. The maximum likelihood estimation of the delays requires the filtering in the minimum mean square error (MMSE) sense of the signals. The problem becomes that of the joint estimation of the signals with the identification of the delays. Due to the structure of the signal model, the signal MMSE estimate is obtained via a recursive structure of the Kalman-Bucy type. The class of signals considered includes the stationary signals, to which the cross-correlation receivers are restricted. In fact, it can be shown that the receiver studied in this paper is a generalization of the cross-correlation receiver. The paper presents the general receiver structure, discussing it in the context of a specific example. The Cramer-Rao bound associated with the delay estimation is also discussed.

The problem of absolute phase tracking and the development of the properties of an optimal estimator of absolute phase are considered. Using Monte Carlo simulation, this estimator's performance is compared with that of the phase-locked loop on the basis of slip distribution growth rate. Further slip prediction is considered and a statistic, based on the entropy of the conditional distribution of the phase given the observations, is shown to be effective.

The paper is concerned with the location of passive sources. Conceptually, this is viewed as a time delay estimation followed by a geometry determination. Signal, noise, and channel modeling questions affect the first block of the processor, i.e., the delay estimator. The second block is sensitive to the geometry description, namely the hypotheses on the dynamics, the array shape, and the relative observer/ /source configuration. Commonly used assumptions lead to decoupled effects which simplify the receiver structure. For deterministic array and source dynamics, a finite parameter description results. The receiver is designed via Maximum-Likelihood techniques. These do not encompass more general situations. To treat the problem of uncertain sensor location, or of stochastic dynamics, a different geometry description is considered. This description represents line arrays and motions as curves in space. Recalling simple facts from Differential Geometry, one is naturally led to describe the array geometry and/or the motion dynamics by a set of differential equations. This casts the passive positioning problem in the context of recursive Kalman-Bucy filtering. The problem of sensor uncertainty location and stochastic dynamics can then be dealt with, without having to consider Taylor series type arguments or other unnatural approximations.