Motivated by the practical application of beam tracking of multiple devices in Multiple Input Multiple Output (MIMO) communication, we study the problem of non-adaptive twenty questions estimation for locating and tracking multiple moving targets under a query-dependent noisy channel. Specifically, we derive a non-asymptotic bound and a second-order asymptotic bound on resolution for optimal query procedures and provide numerical examples to illustrate our results. In particular, we demonstrate that the bound is achieved by a state estimator that thresholds the mutual information density over possible target locations. This single threshold decoding rule has reduced the computational complexity compared to the multiple threshold scheme proposed for locating multiple stationary targets (Zhou, Bai and Hero, TIT 2022). We discuss two special cases of our setting: the case with unknown initial location and known velocity, and the case with known initial location and unknown velocity. Both cases share the same theoretical benchmark that applies to stationary multiple target search in Zhou, Bai and Hero (TIT 2022) while the known initial location case is close to the theoretical benchmark for stationary target search when the maximal speed is inversely proportional to the number of queries. We also generalize our results to account for a piecewise constant velocity model introduced in Zhou and Hero (TIT 2023), where targets change velocity periodically. Finally, we illustrate our proposed algorithm for the application of beam tracking of multiple mobile transmitters in a 5G wireless network.

This work invokes the notion of f-divergence to introduce a novel upper bound on the Bayes error rate of a general classification task. We show that the proposed bound can be computed by sampling from the output of a parameterized model. Using this practical interpretation, we introduce the Bayes optimal learning threshold (BOLT) loss whose minimization enforces a classification model to achieve the Bayes error rate. We validate the proposed loss for image and text classification tasks, considering MNIST, Fashion-MNIST, CIFAR10, and IMDb datasets. Numerical experiments demonstrate that models trained with BOLT achieve performance on par with or exceeding that of cross-entropy, particularly on challenging datasets. This highlights the potential of BOLT in improving generalization.

We address the problem of detecting a change in the distribution of a high-dimensional multivariate normal time series. Assuming that the post-change parameters are unknown and estimated using a sliding window of historical data, we extend the framework of quickest change detection (QCD) to the high-dimensional setting in which the observation dimension increases proportionally with the number of samples used to estimate the post-change parameters. Our analysis reveals that the high-dimensional performance of QCD procedures is governed by an information-theoretic quantity: the Kullback-Leibler (KL) divergence between the true and estimated post-change distributions. Using random matrix theory, we express this divergence explicitly in terms of the underlying post-change model and a parameterized family of estimators. We further identify estimators that asymptotically minimize this KL divergence, resulting in a method that provably outperforms QCD procedures relying on classical maximum likelihood estimation of the postchange parameters.

Motivated by the practical application of beam tracking of multiple devices in Multiple Input Multiple Output (MIMO) communication, we study the problem of non-adaptive twenty questions estimation for locating and tracking multiple moving targets under a query-dependent noisy channel. Specifically, we derive a second-order asymptotic bound on resolution for optimal query procedures and provide numerical examples to illustrate our results. In particular, we demonstrate that a single threshold decoding rule achieves the asymptotic bound. The single threshold decoding rule has reduced the computational complexity compared to the multiple threshold method proposed for locating multiple stationary targets (Zhou, Bai and Hero, TIT 2022). Finally, we illustrate our proposed algorithm for the application of beam tracking of multiple mobile transmitters in a 5G wireless network.

This paper addresses the gradient coding and coded matrix multiplication problems in distributed optimization and coded computing. We present a computationally efficient coding method which overcomes the drawbacks of the Fractional Repetition Coding gradient coding method proposed by Tandon et al., and can also be leveraged by coded computing networks whose servers are of heterogeneous nature. Specifically, we propose a construction for fractional repetition gradient coding; while ensuring that the generator matrix remains close to perfectly balanced for any set of coding parameters, as well as a low complexity decoding step. The proposed binary encoding avoids operations over the real and complex numbers which inherently introduce numerical and rounding errors, thereby enabling accurate distributed encodings of the partial gradients. We then make connections between gradient coding and coded matrix multiplication. Specifically, we show that any gradient coding scheme can be extended to coded matrix multiplication. Furthermore, we show how the proposed binary gradient coding scheme can be used to construct two different coded matrix multiplication schemes, each achieving different trade-offs.

We revisit the problem of statistical sequence matching between two databases of sequences initiated by Unnikrishnan (TIT 2015) and derive achievable theoretical performance guar-antees for a generalized likelihood ratio test (G LRT) in the large deviations regime, when the number of matched pairs of sequences between two databases is unknown. In this case, the task is to accurately estimate the number of matched pairs and identify the matched pairs of sequences among all possible matches between the sequences in the two databases. We generalize the GLRT by Unnikrishnan and explicitly characterize the tradeoff among the exponential decay rates for probabilities of mismatch, false reject and false alarm. When one of the two databases contains a single sequence, the problem of statistical sequence matching specializes to the problem of multiple classification introduced by Gutman (TIT 1989). For this special case, our result strengthens previous result of Gutman (TIT 1989) and Zhou, Tan and Motani (Information and Inference 2020) by allowing the testing sequence to be generated from a distribution that is different from generating distributions of all training sequences.

MOTIVATION: Understanding the mechanisms and structural mappings between molecules and pathway classes are critical for design of reaction predictors for synthesizing new molecules. This article studies the problem of prediction of classes of metabolic pathways (series of chemical reactions occurring within a cell) in which a given biochemical compound participates. We apply a hybrid machine learning approach consisting of graph convolutional networks used to extract molecular shape features as input to a random forest classifier. In contrast to previously applied machine learning methods for this problem, our framework automatically extracts relevant shape features directly from input SMILES representations, which are atom-bond specifications of chemical structures composing the molecules. RESULTS: Our method is capable of correctly predicting the respective metabolic pathway class of 95.16% of tested compounds, whereas competing methods only achieve an accuracy of 84.92% or less. Furthermore, our framework extends to the task of classification of compounds having mixed membership in multiple pathway classes. Our prediction accuracy for this multi-label task is 95.62%. We analyze the relative importance of various global physicochemical features to the pathway class prediction problem and show that simple linear/logistic regression models can predict the values of these global features from the shape features extracted using our framework. AVAILABILITY AND IMPLEMENTATION: https://github.com/baranwa2/MetabolicPathwayPrediction.

Gradient coding is a method for mitigating straggling servers in a centralized computing network that uses erasure-coding techniques to distributively carry out first-order optimization methods. Randomized numerical linear algebra uses randomization to develop improved algorithms for large-scale linear algebra computations. In this paper, we propose a method for distributed optimization that combines gradient coding and randomized numerical linear algebra. The proposed method uses a randomized$\ell _{2}$-subspace embedding and a gradient coding technique to distribute blocks of data to the computational nodes of a centralized network, and at each iteration the central server only requires a small number of computations to obtain the steepest descent update. The novelty of our approach is that the data is replicated according to importance scores, called block leverage scores, in contrast to most gradient coding approaches that uniformly replicate the data blocks. Furthermore, we do not require a decoding step at each iteration, avoiding a bottleneck in previous gradient coding schemes. We show that our approach results in a valid$\ell _{2}$-subspace embedding, and that our resulting approximation converges to the optimal solution.

We revisit the problem of statistical sequence matching between two databases of sequences initiated by Unnikrishnan, (2015) and derive theoretical performance guarantees for the generalized likelihood ratio test (GLRT). We first consider the case where the number of matched pairs of sequences between the databases is known. In this case, the task is to accurately find the matched pairs of sequences among all possible matches between the sequences in the two databases. We analyze the performance of the GLRT by Unnikrishnan and explicitly characterize the tradeoff between the mismatch and false reject probabilities under each hypothesis in both large and small deviations regimes. Furthermore, we demonstrate the optimality of Unnikrishnan’s GLRT test under the generalized Neyman-Person criterion for both regimes and illustrate our theoretical results via numerical examples. Subsequently, we generalize our achievability analyses to the case where the number of matched pairs is unknown, and an additional error probability needs to be considered. When one of the two databases contains a single sequence, the problem of statistical sequence matching specializes to the problem of multiple classification introduced by Gutman, (1989). For this special case, our result for the small deviations regime strengthens previous result of Zhou et al., (2020) by removing unnecessary conditions on the generating distributions.

Disease risk prediction models play an important role in preventing disease developments in modern healthcare. However, the lack of focus on high-risk patients has hindered the large-scale practical application of these models, especially considering the limitation of medical resources available for following up on patients who are deemed high-risk. In this study, we propose a novel and practical approach that focuses on minimizing the number of false positive observations among high-risk patients by introducing the Highest-k Loss. The solution is to estimate the weights of the highest k scores with a differentiable estimation of the sorting operation and apply the weights to the loss function. We extracted 253,680 survey responses from a public dataset of the U.S. health survey system to define a diabetes prediction task. This study employs nested cross-validation as well as an aggregated model applied to an independent test set to systematically evaluate the proposed method. Compared with traditional binary cross entropy loss and Focal loss, the Highest-k loss improved the precision (positive predictive value) for the highest 1% scores by 0.05 (95% CI: 0.041-0.055), the highest 5% scores by 0.03 (95% CI: 0.024-0.032), and the highest 10% scores by 0.02 (95% CI: 0.016-0.021). The introduced Highest-k loss function addresses the problem of prevailing risk prediction models and offers a practical solution that focuses on patients with the k highest predictive scores who can realistically receive an intervention as opposed to the entire patient population.

Lifelong learning (LL) aims to improve a predictive model as the data source evolves continuously. Most work in this learning paradigm has focused on resolving the problem of ‘catastrophic forgetting,’ which refers to a notorious dilemma between improving model accuracy over new data and retaining accuracy over previous data. Yet, it is also known that machine learning (ML) models can be vulnerable in the sense that even tiny, adversarial input perturbations can deceive the models into producing erroneous predictions. This motivates the research objective of this paper – specification of a new LL framework that can salvage model robustness (against adversarial attacks) from catastrophic forgetting. Specifically, we propose a new memory-replay LL strategy that leverages modern bi-level optimization techniques to determine the ‘coreset’ of the current data (i.e., a small amount of data to be memorized) for ease of preserving adversarial robustness over time. We term the resulting LL framework ‘Data-Efficient Robustness-Preserving LL’ (DERPLL). The effectiveness of DERPLL is evaluated for class-incremental image classification using ResNet-18 over the CIFAR-10 dataset. Experimental results show that DERPLL outperforms the conventional coreset-guided LL baseline and achieves a substantial improvement in both standard accuracy and robust accuracy.

Large-scale computations are ubiquitous and demand exorbitant resources, with matrix multiplication being a prominent example. Multiplying high-dimensional matrices is cumbersome for an individual server but is frequently needed in many applications. To alleviate the computational cost, one can take a low-rank approximation of the matrix product and distribute it over multiple workers. However, the tail latency of such distributed computations is degraded by straggling workers. One solution is to query extra workers with coded inputs to replace the outputs of straggling workers; this technique is called "coded computing." Nearly all existing coded computing schemes apply to multiplying any matrices. Instead, we propose a new framework to design coded computing schemes to take advantage of the structure induced by compression, which we call compression-informed coded computing. We then showcase the benefits of the framework in two steps. First, we illustrate how sketching can lead to linear dependencies in the matrices multiplied by the workers. Second, we apply locality-based coded computing to leverage these linear dependencies to make do with fewer workers compared to coded computing schemes that ignore the structure of the matrices being multiplied.

Recalibrating probabilistic classifiers is vital for enhancing the reliability and accuracy of predictive models. Despite the development of numerous recalibration algorithms, there is still a lack of a comprehensive theory that integrates calibration and sharpness (which is essential for maintaining predictive power). In this paper, we introduce the concept of minimum-risk recalibration within the framework of mean-squared-error (MSE) decomposition, offering a principled approach for evaluating and recalibrating probabilistic classifiers. Using this framework, we analyze the uniform-mass binning (UMB) recalibration method and establish a finite-sample risk upper bound of order $\tilde{O}(B/n + 1/B^2)$ where $B$ is the number of bins and $n$ is the sample size. By balancing calibration and sharpness, we further determine that the optimal number of bins for UMB scales with $n^{1/3}$, resulting in a risk bound of approximately $O(n^{-2/3})$. Additionally, we tackle the challenge of label shift by proposing a two-stage approach that adjusts the recalibration function using limited labeled data from the target domain. Our results show that transferring a calibrated classifier requires significantly fewer target samples compared to recalibrating from scratch. We validate our theoretical findings through numerical simulations, which confirm the tightness of the proposed bounds, the optimal number of bins, and the effectiveness of label shift adaptation.

Many applications benefit from theory relevant to the identification of variables having large correlations or partial correlations in high dimension. Recently there has been progress in the ultra-high dimensional setting when the sample size$n$is fixed and the dimension$p$tends to infinity. Despite these advances, the correlation screening framework suffers from practical, methodological and theoretical deficiencies. For instance, previous correlation screening theory requires that the population covariance matrix be sparse and block diagonal. This block sparsity assumption is however restrictive in practical applications. As a second example, correlation and partial correlation screening requires the estimation of dependence measures, which can be computationally prohibitive. In this paper, we propose a unifying approach to correlation and partial correlation mining that is not restricted to block diagonal correlation structure, thus yielding a methodology that is suitable for modern applications. By making connections to random geometric graphs, the number of highly correlated or partial correlated variables are shown to have compound Poisson finite-sample characterizations, which hold for both the finite$p$case and when$p$tends to infinity. The unifying framework also demonstrates a duality between correlation and partial correlation screening with theoretical and practical consequences.

Using the 20 questions estimation framework with query-dependent noise, we study non-adaptive search strategies for a moving target over the unit cube with unknown initial location and velocities under a piecewise constant velocity model. In this search problem, there is an oracle who knows the instantaneous location of the target at any time. Our task is to query the oracle as few times as possible to accurately estimate the location of the target at any specified time. We first study the case where the oracle’s answer to each query is corrupted by discrete noise and then generalize our results to the case of additive white Gaussian noise. In our formulation, the performance criterion is the resolution, which is defined as the maximal$L_{\infty} $distance between the true locations and estimated locations. We characterize the minimal resolution of an optimal non-adaptive query procedure with a finite number of queries by deriving non-asymptotic and asymptotic bounds. Our bounds are tight in the first-order asymptotic sense when the number of queries satisfies a certain condition and our bounds are tight in the stronger second-order asymptotic sense when the target moves with a constant velocity. To prove our results, we relate the current problem to channel coding, borrow ideas from finite blocklength information theory and construct bounds on the number of possible quantized target trajectories.

In this work, we propose a method for speeding up linear regression distributively, while ensuring security. We leverage randomized sketching techniques, and improve straggler resilience in asynchronous systems. Specifically, we apply a random orthonormal matrix and then subsample in blocks, to simultaneously secure the information and reduce the dimension of the regression problem. In our setup, the transformation corresponds to an encoded encryption in an approximate gradient coding scheme, and the subsampling corresponds to the responses of the non-straggling workers; in a centralized coded computing network. We focus on the special case of the Subsampled Randomized Hadamard Transform, which we generalize to block sampling; and discuss how it can be used to secure the data.

We revisit the outlier hypothesis testing framework of Li et al. (TIT 2014) and derive fundamental limits for the optimal test under the generalized Neyman-Pearson criterion. In outlier hypothesis testing, one is given multiple observed sequences, where most sequences are generated i.i.d. from a nominal distribution. The task is to discern the set of outlying sequences that are generated according to anomalous distributions. The nominal and anomalous distributions are unknown. We consider the case of multiple outlying sequences where the number of outlying sequences is unknown and each outlying sequence can follow a different anomalous distribution. Under this setting, we study the tradeoff among the probabilities of misclassification error, false alarm and false reject. Specifically, we propose a threshold-based test that ensures exponential decay of misclassification error and false alarm probabilities. We study two constraints on the false reject probability, with one constraint being that it is a non-vanishing constant and the other being that it has an exponential decay rate. For both cases, we derive bounds on the false reject probability, as a function of the threshold, for each tuple of nominal and anomalous distributions.

BACKGROUND: Development of new methods for analysis of protein-protein interactions (PPIs) at molecular and nanometer scales gives insights into intracellular signaling pathways and will improve understanding of protein functions, as well as other nanoscale structures of biological and abiological origins. Recent advances in computational tools, particularly the ones involving modern deep learning algorithms, have been shown to complement experimental approaches for describing and rationalizing PPIs. However, most of the existing works on PPI predictions use protein-sequence information, and thus have difficulties in accounting for the three-dimensional organization of the protein chains. RESULTS: In this study, we address this problem and describe a PPI analysis based on a graph attention network, named Struct2Graph, for identifying PPIs directly from the structural data of folded protein globules. Our method is capable of predicting the PPI with an accuracy of 98.89% on the balanced set consisting of an equal number of positive and negative pairs. On the unbalanced set with the ratio of 1:10 between positive and negative pairs, Struct2Graph achieves a fivefold cross validation average accuracy of 99.42%. Moreover, Struct2Graph can potentially identify residues that likely contribute to the formation of the protein-protein complex. The identification of important residues is tested for two different interaction types: (a) Proteins with multiple ligands competing for the same binding area, (b) Dynamic protein-protein adhesion interaction. Struct2Graph identifies interacting residues with 30% sensitivity, 89% specificity, and 87% accuracy. CONCLUSIONS: In this manuscript, we address the problem of prediction of PPIs using a first of its kind, 3D-structure-based graph attention network (code available at https://github.com/baranwa2/Struct2Graph ). Furthermore, the novel mutual attention mechanism provides insights into likely interaction sites through its unsupervised knowledge selection process. This study demonstrates that a relatively low-dimensional feature embedding learned from graph structures of individual proteins outperforms other modern machine learning classifiers based on global protein features. In addition, through the analysis of single amino acid variations, the attention mechanism shows preference for disease-causing residue variations over benign polymorphisms, demonstrating that it is not limited to interface residues.

We study the problem of simultaneous search for multiple targets over a multidimensional unit cube and derive fundamental resolution limits of non-adaptive querying procedures using the 20 questions estimation framework. The performance criterion that we consider is the achievable resolution, which is defined as the maximal$L_\infty $norm between the location vector and its estimated version where the maximization is over all target location vectors. The fundamental resolution limit is defined as the minimal achievable resolution of any non-adaptive query procedure, where each query has binary yes/no answers. We drive non-asymptotic and second-order asymptotic bounds on the minimal achievable resolution, using tools from finite blocklength information theory. Specifically, in the achievability part, we relate the 20 questions problem to data transmission over a multiple access channel, use the information spectrum method by Han and borrow results from finite blocklength analysis for random access channel coding. In the converse part, we relate the 20 questions problem to data transmission over a point-to-point channel and adapt finite blocklength converse results for channel coding. Our results extend the purely first-order asymptotic analyses of Kaspiet al.(ISIT 2015) for the one-dimensional case: we consider channels beyond the binary symmetric channel and derive non-asymptotic and second-order asymptotic bounds on the performance of optimal non-adaptive query procedures.

Graph convolutional networks (GCNs) are a widely used method for graph representation learning. To elucidate their capabilities and limitations for graph classification, we investigate their power to generate well-separated embedding vectors for graphs sampled from different random graph models, which correspond to different class-conditional distributions in a classification problem. It has been recognized that metric properties of learned representations are important for reduction of complexity of classifiers trained on them. Additionally, we show that inability to generate well-separated embedding vectors for two different graph models implies information-theoretic indistinguishability of these models based on noise-perturbed embedding vectors of sample graphs. We consider graph models arising from graphons, which parametrize all infinite exchangeable graph models. We precisely characterize, in terms of degree profile closeness, the set of graphon pairs that are indistinguishable (in metric and information-theoretic senses) by a GCN with depth at least logarithmic in sample graph size. Outside this set, a very simple architecture suffices for distinguishability. We then exhibit a concrete, infinite set of graphon pairs that are well-separated in cut distance and are indistinguishable by a GCN. These results theoretically match empirical observations of several prior works. Finally, we give empirical results on synthetic and real graph classification datasets, giving some indication that degree profile closeness gives rise to indistinguishability of graph distributions in real datasets, even beyond our theoretical framework.

We revisit the outlier hypothesis testing framework of Liet al.(TIT 2014) and derive fundamental limits for the optimal test under the generalized Neyman-Pearson criterion. In outlier hypothesis testing, one is given multiple observed sequences, where most sequences are generated i.i.d. from a nominal distribution. The task is to discern the set of outlying sequences that are generated from anomalous distributions. The nominal and anomalous distributions areunknown. We study the tradeoff among the probabilities of misclassification error, false alarm and false reject for tests that satisfy weak conditions on the rate of decrease of these error probabilities as a function of sequence length. Specifically, we propose a threshold-based test that ensures exponential decay of misclassification error and false alarm probabilities. We study two constraints on the false reject probability, with one constraint being that it is a non-vanishing constant and the other being that it has an exponential decay rate. For both cases, we characterize bounds on the false reject probability, as a function of the threshold, for each pair of nominal and anomalous distributions and demonstrate the optimality of our test under the generalized Neyman-Pearson criterion. We first consider the case of at most one outlying sequence and then generalize our results to the case of multiple outlying sequences where the number of outlying sequences is unknown and each outlying sequence can follow a different anomalous distribution.

One of the most common operations in signal processing is matrix multiplication. However, it presents a major computational bottleneck when the matrix dimension is high, as can occur for large data size or feature dimension. Two different approaches to overcoming this bottleneck are: 1) low rank approximation of the matrix product; and 2) distributed computation. We propose a scheme that combines these two approaches. To enable distributed low rank approximation, we generalize the approximate matrix CR-multiplication to accommodate weighted block sampling, and we introduce a weighted coded matrix multiplication method. This results in novel approximate weighted CR coded matrix multiplication schemes, which achieve improved performance for distributed matrix multiplication and are robust to stragglers.

Sparse representation has been widely used in data compression, signal and image denoising, dimensionality reduction and computer vision. While overcomplete dictionaries are required for sparse representation of multidimensional data, orthogonal bases represent one-dimensional data well. In this paper, we propose a data-driven sparse representation using orthonormal bases under the lossless compression constraint. We show that imposing such constraint under the Minimum Description Length (MDL) principle leads to a unique and optimal sparse representation for one-dimensional data, which results in discriminative features useful for data discovery.

We establish fundamental limits of tracking a moving target over the unit cube under the framework of 20 questions with measurement-dependent noise. In this problem, there is an oracle who knows the instantaneous location of a target. Our task is to query the oracle as few times as possible to accurately estimate the trajectory of the moving target, whose initial location and velocity is unknown. We study the case where the oracle’s answer to each query is corrupted by random noise with query-dependent discrete distribution. In our formulation, the performance criterion is the resolution, which is defined as the maximal absolute value between the true location and estimated location at each discrete time during the searching process. We are interested in the minimal resolution of any non-adaptive searching procedure with a finite number of queries and derive approximations to this optimal resolution via the second-order asymptotic analysis.

We propose a new graphical model inference procedure, called SG-PALM, for learning conditional dependency structure of high-dimensional tensor-variate data. Unlike most other tensor graphical models the proposed model is interpretable and computationally scalable to high dimension. Physical interpretability follows from the Sylvester generative (SG) model on which SG-PALM is based: the model is exact for any observation process that is a solution of a partial differential equation of Poisson type. Scalability follows from the fast proximal alternating linearized minimization (PALM) procedure that SG-PALM uses during training. We establish that SG-PALM converges linearly (i.e., geometric convergence rate) to a global optimum of its objective function. We demonstrate scalability and accuracy of SG-PALM for an important but challenging climate prediction problem: spatio-temporal forecasting of solar flares from multimodal imaging data.

We study the achievable performance of adaptive query procedures for the noisy 20 questions problem with measurement-dependent noise over a unit cube of finite dimension. The performance criterion that we consider is the minimal resolution, defined as the$L$∞norm between the estimated and the true values of the random location vector of a target, given a finite number of queries constrained by an excess-resolution probability. Specifically, we derive the achievable resolution of an adaptive query procedure based on the variable length feedback code by Polyanskiy et al. (TIT 2011). Furthermore, we verify our theoretical results with numerical simulations and compare the performance of our considered adaptive query procedure with that of certain state-of-the-art algorithms, such as the sorted posterior matching algorithm by Chiu and Javadi (ITW 2016). In particular, we demonstrate that the termination strategy adopted in our adaptive query procedure can significantly enhance the asymptotic performance of adaptive query procedures, especially at moderate to large excess-resolution probability constraints.

We study the problem of simultaneous search for multiple targets over a multidimensional unit cube and derive the fundamental resolution limit of non-adaptive querying procedures using the 20 questions estimation framework. The performance criterion that we consider is the achievable resolution, which is defined as the maximal$L$∞norm between the location vector and its estimated version where the maximization is over the possible location vectors of all targets. The fundamental resolution limit is then defined as the minimal achievable resolution of any nonadaptive query procedure. We drive the second-order asymptotic bound on the minimal achievable resolution by relating the current problem to a data transmission problem over a multiple access channel, using the information spectrum by Han and borrowing results from finite blocklength information theory for random access channel coding. Our results extend the purely first-order asymptotic analyses of Kaspi et al. (ISIT 2015) for the one-dimensional case. Specifically, we consider more general channels, derive the second-order asymptotic result and establish a phase transition phenomenon.

Motivated by practical machine learning applications, we revisit the outlying sequence detection problem (Li et al., TIT 2014) and derive fundamental limits of optimal detection when the reject option is allowed for outlying sequences. In the considered outlying sequence detection (OSD) problem, one is given multiple observed sequences, where all sequences are generated i.i.d. from a nominal distribution with at most one exception. The task is to discern the outlying sequence that is generated according to an anomalous distribution. In OSD, the nominal and anomalous distributions are unknown. In this paper, we consider the case where there is a reject option for the OSD, i.e., we reject the samples as insufficient for making a reliable decision (cf. Bartlett et al., JMLR 2008). We study the tradeoff among the probabilities of misclassification error, false alarm and false reject for tests that satisfy weak conditions on the rate of decrease of these error probabilities as a function of sequence length. We propose a second-order asymptotically optimal test that provides a finite sample approximation to the error probabilities.

Mutual information is a measure of the dependence between random variables that has been used successfully in myriad applications in many fields. Generalized mutual information measures that go beyond classical Shannon mutual information have also received much interest in these applications. We derive the mean squared error convergence rates of kernel density-based plug-in estimators of general mutual information measures between two multidimensional random variablesXandYfor two cases: 1)XandYare continuous; 2)XandYmay have a mixture of discrete and continuous components. Using the derived rates, we propose an ensemble estimator of these information measures called GENIE by taking a weighted sum of the plug-in estimators with varied bandwidths. The resulting ensemble estimators achieve the 1/N parametric mean squared error convergence rate when the conditional densities of the continuous variables are sufficiently smooth. To the best of our knowledge, this is the first nonparametric mutual information estimator known to achieve the parametric convergence rate for the mixture case, which frequently arises in applications (e.g. variable selection in classification). The estimator is simple to implement and it uses the solution to an offline convex optimization problem and simple plug-in estimators. A central limit theorem is also derived for the ensemble estimators and minimax rates are derived for the continuous case. We demonstrate the ensemble estimator for the mixed case on simulated data and apply the proposed estimator to analyze gene relationships in single cell data.

We establish fundamental limits on estimation accuracy for the noisy 20 questions problem with measurement-dependent noise and introduce optimal non-adaptive procedures that achieve these limits. The minimal achievable resolution is defined as the absolute difference between the estimated and the true locations of a target over a unit cube, given a finite number of queries constrained by the excess-resolution probability. Inspired by the relationship between the 20 questions problem and the channel coding problem, we derive non-asymptotic bounds on the minimal achievable resolution to estimate the target location. Furthermore, applying the Berry-Esseen theorem to our non-asymptotic bounds, we obtain a second-order asymptotic approximation to the achievable resolution of optimal non-adaptive query procedures with a finite number of queries subject to the excess-resolution probability constraint. We specialize our second-order results to measurement-dependent versions of several channel models including the binary symmetric, the binary erasure and the binary Z- channels. As a complement, we establish a second-order asymptotic achievability bound for adaptive querying and use this to bound the benefit of adaptive querying.

This paper introduces the Sylvester graphical lasso (SyGlasso) that captures multiway dependencies present in tensor-valued data. The model is based on the Sylvester equation that defines a generative model. The proposed model complements the tensor graphical lasso (Greenewald et al., 2019) that imposes a Kronecker sum model for the inverse covariance matrix, by providing an alternative Kronecker sum model that is generative and interpretable. A nodewise regression approach is adopted for estimating the conditional independence relationships among variables. The statistical convergence of the method is established, and empirical studies are provided to demonstrate the recovery of meaningful conditional dependency graphs. We apply the SyGlasso to an electroencephalography (EEG) study to compare the brain connectivity of alcoholic and nonalcoholic subjects. We demonstrate that our model can simultaneously estimate both the brain connectivity and its temporal dependencies.

A major hurdle in machine learning is scalability to massive datasets. Approaches to overcome this hurdle include compression of the data matrix and distributing the computations. Leverage score sampling provides a compressed approximation of a data matrix using an importance weighted subset. Gradient coding has been recently proposed in distributed optimization to compute the gradient using multiple unreliable worker nodes. By designing coding matrices, gradient coded computations can be made resilient to stragglers, which are nodes in a distributed network that degrade system performance. We present a novel weighted leverage score approach, that achieves improved performance for distributed gradient coding by utilizing an importance sampling.

We study fundamental limits of estimation accuracy for the noisy 20 questions problem with measurement-dependent noise and introduce optimal non-adaptive procedures that achieve these limits. The minimal achievable resolution is defined as the absolute difference between the estimated and the true values of the target random variable, given a finite number of queries constrained by the excess-resolution probability. Inspired by the relationship between the 20 questions problem and the channel coding problem, we derive non-asymptotic bounds on the minimal achievable resolution. Furthermore, applying the Berry-Esseen theorem to our non-asymptotic bounds, we obtain a second-order asymptotic approximation to finite blocklength performance, specifically the achievable resolution of optimal non-adaptive query procedures with a finite number of queries subject to the excess-resolution probability constraint.

A major hurdle in machine learning is scalability to massive datasets. One approach to overcoming this is to distribute the computational tasks among several workers. Gradient coding has been recently proposed in distributed optimization to compute the gradient of an objective function using multiple, possibly unreliable, worker nodes. By designing distributed coded schemes, gradient coded computations can be made resilient to stragglers, nodes with longer response time compared to other nodes in a distributed network. Most such schemes rely on operations over the real or complex numbers and are inherently numerically unstable. We present a binary scheme which avoids such operations, thereby enabling numerically stable distributed computation of the gradient. Also, some restricting assumptions in prior work are dropped, and a more efficient decoding is given.

Graph convolutional networks (GCNs) are a widely used method for graph representation learning. To elucidate the capabilities and limitations of GCNs, we investigate their power, as a function of their number of layers, to distinguish between different random graph models (corresponding to different class-conditional distributions in a classification problem) on the basis of the embeddings of their sample graphs. In particular, the graph models that we consider arise from graphons, which are the most general possible parameterizations of infinite exchangeable graph models and which are the central objects of study in the theory of dense graph limits. We give a precise characterization of the set of pairs of graphons that are indistinguishable by a GCN with nonlinear activation functions coming from a certain broad class if its depth is at least logarithmic in the size of the sample graph. This characterization is in terms of a degree profile closeness property. Outside this class, a very simple GCN architecture suffices for distinguishability. We then exhibit a concrete, infinite class of graphons arising from stochastic block models that are well-separated in terms of cut distance and are indistinguishable by a GCN. These results theoretically match empirical observations of several prior works on GCNs. To prove our results, we exploit a connection to random walks on graphs.

While Internet of Things (IoT) devices and sensors create continuous streams of information, Big Data infrastructures are deemed to handle the influx of data in realtime. One type of such a continuous stream of information is time series data. Due to the richness of information in time series and inadequacy of summary statistics to encapsulate structures and patterns in such data, development of new approaches to learn time series is of interest. In this paper, we propose a novel method, called pattern tree, to learn patterns in the times-series using a binary-structured tree. While a pattern tree can be used for many purposes such as lossless compression, prediction and anomaly detection, in this paper we focus on its application in time series estimation and forecasting. In comparison to other methods, our proposed pattern tree method improves the mean squared error of estimation.

MOTIVATION: Understanding the mechanisms and structural mappings between molecules and pathway classes are critical for design of reaction predictors for synthesizing new molecules. This article studies the problem of prediction of classes of metabolic pathways (series of chemical reactions occurring within a cell) in which a given biochemical compound participates. We apply a hybrid machine learning approach consisting of graph convolutional networks used to extract molecular shape features as input to a random forest classifier. In contrast to previously applied machine learning methods for this problem, our framework automatically extracts relevant shape features directly from input SMILES representations, which are atom-bond specifications of chemical structures composing the molecules. RESULTS: Our method is capable of correctly predicting the respective metabolic pathway class of 95.16% of tested compounds, whereas competing methods only achieve an accuracy of 84.92% or less. Furthermore, our framework extends to the task of classification of compounds having mixed membership in multiple pathway classes. Our prediction accuracy for this multi-label task is 97.61%. We analyze the relative importance of various global physicochemical features to the pathway class prediction problem and show that simple linear/logistic regression models can predict the values of these global features from the shape features extracted using our framework. AVAILABILITY AND IMPLEMENTATION: https://github.com/baranwa2/MetabolicPathwayPrediction. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We propose a new topic modeling procedure that takes advantage of the fact that the Latent Dirichlet Allocation (LDA) log-likelihood function is asymptotically equivalent to the logarithm of the volume of the topic simplex. This allows topic modeling to be reformulated as finding the probability simplex that minimizes its volume and encloses the documents that are represented as distributions over words. A convex relaxation of the minimum volume topic model optimization is proposed, and it is shown that the relaxed problem has the same global minimum as the original problem under the separability assumption and the sufficiently scattered assumption introduced by Arora et al. (2013) and Huang et al. (2016). A locally convergent alternating direction method of multipliers (ADMM) approach is introduced for solving the relaxed minimum volume problem. Numerical experiments illustrate the benefits of our approach in terms of computation time and topic recovery performance.

We propose a method for simultaneously detecting shared and unshared communities in heterogeneous multilayer weighted and undirected networks. The multilayer network is assumed to follow a generative probabilistic model that takes into account the similarities and dissimilarities between the communities. We make use of a variational Bayes approach for jointly inferring the shared and unshared hidden communities from multilayer network observations. We show that our approach outperforms state-of-the-art algorithms in detecting disparate (shared and private) communities on synthetic data as well as on real genome-wide fibroblast proliferation dataset.

The Mutual Information (MI) is an often used measure of dependency between two random variables utilized in information theory, statistics and machine learning. Recently several MI estimators have been proposed that can achieve parametric MSE convergence rate. However, most of the previously proposed estimators have high computational complexity of at least O(N2). We propose a unified method for empirical non-parametric estimation of general MI function between random vectors in d based on N i.i.d. samples. The reduced complexity MI estimator, called the ensemble dependency graph estimator (EDGE), combines randomized locality sensitive hashing (LSH), dependency graphs, and ensemble bias-reduction methods. We prove that EDGE achieves optimal computational complexity O(N), and can achieve the optimal parametric MSE rate of O(1/N) if the density is d times differentiable. To the best of our knowledge EDGE is the first non-parametric MI estimator that can achieve parametric MSE rates with linear time complexity. We illustrate the utility of EDGE for the analysis of the information plane (IP) in deep learning. Using EDGE we shed light on a controversy on whether or not the compression property of information bottleneck (IB) in fact holds for ReLu and other rectification functions in deep neural networks (DNN).

Feature selection and reducing the dimensionality of data is an essential step in data analysis. In this work we propose a new criterion for feature selection that is formulated as conditional information between features given the labeled variable. Instead of using the standard mutual information measure based on Kullback-Leibler divergence, we use our proposed criterion to filter out redundant features for the purpose of multiclass classification. This approach results in an efficient and fast non-parametric implementation of feature selection as it can be directly estimated using a geometric measure of dependency, the global Friedman-Rafsky (ΓR) multivariate run test statistic constructed by a global minimal spanning tree (MST). We demonstrate the advantages of our proposed feature selection approach through simulation. In addition the proposed feature selection method is applied to the MNIST data set.

We revisit the successive refinement problem with causal decoder side information considered by Maor and Merhav (2008) and strengthen their result by deriving an exponential strong converse theorem. To be specific, we show that for any rate-distortion tuple outside the rate-distortion region of the successive refinement problem with causal decoder side information, the excess-distortion probability approaches one exponentially fast. Our proof follows by judiciously adapting the recently proposed strong converse technique by Oohama using the information spectrum method, the variational form of the rate-distortion region and Hölder's inequality. The lossy source coding problem with causal decoder side information considered by El Gamal and Weissman is a special case of the current problem. Therefore, the exponential strong converse theorem for the El Gamal and Weissman problem follows as a corollary of our result.

In this paper, we design and analyze a new zeroth-order online algorithm, namely, the zeroth-order online alternating direction method of multipliers (ZOO-ADMM), which enjoys dual advantages of being gradient-free operation and employing the ADMM to accommodate complex structured regularizers. Compared to the first-order gradient-based online algorithm, we show that ZOO-ADMM requires $\sqrt{m}$ times more iterations, leading to a convergence rate of $O(\sqrt{m}/\sqrt{T})$, where $m$ is the number of optimization variables, and $T$ is the number of iterations. To accelerate ZOO-ADMM, we propose two minibatch strategies: gradient sample averaging and observation averaging, resulting in an improved convergence rate of $O(\sqrt{1+q^{-1}m}/\sqrt{T})$, where $q$ is the minibatch size. In addition to convergence analysis, we also demonstrate ZOO-ADMM to applications in signal processing, statistics, and machine learning.

We propose a scalable divergence estimation method based on hashing. Consider two continuous random variables $X$ and $Y$ whose densities have bounded support. We consider a particular locality sensitive random hashing, and consider the ratio of samples in each hash bin having non-zero numbers of Y samples. We prove that the weighted average of these ratios over all of the hash bins converges to f-divergences between the two samples sets. We derive the MSE rates for two families of smooth functions; the Hölder smoothness class and differentiable functions. In particular, it is proved that if the density functions have bounded derivatives up to the order $d$, where $d$ is the dimension of samples, the optimal parametric MSE rate of $O(1/N)$ can be achieved. The computational complexity is shown to be $O(N)$, which is optimal. To the best of our knowledge, this is the first empirical divergence estimator that has optimal computational complexity and can achieve the optimal parametric MSE estimation rate of $O(1/N)$.

In this paper, we explore how network centrality and network entropy can be used to identify a bifurcation network event. A bifurcation often occurs when a network undergoes a qualitative change in its structure as a response to internal changes or external signals. In this paper, we show that network centrality allows us to capture important topological properties of dynamic networks. By extracting multiple centrality features from a network for dimensionality reduction, we are able to track the network dynamics underlying an intrinsic low-dimensional manifold. Moreover, we employ von Neumann graph entropy (VNGE) to measure the information divergence between networks over time. In particular, we propose an asymptotically consistent estimator of VNGE so that the cubic complexity of VNGE is reduced to quadratic complexity that scales more gracefully with network size. Finally, the effectiveness of our approaches is demonstrated through a real-life application of cyber intrusion detection.

We propose a non-adaptive unequal error protection (UEP) querying policy based on superposition coding for the noisy 20 questions problem. In this problem, a player wishes to successively refine an estimate of the value of a continuous random variable by posing binary queries and receiving noisy responses. When the queries are designed non-adaptively as a single block and the noisy responses are modeled as the outputs of a binary symmetric channel the 20 questions problem can be mapped to an equivalent problem of channel coding with UEP. A new non-adaptive querying strategy based on UEP superposition coding is introduced whose estimation error decreases with an exponential rate of convergence that is significantly better than that of the UEP repetition coding introduced by Variani et al. (2015). In fact, we show that the proposed non-adaptive UEP querying policy achieves the same order convergence rate as the adaptive policy.

In many real-world applications, data is not collected as one batch, but sequentially over time, and often it is not possible or desirable to wait until the data is completely gathered before analyzing it. Thus, we propose a framework to sequentially update a maximum margin classifier by taking advantage of the Maximum Entropy Discrimination principle. Our maximum margin classifier allows for a kernel representation to represent large numbers of features and can also be regularized with respect to a smooth sub-manifold, allowing it to incorporate unlabeled observations. We compare the performance of our classifier to its non-sequential equivalents in both simulated and real datasets.

Meta learning of optimal classifier error rates allows an experimenter to empirically estimate the intrinsic ability of any estimator to discriminate between two populations, circumventing the difficult problem of estimating the optimal Bayes classifier. To this end we propose a weighted nearest neighbor (WNN) graph estimator for a tight bound on the Bayes classification error; the Henze-Penrose (HP) divergence. Similar to recently proposed HP estimators [1], the proposed estimator is non-parametric and does not require density estimation. However, unlike previous approaches the proposed estimator is rate-optimal, i.e., its mean squared estimation error (MSEE) decays to zero at the fastest possible rate of O(1/M+1/N) where M, N are the sample sizes of the respective populations. We illustrate the proposed WNN meta estimator for several simulated and real data sets.

Henze-Penrose divergence is a non-parametric divergence measure that can be used to estimate a bound on the Bayes error in a binary classification problem. In this paper, we show that a cross-match statistic based on optimal weighted matching can be used to directly estimate Henze-Penrose divergence. Unlike an earlier approach based on the Friedman-Rafsky minimal spanning tree statistic, the proposed method is dimension-independent. The new approach is evaluated using simulation and applied to real datasets to obtain Bayes error estimates.

We consider query-based data acquisition and the corresponding information recovery problem, where the goal is to recover k binary variables (information bits) from parity measurements of those variables. The queries and the corresponding parity measurements are designed using the encoding rule of Fountain codes. By using Fountain codes, we can design potentially limitless number of queries, and corresponding parity measurements, and guarantee that the original k information bits can be recovered with high probability from any sufficiently large set of measurements of size n. In the query design, the average number of information bits that is associated with one parity measurement is called query difficulty (d̅) and the minimum number of measurements required to recover the k information bits for a fixed d̅ is called sample complexity (n). We analyze the fundamental trade-offs between the query difficulty and the sample complexity, and show that the sample complexity of n = c max{k,(k log k)/d̅} for some constant c > 0 is necessary and sufficient to recover k information bits with high probability as k→∞.

Data-driven anomaly detection methods suffer from the drawback of detecting all instances that are statistically rare, irrespective of whether the detected instances have realworld significance or not. In this paper, we are interested in the problem of specifically detecting anomalous instances that are known to have high real-world utility, while ignoring the low-utility statistically anomalous instances. To this end, we propose a novel method called Latent Laplacian Maximum Entropy Discrimination (LatLapMED) as a potential solution. This method uses the EM algorithm to simultaneously incorporate the Geometric Entropy Minimization principle for identifying statistical anomalies, and the Maximum Entropy Discrimination principle to incorporate utility labels, in order to detect highutility anomalies. Here, we apply our method in both simulated and real datasets to demonstrate that it has superior performance over existing alternatives that independently pre-process with unsupervised anomaly detection algorithms before classifying.

In this paper, we propose an open-loop unequal-error-protection querying policy based on superposition coding for the noisy 20 questions problem. In this problem, a player wishes to successively refine an estimate of the value of a continuous random variable by posing binary queries and receiving noisy responses. When the queries are designed non-adaptively as a single block and the noisy responses are modeled as the output of a binary symmetric channel, the 20 questions problem can be mapped to an equivalent problem of channel coding with unequal error protection (UEP). A new non-adaptive querying strategy based on UEP superposition coding is introduced, whose estimation error decreases with an exponential rate of convergence that is significantly better than that of the UEP repetition coding introduced by Variani et al. (2015). With the proposed querying strategy, the rate of exponential decrease in the number of queries matches the rate of a closed-loop adaptive scheme, where queries are sequentially designed with the benefit of feedback. Furthermore, the achievable error exponent is significantly better than that of random block codes employing equal error protection.

One of the longstanding problems in spectral graph clustering (SGC) is the so-called model order selection problem: automated selection of the correct number of clusters. This is equivalent to the problem of finding the number of connected components or communities in an undirected graph. In this paper, we propose AMOS, an automated model order selection algorithm for SGC. Based on a recent analysis of clustering reliability for SGC under the random interconnection model, AMOS works by incrementally increasing the number of clusters, estimating the quality of identified clusters, and providing a series of clustering reliability tests. Consequently, AMOS outputs clusters of minimal model order with statistical clustering reliability guarantees. Comparing to three other automated graph clustering methods on real-world datasets, AMOS shows superior performance in terms of multiple external and internal clustering metrics.

In this paper, we are interested in learning the underlying graph structure behind training data. Solving this basic problem is essential to carry out any graph signal processing or machine learning task. To realize this, we assume that the data is smooth with respect to the graph topology, and we parameterize the graph topology using an edge sampling function. That is, the graph Laplacian is expressed in terms of a sparse edge selection vector, which provides an explicit handle to control the sparsity level of the graph. We solve the sparse graph learning problem given some training data in both the noiseless and noisy settings. Given the true smooth data, the posed sparse graph learning problem can be solved optimally and is based on simple rank ordering. Given the noisy data, we show that the joint sparse graph learning and denoising problem can be simplified to designing only the sparse edge selection vector, which can be solved using convex optimization.

We focus on the problem of distributed optimization for multi-agent networks via distributed dual averaging (DDA) over an evolving network of growing connectivity. It is known that the convergence rate of DDA is influenced by the algebraic connectivity of the underlying network, where better connectivity leads to faster convergence. However, the effect of the growth of network connectivity on the convergence rate has not been fully understood. This paper provides a tractable approach to analyze the improvement in the convergence rate of DDA induced by the growth of network connectivity. This analysis is applicable, for example, to successive refinement strategies in massive multi-core optimizers where an increasing number of local data passage edges are successively added between cores in order to accelerate total run time. Compared to the existing convergence results, our analysis gives tighter bounds on the convergence of DDA over networks of growing connectivity. Numerical experiments show that our analysis leads to orders of improvement for evaluating convergence rate, which is not captured by existing analysis.

We study the sensor selection problem for field estimation, where a best subset of sensors is activated to monitor a spatially correlated random field. Different from most commonly used centralized selection algorithms, we propose a decentralized architecture where sensor selection can be carried out in a distributed way and by the sensors themselves. A decentralized approach is essential since each sensor has access only to the information (e.g., correlation) in its neighborhood. To make distributed optimization possible, we decompose the global cost function into local cost functions that require only the information in local neighborhoods of sensors. We then employ the alternating direction method of multipliers (ADMM) to solve the proposed sensor selection problem. In our algorithm, each sensor solves small-scale optimization problems, and communicates directly only with its immediate neighbors. Numerical results are provided to show the effectiveness of our approach.

Information theoretic measures (e.g. the Kullback Liebler divergence and Shannon mutual information) have been used for exploring possibly nonlinear multivariate dependencies in high dimension. If these dependencies are assumed to follow a Markov factor graph model, this exploration process is called structure discovery. For discrete-valued samples, estimates of the information divergence over the parametric class of multinomial models lead to structure discovery methods whose mean squared error achieves parametric convergence rates as the sample size grows. However, a naive application of this method to continuous nonparametric multivariate models converges much more slowly. In this paper we introduce a new method for nonparametric structure discovery that uses weighted ensemble divergence estimators that achieve parametric convergence rates and obey an asymptotic central limit theorem that facilitates hypothesis testing and other types of statistical validation.

We introduce an adaptive version of directed information to estimate an influence graph over nodes with time-varying features. Originally developed as a generalization of the Shannon Mutual Information for quantifying the effect of feedback in a simple communication channel, directed information (DI) measures the amount of causal, time-varying influence that one node's actions have on another node. By estimating these quantities, we can infer a directed graph that captures the flow of influence between nodes. We introduce an online time-averaged version of DI called adaptive directed information (ADI) to study the difference in graphical structure over time. This method is applied to two Twitter US political datasets to track changes in the graphical structure between candidates' Twitter feeds.

Since pedestrians in videos have a wide range of appearances such as body poses, occlusions, and complex backgrounds, pedestrian detection is a challengeable task. In this paper, we propose part-level fully convolutional networks (FCN) for pedestrian detection. We adopt deep learning to deal with the proposal shifting problem in pedestrian detection. First, we combine convolutional neural networks (CNN) and FCN to align bounding boxes for pedestrians. Then, we perform part-level pedestrian detection based on CNN to recall the lost body parts. Experimental results demonstrate that the proposed method achieves 6.83% performance improvement in log-average miss rate over CifarNet.

We derive the mean squared error convergence rates of kernel density-based plug-in estimators of mutual information measures between two multidimensional random variables X and Y for two cases: 1) X and Y are both continuous; 2) X is continuous and Y is discrete. Using the derived rates, we propose an ensemble estimator of these information measures for the second case by taking a weighted sum of the plug-in estimators with varied bandwidths. The resulting ensemble estimator achieves the 1 /N parametric convergence rate when the conditional densities of the continuous variables are sufficiently smooth. To the best of our knowledge, this is the first nonparametric mutual information estimator known to achieve the parametric convergence rate for this case, which frequently arises in applications (e.g. variable selection in classification). The estimator is simple to implement as it uses the solution to an offline convex optimization problem and simple plug-in estimators. Ensemble estimators that achieve the parametric rate are also derived for the first case (X and Y are both continuous) and another case: 3) X and Y may have any mixture of discrete and continuous components.

We propose a direct estimation method for Rényi and f-divergence measures based on a new graph theoretical interpretation. Suppose that we are given two sample sets X and Y, respectively with N and M samples, where η := M/N is a constant value. Considering the k-nearest neighbor (k-NN) graph of Y in the joint data set (X, Y), we show that the average powered ratio of the number of X points to the number of Y points among all k-NN points is proportional to Rényi divergence of X and Y densities. A similar method can also be used to estimate f-divergence measures. We derive bias and variance rates, and show that for the class of γ-Hölder smooth functions, the estimator achieves the MSE rate of O(N-2γ/(γ+d)). Furthermore, by using a weighted ensemble estimation technique, for density functions with continuous and bounded derivatives of up to the order d, and some extra conditions at the support set boundary, we derive an ensemble estimator that achieves the parametric MSE rate of O(1/N). Our estimator requires no boundary correction, and remarkably, the boundary issues do not show up. Our approach is also more computationally tractable than other competing estimators, which makes them appealing in many practical applications.

We show a direct relationship between the variance and the differential entropy for subclasses of symmetric and asymmetric unimodal distributions by providing an upper bound on variance in terms of entropy power. Combining this bound with the well-known entropy power lower bound on variance, we prove that the variance of the appropriate subclasses of unimodal distributions can be bounded below and above by the scaled entropy power. As the differential entropy decreases, the variance is sandwiched between two exponentially decreasing functions in the differential entropy. This establishes that for the subclasses of unimodal distributions, the differential entropy can be used as a surrogate for concentration of the distribution.

This paper proposes a general adaptive procedure for budget-limited predictor design in high dimensions called two-stage Sampling, Prediction and Adaptive Regression via Correlation Screening (SPARCS). The SPARCS can be applied to high-dimensional prediction problems in experimental science, medicine, finance, and engineering, as illustrated by the following. Suppose that one wishes to run a sequence of experiments to learn a sparse multivariate predictor of a dependent variable Y (disease prognosis for instance) based on a p dimensional set of independent variables X = [X1,..., Xp]T(assayed biomarkers). Assume that the cost of acquiring the full set of variables X increases linearly in its dimension. The SPARCS breaks the data collection into two stages in order to achieve an optimal tradeoff between sampling cost and predictor performance. In the first stage, we collect a few (n) expensive samples {yi, si}i=1n, at the full dimension p ≫ n of X, winnowing the number of variables down to a smaller dimension l <; p using a type of cross correlation or regression coefficient screening. In the second stage, we collect a larger number (t - n) of cheaper samples of the l variables that passed the screening of the first stage. At the second stage, a low-dimensional predictor is constructed by solving the standard regression problem using all t samples of the selected variables. The SPARCS is an adaptive online algorithm that implements false positive control on the selected variables, is well suited to small sample sizes, and is scalable to high dimensions. We establish asymptotic bounds for the familywise error rate, specify high dimensional convergence rates for support recovery, and establish optimal sample allocation rules to the first and second stages.

In this paper, we explore the three-node multiterminal lossy source coding problem, which seems to offer a formidable mathematical complexity. We derive an inner bound to the general rate-distortion region of this problem, which is a natural extension of the seminal work by Kaspi on the interactive two-terminal source coding problem. It is shown that this (rather involved) inner bound contains several rate-distortion regions of some relevant source coding settings. In this way, besides the non-trivial extension of the interactive two terminal problem, our results can be seen as a generalization and hence unification of several previous works in the field. By specializing the inner bound to particular cases, we obtain some novel rate-distortion regions for several multi-terminal lossy source coding problems.

Many modern datasets can be represented as graphs and hence spectral decompositions such as graph principal component analysis (PCA) can be useful. Distinct from previous graph decomposition approaches based on subspace projection of a single topological feature, e.g., the Fiedler vector of centered graph adjacency matrix (graph Laplacian), we propose spectral decomposition approaches to graph PCA and graph dictionary learning that integrate multiple features, including graph walk statistics, centrality measures and graph distances to reference nodes. In this paper we propose a new PCA method for single graph analysis, called multi-centrality graph PCA (MC-GPCA), and a new dictionary learning method for ensembles of graphs, called multi-centrality graph dictionary learning (MC-GDL), both based on spectral decomposition of multi-centrality matrices. As an application to cyber intrusion detection, MC-GPCA can be an effective indicator of anomalous connectivity pattern and MC-GDL can provide discriminative basis for attack classification.

Head movement during scanning introduces artificial signal changes and impedes activation detection in fMRI studies. The head motion in fMRI acquired using slice-based Echo Planar Imaging (EPI) sequence can be estimated and compensated by aligning the images onto a reference volume through image registration. Registering EPI images volume by volume fails to consider head motion between slices, leading to biased head motion estimates. Slice-to-volume registration is used to estimate motion parameters for each slice by more accurately representing the image acquisition sequence. However, it is prone to image noise and geometric distortion, resulting in high variance estimates. In this work, we propose a Gaussian particle filter based head motion tracking algorithm to reduce the image misregistration errors. The algorithm models head motion by using a dynamic state space model (SSM) to model continuous slice acquisition thereby providing more accurate motion estimates and voxel position estimates. We demonstrate significant performance improvement of the proposed approach as compared to previous registration-only methods of head motion estimation.

High frequency oscillations (HFOs) are a promising biomarker of epileptic brain tissue and activity. HFOs additionally serve as a prototypical example of challenges in the analysis of discrete events in high-temporal resolution, intracranial EEG data. Two primary challenges are 1) dimensionality reduction, and 2) assessing feasibility of classification. Dimensionality reduction assumes that the data lie on a manifold with dimension less than that of the features space. However, previous HFO analysis have assumed a linear manifold, global across time, space (i.e. recording electrode/channel), and individual patients. Instead, we assess both a) whether linear methods are appropriate and b) the consistency of the manifold across time, space, and patients. We also estimate bounds on the Bayes classification error to quantify the distinction between two classes of HFOs (those occurring during seizures and those occurring due to other processes). This analysis provides the foundation for future clinical use of HFO features and guides the analysis for other discrete events, such as individual action potentials or multi-unit activity.

In this paper, a generalization of the Gaussian quasi likelihood ratio test (GQLRT) for simple hypotheses is developed. The proposed generalization, called measure-transformed GQLRT (MT-GQLRT), selects a Gaussian probability model that best empirically fits a transformed probability measure of the data. By judicious choice of the transform we show that, unlike the GQLRT, the proposed test can gain sensitivity to higher-order statistical moments and resilience to outliers leading to significant mitigation of the model mismatch effect on the decision performance. Under some mild regularity conditions we show that the proposed test statistic is asymptotically normal. A data driven procedure for optimal selection of the measure transformation parameters is developed that maximizes an empirical estimate of the asymptotic power given a fixed empirical asymptotic size. The MT-GQLRT is applied to signal classification in a simulation example that illustrates its sensitivity to higher-order statistical moments and resilience to outliers.

In this paper, we propose an unequal error protection coding strategy based on superposition coding for the noisy 20 questions problem. In this problem, a player wishes to successively refine an estimate of the value of a continuous random variable by posing binary queries and receiving noisy responses. When the queries are designed non-adaptively as a single block and the noisy responses are modeled as the output of a binary symmetric channel the 20 questions problem can be mapped to an equivalent problem of channel coding with unequal error protection (UEP). A superposition coding strategy with UEP is introduced that has error exponent that is significantly better than that of the UEP repetition code introduced by Variani et al. [1].

Recent work has focused on the problem of non-parametric estimation of divergence functionals. Many existing approaches are restrictive in their assumptions on the density support or require difficult calculations at the support boundary which must be known a priori. We derive the MSE convergence rate of a leave-one-out kernel density plug-in divergence functional estimator for general bounded density support sets where knowledge of the support boundary is not required. We generalize the theory of optimally weighted ensemble estimation to derive two estimators that achieve the parametric rate when the densities are sufficiently smooth. The asymptotic distribution of these estimators and tuning parameter selection guidelines are provided. Based on the theory, we propose an empirical estimator of Rényi-α divergence that outperforms the standard kernel density plug-in estimator, especially in higher dimensions.

The performance of MIMO radar has been a subject of intense study in the past decades. For such a system, however, the important phenomenon of phase transition has received little attention in the literature. In this paper, we study the phase transition on the target detection probability of a SNR maximizing detector. Such a detector declares a target to be present when the largest eigenvalue of the observed data matrix exceeds a threshold. In particular, we identify a critical value below and above which the limiting detection performance is described by the Tracy-Widom law and the Gaussian law, respectively. Under both laws, the scaling limits and asymptotic expansions of misdetection probability at the vanishing regime are derived using tools from random matrix theory.

MOTIVATION: Topological domains have been proposed as the backbone of interphase chromosome structure. They are regions of high local contact frequency separated by sharp boundaries. Genes within a domain often have correlated transcription. In this paper, we present a computational efficient spectral algorithm to identify topological domains from chromosome conformation data (Hi-C data). We consider the genome as a weighted graph with vertices defined by loci on a chromosome and the edge weights given by interaction frequency between two loci. Laplacian-based graph segmentation is then applied iteratively to obtain the domains at the given compactness level. Comparison with algorithms in the literature shows the advantage of the proposed strategy. RESULTS: An efficient algorithm is presented to identify topological domains from the Hi-C matrix. AVAILABILITY AND IMPLEMENTATION: The Matlab source code and illustrative examples are available at http://bionetworks.ccmb.med.umich.edu/ CONTACT: : [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Consider the problem of designing a panel of complex biomarkers to predict a patient's health or disease state when one can pair his or her current test sample, called a target sample, with the patient's previously acquired healthy sample, called a reference sample. As contrasted to a population averaged reference this reference sample is individualized. Automated predictor algorithms that compare and contrast the paired samples to each other could result in a new generation of test panels that compare to a person's healthy reference to enhance predictive accuracy. This paper develops such an individualized predictor and illustrates the added value of including the healthy reference for design of predictive gene expression panels. RESULTS: The objective is to predict each subject's state of infection, e.g., neither exposed nor infected, exposed but not infected, pre-acute phase of infection, acute phase of infection, post-acute phase of infection. Using gene microarray data collected in a large scale serially sampled respiratory virus challenge study we quantify the diagnostic advantage of pairing a person's baseline reference with his or her target sample. The full study consists of 2886 microarray chips assaying 12,023 genes of 151 human volunteer subjects under 4 different inoculation regimes (HRV, RSV, H1N1, H3N2). We train (with cross-validation) reference-aided sparse multi-class classifier algorithms on this data to show that inclusion of a subject's reference sample can improve prediction accuracy by as much as 14 %, for the H3N2 cohort, and by at least 6 %, for the H1N1 cohort. Remarkably, these gains in accuracy are achieved by using smaller panels of genes, e.g., 39 % fewer for H3N2 and 31 % fewer for H1N1. The biomarkers selected by the predictors fall into two categories: 1) contrasting genes that tend to differentially express between target and reference samples over the population; 2) reinforcement genes that remain constant over the two samples, which function as housekeeping normalization genes. Many of these genes are common to all 4 viruses and their roles in the predictor elucidate the function that they play in differentiating the different states of host immune response. CONCLUSIONS: If one uses a suitable mathematical prediction algorithm, inclusion of a healthy reference in biomarker diagnostic testing can potentially improve accuracy of disease prediction with fewer biomarkers.

When can reliable inference be drawn in the “Big Data” context? This paper presents a framework for answering this fundamental question in the context of correlation mining, with implications for general large-scale inference. In large-scale data applications like genomics, connectomics, and eco-informatics, the data set is often variable rich but sample starved: a regime where the number n of acquired samples (statistical replicates) is far fewer than the number p of observed variables (genes, neurons, voxels, or chemical constituents). Much of recent work has focused on understanding the computational complexity of proposed methods for “Big Data.” Sample complexity, however, has received relatively less attention, especially in the setting when the sample size n is fixed, and the dimension p grows without bound. To address this gap, we develop a unified statistical framework that explicitly quantifies the sample complexity of various inferential tasks. Sampling regimes can be divided into several categories: 1) the classical asymptotic regime where the variable dimension is fixed and the sample size goes to infinity; 2) the mixed asymptotic regime where both variable dimension and sample size go to infinity at comparable rates; and 3) the purely high-dimensional asymptotic regime where the variable dimension goes to infinity and the sample size is fixed. Each regime has its niche but only the latter regime applies to exa-scale data dimension. We illustrate this high-dimensional framework for the problem of correlation mining, where it is the matrix of pairwise and partial correlations among the variables that are of interest. Correlation mining arises in numerous applications and subsumes the regression context as a special case. We demonstrate various regimes of correlation mining based on the unifying perspective of high-dimensional learning rates and sample complexity for different structured covariance models and different inference tasks.

We consider the problem of identifying patterns in a data set that exhibits anomalous behavior, often referred to as anomaly detection. Similarity-based anomaly detection algorithms detect abnormally large amounts of similarity or dissimilarity, e.g., as measured by the nearest neighbor Euclidean distances between a test sample and the training samples. In many application domains, there may not exist a single dissimilarity measure that captures all possible anomalous patterns. In such cases, multiple dissimilarity measures can be defined, including nonmetric measures, and one can test for anomalies by scalarizing using a nonnegative linear combination of them. If the relative importance of the different dissimilarity measures are not known in advance, as in many anomaly detection applications, the anomaly detection algorithm may need to be executed multiple times with different choices of weights in the linear combination. In this paper, we propose a method for similarity-based anomaly detection using a novel multicriteria dissimilarity measure, the Pareto depth. The proposed Pareto depth analysis (PDA) anomaly detection algorithm uses the concept of Pareto optimality to detect anomalies under multiple criteria without having to run an algorithm multiple times with different choices of weights. The proposed PDA approach is provably better than using linear combinations of the criteria, and shows superior performance on experiments with synthetic and real data sets.

This paper presents a Bayesian algorithm for linear spectral unmixing that accounts for outliers present in the data. The proposed model assumes that the pixel reflectances are linear mixtures of unknown endmembers, corrupted by an additional term modelling outliers and additive Gaussian noise. A Markov random field is considered for outlier detection based on the spatial and spectral structures of the anomalies. This allows outliers to be identified in particular regions and wavelengths of the data cube. A Bayesian algorithm is proposed to estimate the parameters involved in the model yielding a joint linear unmixing and outlier detection algorithm. Simulations conducted with synthetic data demonstrate the accuracy of the proposed unmixing and outlier detection strategy for the analysis of hyperspectral images.

In this paper, we study the sensitivity of the spectral clustering based community detection algorithm subject to a Erdos-Renyi type random noise model. We prove phase transitions in community detectability as a function of the external edge connection probability and the noisy edge presence probability under a general network model where two arbitrarily connected communities are interconnected by random external edges. Specifically, the community detection performance transitions from almost perfect detectability to low detectability as the intercommunity edge connection probability exceeds some critical value.We derive upper and lower bounds on the critical value and show that the bounds are identical when the two communities have the same size. The phase transition results are validated using network simulations. Using the derived expressions for the phase transition threshold we propose a method for estimating this threshold from observed data.

Significant attention has been given to minimizing a penalized least squares criterion for estimating sparse solutions to large linear systems of equations. The penalty induces sparsity and the natural choice is the so-called l0norm. In this paper we develop a Momentumized Iterative Shrinkage Thresholding (MIST) algorithm for minimizing the resulting non-convex criterion and prove its convergence to a local minimizer. Simulations on large data sets show superior performance of the proposed method to other methods.

Social networks often encode community structure using multiple distinct types of links between nodes. In this paper we introduce a novel method to extract information from such multi-layer networks, where each type of link forms its own layer. Using the concept of Pareto optimality, community detection in this multi-layer setting is formulated as a multiple criterion optimization problem. We propose an algorithm for finding an approximate Pareto frontier containing a family of solutions. The power of this approach is demonstrated on a Twitter dataset, where the nodes are hashtags and the layers correspond to (1) behavioral edges connecting pairs of hashtags whose temporal profiles are similar and (2) relational edges connecting pairs of hashtags that appear in the same tweets.

In this paper, we consider the problem of estimating a deterministic vector parameter when the likelihood function is unknown or not expressible. We develop an estimator, called measure-transformed quasi maximum likelihood estimator (MT-QMLE), that minimizes the empirical Kullback-Leibler divergence between the transformed probability measure of the data and a hypothesized Gaussian probability distribution. By judicious choice of the transform we show that the proposed estimator can gain sensitivity to higher-order statistical information and resilience to outliers. Under some regularity conditions we show that the MT-QMLE is consistent, asymptotically normal and unbiased. Furthermore, we derive a necessary and sufficient condition for its asymptotic efficiency. The MT-QMLE is applied to source localization in a simulation example that illustrates its sensitivity to higher-order information and resilience to outliers.

In this paper, we consider multi-sensor classification when there is a large number of unlabeled samples. The problem is formulated under the multi-view learning framework and a Consensus-based Multi-View Maximum Entropy Discrimination (CMV-MED) algorithm is proposed. By iteratively maximizing the stochastic agreement between multiple classifiers on the unlabeled dataset, the algorithm simultaneously learns multiple high accuracy classifiers. We demonstrate that our proposed method can yield improved performance over previous multi-view learning approaches by comparing performance on three real multi-sensor data sets.

We propose a coercive approach to simultaneously register and segment multi-modal images which share similar spatial structure. Registration is done at the region level to facilitate data fusion while avoiding the need for interpolation. The algorithm performs alternating minimization of an objective function informed by statistical models for pixel values in different modalities. Hypothesis tests are developed to determine whether to refine segmentations by splitting regions. We demonstrate that our approach has significantly better performance than the state-of-the-art registration and segmentation methods on microscopy images.

The problem of quickest detection of a change in the distribution of a n × p random matrix based on a sequence of observations having a single unknown change point is considered. The forms of the pre- and post-change distributions of the rows of the matrices are assumed to belong to the family of elliptically contoured densities with sparse dispersion matrices but are otherwise unknown. We propose a non-parametric stopping rule that is based on a novel summary statistic related to k-nearest neighbor correlation between columns of each observed random matrix. In the large scale regime of p → ∞ and n fixed we show that, among all functions of the proposed summary statistic, the proposed stopping rule is asymptotically optimal under a minimax quickest change detection (QCD) model.

The rate-distortion regions of cooperative and interactive source coding is studied and characterized in several important special cases. For the general cooperative and interactive three node source coding problem, we present an improved inner bound with respect to the bound derived in [1]. This inner bound is used to characterize the optimal rate-distortion regions of several special cases of three terminal information sharing protocols.

The Fisher information matrix (FIM) is a foundational concept in statistical signal processing. The FIM depends on the probability distribution, assumed to belong to a smooth parametric family. Traditional approaches to estimating the FIM require estimating the probability distribution function (PDF), or its parameters, along with its gradient or Hessian. However, in many practical situations the PDF of the data is not known but the statistician has access to an observation sample for any parameter value. Here we propose a method of estimating the FIM directly from sampled data that does not require knowledge of the underlying PDF. The method is based on non-parametric estimation of an f-divergence over a local neighborhood of the parameter space and a relation between curvature of the f-divergence and the FIM. Thus we obtain an empirical estimator of the FIM that does not require density estimation and is asymptotically consistent. We empirically evaluate the validity of our approach using two experiments.

This letter considers statistical estimation problems where the probability distribution of the observed random variable is invariant with respect to actions of a finite topological group. It is shown that any such distribution must satisfy a restricted finite mixture representation. When specialized to the case of distributions over the sphere that are invariant to the actions of a finite spherical symmetry group G, a group-invariant extension of the Von Mises Fisher (VMF) distribution is obtained. The G-invariant VMF is parameterized by location and scale parameters that specify the distribution's mean orientation and its concentration about the mean, respectively. Using the restricted finite mixture representation these parameters can be estimated using an Expectation Maximization (EM) maximum likelihood (ML) estimation algorithm. This is illustrated for the problem of mean crystal orientation estimation under the spherically symmetric group associated with the crystal form, e.g., cubic or octahedral or hexahedral. Simulations and experiments establish the advantages of the extended VMF EM-ML estimator for data acquired by Electron Backscatter Diffraction (EBSD) microscopy of a polycrystalline Nickel alloy sample.

Most content-based image retrieval systems consider either one single query, or multiple queries that include the same object or represent the same semantic information. In this paper, we consider the content-based image retrieval problem for multiple query images corresponding to different image semantics. We propose a novel multiple-query information retrieval algorithm that combines the Pareto front method with efficient manifold ranking. We show that our proposed algorithm outperforms state of the art multiple-query retrieval algorithms on real-world image databases. We attribute this performance improvement to concavity properties of the Pareto fronts, and prove a theoretical result that characterizes the asymptotic concavity of the fronts.

This paper studies adaptive sensing for estimating the nonzero amplitudes of a sparse signal with the aim of providing analytical guarantees on the performance gain due to adaptive resource allocation. We consider a previously proposed optimal two-stage policy for allocating sensing resources. For positive powers q, we derive tight upper bounds on the mean qth-power error resulting from the optimal two-stage policy and corresponding lower bounds on the improvement over nonadaptive uniform sensing. It is shown that the adaptation gain is related to the detectability of nonzero signal components as characterized by Chernoff coefficients, thus quantifying analytically the dependence on the sparsity level of the signal, the signal-to-noise ratio (SNR), and the sensing resource budget. For fixed sparsity levels and increasing SNR or sensing budget, we obtain the rate of convergence to oracle performance and the rate at which the fraction of resources spent on the first exploratory stage decreases to zero. For a vanishing fraction of nonzero components, the gain increases without bound as a function of SNR and sensing budget. Numerical simulations demonstrate that the bounds on adaptation gain are quite tight in nonasymptotic regimes as well.

In this paper, a new centrality called local Fiedler vector centrality (LFVC) is proposed to analyze the connectivity structure of a graph. It is associated with the sensitivity of algebraic connectivity to node or edge removals and features distributed computations via the associated graph Laplacian matrix. We prove that LFVC can be related to a monotonic submodular set function that guarantees that greedy node or edge removals come within a factor 1-1/e of the optimal non-greedy batch removal strategy. Due to the close relationship between graph topology and community structure, we use LFVC to detect deep and overlapping communities on real-world social network datasets. The results offer new insights on community detection by discovering new significant communities and key members in the network. Notably, LFVC is also shown to significantly outperform other well-known centralities for community detection.

Incorporating spatial information into hyperspectral unmixing procedures has been shown to have positive effects, due to the inherent spatial-spectral duality in hyperspectral scenes. Current research works that consider spatial information are mainly focused on the linear mixing model. In this paper, we investigate a variational approach to incorporating spatial correlation into a nonlinear unmixing procedure. A nonlinear algorithm operating in reproducing kernel Hilbert spaces, associated with an ℓ1local variation norm as the spatial regularizer, is derived. Experimental results, with both synthetic and real data, illustrate the effectiveness of the proposed scheme.

Recently, major attention has been given to penalized log-likelihood estimators for sparse precision (inverse covariance) matrices. The penalty is responsible for inducing sparsity, and a very common choice is the convex l1norm. However, it is not always the case that the best estimator is achieved with this penalty. So, to improve sparsity and reduce biases associated with the l1norm, one must move to non-convex penalties such as the lq(0 ≤ qqpenalized log-likelihood problem, and derive the corresponding optimality conditions. A novel cyclic descent algorithm is presented for penalized log-likelihood optimization, and we show how the derived conditions can be used to reduce algorithm computation. We illustrate by comparing reconstruction quality over the range 0 ≤ q ≤ 1 for several experiments.

In this paper, we introduce a new framework for robust multiple signal classification (MUSIC). The proposed framework, called robust measure-transformed (MT) MUSIC, is based on applying a transform to the probability distribution of the received signals, i.e., transformation of the probability measure defined on their observation space. In robust MT-MUSIC, the sample covariance is replaced by the empirical MT-covariance. By judicious choice of the transform we show that: (1) the resulting empirical MT-covariance is B-robust, with bounded influence function that takes negligible values for large norm outliers, and (2) under the assumption of spherical compound Gaussian noise, the noise subspace can be determined from the eigendecomposition of the MT-covariance. The proposed approach is illustrated for direction-of-arrival (DOA) estimation in a simulation example that shows its advantages as compared to other robust MUSIC generalizations.

In this paper, we propose an efficient algorithm to train a robust large-margin classifier, when corrupt measurements caused by sensor failure might be present in the training set. By incorporating a non-parametric prior based on the empirical distribution of the training data, we propose a Geometric-Entropy-Minimization regularized Maximum Entropy Discrimination (GEM-MED) method to perform classification and anomaly detection in a joint manner. We demonstrate that our proposed method can yield improved performance over previous robust classification methods in terms of both classification accuracy and anomaly detection rate using simulated data and real footstep data.

Sunspots, as seen in white light or continuum images, are associated with regions of high magnetic activity on the Sun, visible on magnetogram images. Their complexity is correlated with explosive solar activity and so classifying these active regions is useful for predicting future solar activity. Current classification of sunspot groups is visually based and suffers from bias. Supervised learning methods can reduce human bias but fail to optimally capitalize on the information present in sunspot images. This paper uses two image modalities (continuum and magnetogram) to characterize the spatial and modal interactions of sunspot and magnetic active region images and presents a new approach to cluster the images. Specifically, in the framework of image patch analysis, we estimate the number of intrinsic parameters required to describe the spatial and modal dependencies, the correlation between the two modalities and the corresponding spatial patterns, and examine the phenomena at different scales within the images. To do this, we use linear and nonlinear intrinsic dimension estimators, canonical correlation analysis, and multiresolution analysis of intrinsic dimension.

Gaussian graphical models (GGM) have been widely used in many high-dimensional applications ranging from biological and financial data to recommender systems. Sparsity in GGM plays a central role both statistically and computationally. Unfortunately, real-world data often does not fit well to sparse graphical models. In this paper, we focus on a family of latent variable Gaussian graphical models (LVGGM), where the model is conditionally sparse given latent variables, but marginally non-sparse. In LVGGM, the inverse covariance matrix has a low-rank plus sparse structure, and can be learned in a regularized maximum likelihood framework. We derive novel parameter estimation error bounds for LVGGM under mild conditions in the high-dimensional setting. These results complement the existing theory on the structural learning, and open up new possibilities of using LVGGM for statistical inference.

f-divergence estimation is an important problem in the fields of information theory, machine learning, and statistics. While several divergence estimators exist, relatively few of their convergence rates are known. We derive the MSE convergence rate for a density plug-in estimator of f-divergence. Then by applying the theory of optimally weighted ensemble estimation, we derive a divergence estimator with a convergence rate of O (1 over T) that is simple to implement and performs well in high dimensions. We validate our theoretical results with experiments.

The Generalized Markov Lemma has been used in the proofs of several multiterminal source coding theorems for finite alphabets. An alternative approach to extend this result to countable infinite sources is proposed. We establish sufficient conditions to guarantee the joint typicality of reproduction sequences of random descriptions that have not been necessarily generated from the product of probability measures. Compared to existing proofs for finite alphabets, our technique is simpler and self-contained. It also offers bounds on the asymptotic tail probability of the typicality event providing a scaling law for a large number of source encoders.

The three-node multiterminal lossy source coding problem is investigated. We derive an inner bound to the general rate-distortion region of this problem which appears to be the natural extension of the seminal work by Kaspi [1] on the interactive two-terminal source coding problem. It is shown that this -rather involved- inner bound contains several rate-distortion regions of some relevant source coding settings. In this way, besides the non-trivial extension of the interactive two terminal problem, our results can be seen as a generalization and hence unification of several previous works in the field.

Socially-based recommendation systems have recently attracted significant interest, and a number of studies have shown that social information can dramatically improve a system's predictions of user interests. Meanwhile, there are now many potential applications that involve aspects of both recommendation and information retrieval, and the task of collaborative retrieval---a combination of these two traditional problems---has recently been introduced. Successful collaborative retrieval requires overcoming severe data sparsity, making additional sources of information, such as social graphs, particularly valuable. In this paper we propose a new model for collaborative retrieval, and show that our algorithm outperforms current state-of-the-art approaches by incorporating information from social networks. We also provide empirical analyses of the ways in which cultural interests propagate along a social graph using a real-world music dataset.

We consider the problem of 20 questions with noise for multiple players under the minimum entropy criterion in the setting of stochastic search, with application to target localization. Each player yields a noisy response to a binary query governed by a certain error probability. First, we propose a sequential policy for constructing questions that queries each player in sequence and refines the posterior of the target location. Second, we consider a joint policy that asks all players questions in parallel at each time instant and characterize the structure of the optimal policy for constructing the sequence of questions. This generalizes the single player probabilistic bisection method for stochastic search problems. Third, we prove an equivalence between the two schemes showing that, despite the fact that the sequential scheme has access to a more refined filtration, the joint scheme performs just as well on average. Fourth, we establish convergence rates of the mean-square error and derive error exponents. Finally, we obtain an extension to the case of unknown error probabilities. This framework provides a mathematical model for incorporating a human in the loop for active machine learning systems.

We introduce a new approach to variable selection, called Predictive Correlation Screening, for predictor design. Predictive Correlation Screening (PCS) implements false positive control on the selected variables, is well suited to small sample sizes, and is scalable to high dimensions. We establish asymptotic bounds for Familywise Error Rate (FWER), and resultant mean square error of a linear predictor on the selected variables. We apply Predictive Correlation Screening to the following two-stage predictor design problem. An experimenter wants to learn a multivariate predictor of gene expressions based on successive biological samples assayed on mRNA arrays. She assays the whole genome on a few samples and from these assays she selects a small number of variables using Predictive Correlation Screening. To reduce assay cost, she subsequently assays only the selected variables on the remaining samples, to learn the predictor coefficients. We show superiority of Predictive Correlation Screening relative to LASSO and correlation learning (sometimes popularly referred to in the literature as marginal regression or simple thresholding) in terms of performance and computational complexity.

We consider distributed estimation of the inverse covariance matrix, also called the concentration matrix, in Gaussian graphical models. Traditional centralized estimation often requires iterative and expensive global inference and is therefore difficult in large distributed networks. In this paper, we propose a general framework for distributed estimation based on a maximum marginal likelihood (MML) approach. Each node independently computes a local estimate by maximizing a marginal likelihood defined with respect to data collected from its local neighborhood. Due to the non-convexity of the MML problem, we derive and consider solving a convex relaxation. The local estimates are then combined into a global estimate without the need for iterative message-passing between neighborhoods. We prove that this relaxed MML estimator is asymptotically consistent. Through numerical experiments on several synthetic and real-world data sets, we demonstrate that the two-hop version of the proposed estimator is significantly better than the one-hop version, and nearly closes the gap to the centralized maximum likelihood estimator in many situations.

We consider the problem of 20 questions with noise for collaborative players under the minimum entropy criterion [1] in the setting of stochastic search, with application to target localization. First, assuming conditionally independent collaborators, we characterize the structure of the optimal policy for constructing the sequence of questions. This generalizes the single player probabilistic bisection method [1, 2] for stochastic search problems. Second, we prove a separation theorem showing that optimal joint queries achieve the same performance as a greedy sequential scheme. Third, we establish convergence rates of the mean-square error (MSE). Fourth, we derive upper bounds on the MSE of the sequential scheme. This framework provides a mathematical model for incorporating a human in the loop for active machine learning systems.

We propose a multistage adaptive approach to spectrum sensing and estimation with the goal of concentrating more sensing resources on spectral components of interest. The allocation of resources to minimize the mean squared estimation error is formulated as a dynamic program. An optimal policy is given for the case of two sensing stages. For more than two stages, tractable approximate policies are developed based on open-loop feedback control (OLFC). These policies improve monotonically with the number of stages, and in particular upon the optimal two-stage policy. A spectrum sensing simulation shows substantial reductions in mean squared error compared to non-adaptive sensing and a recently proposed adaptive method. Performance gains in detecting unoccupied channels are also shown.

We propose a segmentation and anomaly detection method for electron backscatter diffraction (EBSD) images. In contrast to conventional methods that require Euler angles to be extracted from diffraction patterns, the proposed method operates on the patterns directly. We use a forward model implemented as a dictionary of diffraction patterns generated by a detailed physics-based simulation of EBSD. The combination of full diffraction patterns and a dictionary allows anomalies to be detected at the same time as grains are segmented, and also increases robustness to noise and instrument blur. The proposed method is demonstrated on a sample of the Ni-base alloy IN100.

The problem of deblurring an image when the blur kernel is unknown remains challenging after decades of work. Recently there has been rapid progress on correcting irregular blur patterns caused by camera shake, but there is still much room for improvement. We propose a new blind deconvolution method using incremental sparse edge approximation to recover images blurred by camera shake. We estimate the blur kernel first from only the strongest edges in the image, then gradually refine this estimate by allowing for weaker and weaker edges. Our method competes with the benchmark de-blurring performance of the state-of-the-art while being significantly faster and easier to generalize.

This paper presents a new method for estimating high dimensional covariance matrices. Our method, permuted rank-penalized least-squares (PRLS), is based on Kronecker product series expansions of the true covariance matrix. Assuming an i.i.d. Gaussian random sample, we establish high dimensional rates of convergence to the true covariance as both the number of samples and the number of variables go to infinity. For covariance matrices of low separation rank, our results establish that PRLS has significantly faster convergence than the standard sample covariance matrix (SCM) estimator. In addition, this framework allows one to tradeoff estimation error for approximation error, thus providing a scalable covariance estimation framework in terms of separation rank, an analog to low rank approximation of covariance matrices [1]. The MSE convergence rates generalize the high dimensional rates recently obtained for the ML Flip-flop algorithm [2], [3].

BACKGROUND: This paper introduces a new constrained model and the corresponding algorithm, called unsupervised Bayesian linear unmixing (uBLU), to identify biological signatures from high dimensional assays like gene expression microarrays. The basis for uBLU is a Bayesian model for the data samples which are represented as an additive mixture of random positive gene signatures, called factors, with random positive mixing coefficients, called factor scores, that specify the relative contribution of each signature to a specific sample. The particularity of the proposed method is that uBLU constrains the factor loadings to be non-negative and the factor scores to be probability distributions over the factors. Furthermore, it also provides estimates of the number of factors. A Gibbs sampling strategy is adopted here to generate random samples according to the posterior distribution of the factors, factor scores, and number of factors. These samples are then used to estimate all the unknown parameters. RESULTS: Firstly, the proposed uBLU method is applied to several simulated datasets with known ground truth and compared with previous factor decomposition methods, such as principal component analysis (PCA), non negative matrix factorization (NMF), Bayesian factor regression modeling (BFRM), and the gradient-based algorithm for general matrix factorization (GB-GMF). Secondly, we illustrate the application of uBLU on a real time-evolving gene expression dataset from a recent viral challenge study in which individuals have been inoculated with influenza A/H3N2/Wisconsin. We show that the uBLU method significantly outperforms the other methods on the simulated and real data sets considered here. CONCLUSIONS: The results obtained on synthetic and real data illustrate the accuracy of the proposed uBLU method when compared to other factor decomposition methods from the literature (PCA, NMF, BFRM, and GB-GMF). The uBLU method identifies an inflammatory component closely associated with clinical symptom scores collected during the study. Using a constrained model allows recovery of all the inflammatory genes in a single factor.

The problem of estimation of density functionals like entropy and mutual information has received much attention in the statistics and information theory communities. A large class of estimators of functionals of the probability density suffer from the curse of dimensionality, wherein the mean squared error decays increasingly slowly as a function of the sample sizeTas the dimensiondof the samples increases. In particular, the rate is often glacially slow of orderO(T-γ/d), where γ > 0 is a rate parameter. Examples of such estimators include kernel density estimators,k-nearest neighbor (k-NN) density estimators,k-NN entropy estimators, intrinsic dimension estimators, and other examples. In this paper, we propose a weighted affine combination of an ensemble of such estimators, where optimal weights can be chosen such that the weighted estimator converges at a much faster dimension invariant rate ofO(T1). Furthermore, we show that these optimal weights can be determined by solving a convex optimization problem which can be performed offline and does not require training data. We illustrate the superior performance of our weighted estimator for two important applications: 1) estimating the Panter-Dite distortion-rate factor; and 2) estimating the Shannon entropy for testing the probability distribution of a random sample.

This paper proposes an approach to infer neural interactions from EEG data using a James-Stein estimator of directed information called shrinkage optimized directed information assessment (SODA). SODA uses shrinkage regularization on empirical histograms to deal with the high dimensionality of multi-channel EEG signals and the small sizes of many real-world datasets. It is designed to make few a priori assumptions, and can handle both non-linear and non-Gaussian flows across electrode sites. The use of James-Stein shrinkage allows the SODA algorithm to achieve higher sensitivity to directed neural interactions for a given specificity. We augment this through a central limit theorem-based approach that can assess the statistical significance of each discovered interaction. When evaluated on brain computer interface EEG motor activity data the neural decoding obtained using SODA outperformed several state-of-the-art approaches including Granger causality, MI, unregularized directed information, and spatial coherence. Our results show that SODA localizes 30% more directed interactions in regions that are consistent with Brodmann functional areas of motor activity.

We introduce an efficient algorithm for performing distributed principal component analysis (PCA) on directed Gaussian graphical models. By exploiting structured sparsity in the Cholesky factor of the inverse covariance (concentration) matrix, our proposed DDPCA algorithm computes global principal subspace estimation through local computation and message passing. We show significant performance and computation/communication advantages of DDPCA for online principal subspace estimation and distributed anomaly detection in real-world computer networks.

System provisioning is the problem of determining the number of resources required to accomplish a complicated system level task, e.g. tracking or discriminating between N targets. This is a central problem in multi-target tracking with synthetic aperture radars where the number of targets can easily exceed the available resources. This paper treats the following conservative sensor provisioning problem: dynamically assign R platforms to process N moving targets in a way that guarantees that the radar maintains track on all targets. We propose a solution to this problem that guarantees a prescribed level of system performance, e.g., multiple target detection and position uncertainty levels, regardless of the scenario. The operational context of the paper is computational provisioning in synthetic aperture radar (SAR) that dynamically assigns different computers to tracking different targets.

We introduce a sparse covariance estimation method for the high dimensional setting when the covariance matrix decomposes as a Kronecker product, i.e., Σ0= A0⊗ B0, and the observations are Gaussian. We propose an ℓ1penalized maximum-likelihood approach to solve this problem. The dual formulation motivates an iterative algorithm (penalized flip-flop; FFP) based on a block coordinate-descent approach. Although the ℓ1-penalized log-likelihood function (objective function) is non-convex in general and non-smooth, we show that FFP converges to a local maximum under relatively mild assumptions. For the fixed dimension case, large-sample statistical consistency is proved and a rate of convergence bound is derived. Simulations show that FFP outperforms its non-penalized counterpart and the naive Glasso algorithm for sparse Kronecker-decomposable covariance matrix.

This work addresses the problem of correlation detection in a group of elliptically-contoured variables, when the number p of variates greatly exceeds the number n of observed samples. We exploit the properties inherent to the Z-score representation of the data set to devise two different decision tests, whose performances are assessed by upper bounding the Type I and Type II error probabilities. The results specifically apply to the asymptotic regime where the number of variates p is large, and the number of samples n is finite and fixed.

We consider the problem of identifying patterns in a data set that exhibit anomalous behavior, often referred to as anomaly detection. In most anomaly detection algorithms, the dissimilarity between data samples is calculated by a single criterion, such as Euclidean distance. However, in many cases there may not exist a single dissimilarity measure that captures all possible anomalous patterns. In such a case, multiple criteria can be defined, and one can test for anomalies by scalarizing the multiple criteria by taking some linear combination of them. If the importance of the different criteria are not known in advance, the algorithm may need to be executed multiple times with different choices of weights in the linear combination. In this paper, we introduce a novel non-parametric multi-criteria anomaly detection method using Pareto depth analysis (PDA). PDA uses the concept of Pareto optimality to detect anomalies under multiple criteria without having to run an algorithm multiple times with different choices of weights. The proposed PDA approach scales linearly in the number of criteria and is provably better than linear combinations of the criteria.

The problem of estimation of entropy functionals of probability densities has received much attention in the information theory, machine learning and statistics communities. Kernel density plug-in estimators are simple, easy to implement and widely used for estimation of entropy. However, kernel plug-in estimators suffer from the curse of dimensionality, wherein the MSE rate of convergence is glacially slow - of order $O(T^{-{\gamma}/{d}})$, where $T$ is the number of samples, and $\gamma>0$ is a rate parameter. In this paper, it is shown that for sufficiently smooth densities, an ensemble of kernel plug-in estimators can be combined via a weighted convex combination, such that the resulting weighted estimator has a superior parametric MSE rate of convergence of order $O(T^{-1})$. Furthermore, it is shown that these optimal weights can be determined by solving a convex optimization problem which does not require training data or knowledge of the underlying density, and therefore can be performed offline. This novel result is remarkable in that, while each of the individual kernel plug-in estimators belonging to the ensemble suffer from the curse of dimensionality, by appropriate ensemble averaging we can achieve parametric convergence rates.

We propose a solution to the image deconvolution problem where the convolution kernel or point spread function (PSF) is assumed to be only partially known. Small perturbations generated from the model are exploited to produce a few principal components explaining the PSF uncertainty in a high-dimensional space. Unlike recent developments on blind deconvolution of natural images, we assume the image is sparse in the pixel basis, a natural sparsity arising in magnetic resonance force microscopy (MRFM). Our approach adopts a Bayesian Metropolis-within-Gibbs sampling framework. The performance of our Bayesian semi-blind algorithm for sparse images is superior to previously proposed semi-blind algorithms such as the alternating minimization algorithm and blind algorithms developed for natural images. We illustrate our myopic algorithm on real MRFM tobacco virus data.

One of the most important problems in large-scale inference problems is the identification of variables that are highly dependent on several other variables. When dependence is measured by partial correlations, these variables identify those rows of the partial correlation matrix that have several entries with large magnitudes, i.e., hubs in the associated partial correlation graph. This paper develops theory and algorithms for discovering such hubs from a few observations of these variables. We introduce a hub screening framework in which the user specifies both a minimum (partial) correlation$\rho $and a minimum degree$\delta $to screen the vertices. The choice of$\rho $and$\delta $can be guided by our mathematical expressions for the phase transition correlation threshold$\rho _{c}$governing the average number of discoveries. They can also be guided by our asymptotic expressions for familywise discovery rates under the assumption of large number$p$of variables, fixed number$n$of multivariate samples, and weak dependence. Under the null hypothesis that the dispersion (covariance) matrix is sparse, these limiting expressions can be used to enforce familywise error constraints and to rank the discoveries in order of increasing statistical significance. For$n\ll p$, the computational complexity of the proposed partial correlation screening method is low and is therefore highly scalable. Thus, it can be applied to significantly larger problems than previous approaches. The theory is applied to discovering hubs in a high-dimensional gene microarray dataset.

This paper introduces a class of${\rm k}$-nearest neighbor ($k$-NN) estimators called bipartite plug-in (BPI) estimators for estimating integrals of nonlinear functions of a probability density, such as Shannon entropy and Rényi entropy. The density is assumed to be smooth, have bounded support, and be uniformly bounded from below on this set. Unlike previous$k$-NN estimators of nonlinear density functionals, the proposed estimator uses data-splitting and boundary correction to achieve lower mean square error. Specifically, we assume that$T$i.i.d. samples$ {\bf X}_{i} \in \BBR ^{d}$from the density are split into two pieces of cardinality$M$and$N$, respectively, with$M$samples used for computing a$k$-NN density estimate and the remaining$N$samples used for empirical estimation of the integral of the density functional. By studying the statistical properties of$k$-NN balls, explicit rates for the bias and variance of the BPI estimator are derived in terms of the sample size, the dimension of the samples, and the underlying probability distribution. Based on these results, it is possible to specify optimal choice of tuning parameters$M/T$,$k$for maximizing the rate of decrease of the mean square error. The resultant optimized BPI estimator converges faster and achieves lower mean squared error than previous$k$-NN entropy estimators. In addition, a central limit theorem is established for the BPI estimator that allows us to specify tight asymptotic confidence intervals.

We propose a novel framework for multimodal video indexing and retrieval using shrinkage optimized directed information assessment (SODA) as similarity measure. The directed information (DI) is a variant of the classical mutual information which attempts to capture the direction of information flow that videos naturally possess. It is applied directly to the empirical probability distributions of both audio-visual features over successive frames. We utilize RASTA-PLP features for audio feature representation and SIFT features for visual feature representation. We compute the joint probability density functions of audio and visual features in order to fuse features from different modalities. With SODA, we further estimate the DI in a manner that is suitable for high dimensional featurespand small sample sizen(largepsmalln) between pairs of video-audio modalities. We demonstrate the superiority of the SODA approach in video indexing, retrieval, and activity recognition as compared to the state-of-the-art methods such as hidden Markov models (HMM), support vector machine (SVM), cross-media indexing space (CMIS), and other noncausal divergence measures such as mutual information (MI). We also demonstrate the success of SODA in audio and video localization and indexing/retrieval of data with missaligned modalities.

This paper investigates a Bayesian model and a Markov chain Monte Carlo (MCMC) algorithm for gene factor analysis. Each sample in the dataset is decomposed as a linear combination of characteristic gene signatures (also referred to as factors) following a linear mixing model. To enforce the sparsity of the relative contribution (called factor score) of each gene signature to a specific sample, constrained Bernoulli-Gaussian distributions are elected as prior distributions for these factor scores. This distribution allows one to ensure non-negativity and full-additivity constraints for the scores that are interpreted as concentrations. The complexity of the resulting Bayesian estimators is alleviated by using a Gibbs sampler which generates samples distributed according to the posterior distribution of interest. These samples are then used to approximate the standard maximum a posteriori (MAP) or minimum mean square error (MMSE) estimators. The accuracy of the proposed Bayesian method is illustrated by simulations conducted on synthetic and real data.

In this paper, we present a novel entropy estimator for a given set of samples drawn from an unknown probability density function (PDF). Counter to other entropy estimators, the estimator presented here is parametric. The proposed estimator uses the maximum entropy principle to offer an to-term approximation to the underlying distribution and does not rely on local density estimation. The accuracy of the proposed algorithm is analyzed and it is shown that the estimation error is ≤ O(√(log n/n)). In addition to the analytic results, a numerical evaluation of the estimator on synthetic data as well as on experimental sensor network data is provided. We demonstrate a significant improvement in accuracy relative to other methods.

We consider estimation of a sparse parameter vector that determines the covariance matrix of a Gaussian random vector via a sparse expansion into known "basis matrices." Using the theory of reproducing kernel Hilbert spaces, we derive lower bounds on the variance of estimators with a given mean function. This includes unbiased estimation as a special case. We also present a numerical comparison of our lower bounds with the variance of two standard estimators (hard-thresholding estimator and maximum likelihood estimator).

Disease occurs due to aberrant modulation of biological pathways. Identification of activated gene pathways from gene expression data is an important problem. In this work, we develop a framework identifying activated pathways that incorporates cellular location of the gene, using gene ontology databases, in addition to gene expression data. This information is combined using Laplacian Eigenmaps to co embed these data into a low dimensional manifold. Model based clustering is then performed to identify biologically relevant activated pathways in the gene expression data. We illustrate the effectiveness of our manifold embedding approach for the problem of extracting immune system pathways from a macrophage gene expression dataset [11].

We propose a novel statistical manifold modeling approach that is capable of classifying poses of object categories from video sequences by simultaneously minimizing the intra-class variability and maximizing inter-pose distance. Following the intuition that an object part based representation and a suitable part selection process may help achieve our purpose, we formulate the part selection problem from a statistical manifold modeling perspective and treat part selection as adjusting the manifold of the object (parameterized by pose) by means of the manifold “alignment” and “expansion” operations. We show that manifold alignment and expansion are equivalent to minimizing the intra-class distance given a pose while increasing the inter-pose distance given an object instance respectively. We formulate and solve this (otherwise intractable) part selection problem as a combinatorial optimization problem using graph analysis techniques. Quantitative and qualitative experimental analysis validates our theoretical claims.

Informative image representations are important in achieving state-of-the-art performance in object recognition tasks. Among feature learning algorithms that are used to develop image representations, restricted Boltzmann machines (RBMs) have good expressive power and build effective representations. However, the difficulty of training RBMs has been a barrier to their wide use. To address this difficulty, we show the connections between mixture models and RBMs and present an efficient training method for RBMs that utilize these connections. To the best of our knowledge, this is the first work showing that RBMs can be trained with almost no hyperparameter tuning to provide classification performance similar to or significantly better than mixture models (e.g., Gaussian mixture models). Along with this efficient training, we evaluate the importance of convolutional training that can capture a larger spatial context with less redundancy, as compared to non-convolutional training. Overall, our method achieves state-of-the-art performance on both Caltech 101 / 256 datasets using a single type of feature.

We analyze a k-nearest neighbor (k-NN) class of plug-in estimators for estimating Shannon entropy and Rényi entropy. Based on the statistical properties of k-NN balls, we derive explicit rates for the bias and variance of these plug-in estimators in terms of the sample size, the dimension of the samples and the underlying probability distribution. In addition, we establish a central limit theorem for the plug-in estimator that allows us to specify confidence intervals on the entropy functionals. As an application, we use our theory in anomaly detection problems to specify thresholds for achieving desired false alarm rates.

Learning minimum volume sets of an underlying nominal distribution is a very effective approach to anomaly detection. Several approaches to learning minimum volume sets have been proposed in the literature, including the K-point nearest neighbor graph (K-kNNG) algorithm based on the geometric entropy minimization (GEM) principle [4]. The K-kNNG detector, while possessing several desirable characteristics, suffers from high computation complexity, and in [4] a simpler heuristic approximation, the leave-one-out kNNG (L1O-kNNG) was proposed. In this paper, we propose a novel bipartite k-nearest neighbor graph (BP-kNNG) anomaly detection scheme for estimating minimum volume sets. Our bipartite estimator retains all the desirable theoretical properties of the K-kNNG, while being computationally simpler than the K-kNNG and the surrogate L1O-kNNG detectors. We show that BP-kNNG is asymptotically consistent in recovering the p-value of each test point. Experimental results are given that illustrate the superior performance of BP-kNNG as compared to the L1O-kNNG and other state of the art anomaly detection schemes.

The scalar shrinkage-thresholding operator is a key ingredient in variable selection algorithms arising in wavelet denoising, JPEG2000 image compression and predictive analysis of gene microarray data. In these applications, the decision to select a scalar variable is given as the solution to a scalar sparsity penalized quadratic optimization. In some other applications, one seeks to select multidimensional variables. In this work, we present a natural multidimensional extension of the scalar shrinkage thresholding operator. Similarly to the scalar case, the threshold is determined by the minimization of a convex quadratic form plus an Euclidean norm penalty, however, here the optimization is performed over a domain of dimensionN≥ 1. The solution to this convex optimization problem is called the multidimensional shrinkage threshold operator (MSTO). The MSTO reduces to the scalar case in the special case ofN=1. In the general case ofN>; 1 the optimal MSTO shrinkage can be found through a simple convex line search. We give an efficient algorithm for solving this line search and show that our method to evaluate the MSTO outperforms other state-of-the art optimization approaches. We present several illustrative applications of the MSTO in the context of Group LASSO penalized estimation.

We investigate the impact of using non-ideal lowpass filters in the modulated wideband (MWC) converter, which is a recent sub-Nyquist sampling system for sparse wideband analog signals. We begin by deriving a perfect reconstruction condition for general lowpass filters, which coincides with the well-known Nyquist inter-symbol interference (ISI) criterion in communication theory. Then, we propose to compensate for the non-ideal lowpass filters using a digital FIR correction scheme. The proposed solution is validated by experimental results.

This works considers the problem of energy constrained adaptive search for sparse targets given probabilistic prior knowledge of target locations. An Adaptive Resource Allocation Policy (ARAP) was introduced by Bashan (2008), showing significant gains over standard methods can be achieved without prior knowledge on the targets' locations. This work extends ARAP to account for nonuniform prior knowledge. It is shown that potential gains exist as compared to ARAP. Moreover, we show that by overestimating the true region of interest, the proposed search policy can always outperform ARAP in terms of worst-case gain. Lastly, results from an application involving estimating the approach of airplanes at an airport suggest that bi-level piecewise uniform priors are adequate approximations.

We develop an approach to intrinsic dimension estimation based on k-nearest neighbor (kNN) distances. The dimension estimator is derived using a general theory on functionals of kNN density estimates. This enables us to predict the performance of the dimension estimation algorithm. In addition, it allows for optimization of free parameters in the algorithm. We validate our theory through simulations and compare our estimator to previous kNN based dimensionality estimation approaches.

Many practical applications of clustering involve data collected over time. In these applications, evolutionary clustering can be applied to the data to track changes in clusters with time. In this paper, we consider an evolutionary version of spectral clustering that applies a forgetting factor to past affinities between data points and aggregates them with current affinities. We propose to use an adaptive forgetting factor and provide a method to automatically choose this forgetting factor at each time step. We evaluate the performance of the proposed method through experiments on synthetic and real data and find that, with an adaptive forgetting factor, we are able to obtain improved clustering performance compared to a fixed forgetting factor.

This paper is concerned with joint Bayesian endmember extraction and linear unmixing of hyperspectral images using a spatial prior on the abundance vectors. We hypothesize that hyperspectral images are composed of two types of regions. For the first type, the material proportions of adjacent pixels are similar and can be jointly characterized by a single vector, and in the second, neighboring pixels have very different abundances and are characterized by unique mixing proportions. Using this hypothesis we propose a new unmixing algorithm which simultaneously segments the image into such regions and performs unmixing. The experimental results show that the new algorithm can lead to improved MSE of both the extracted endmembers and the estimated abundances in low SNR cases.

BACKGROUND: Nonparametric Bayesian techniques have been developed recently to extend the sophistication of factor models, allowing one to infer the number of appropriate factors from the observed data. We consider such techniques for sparse factor analysis, with application to gene-expression data from three virus challenge studies. Particular attention is placed on employing the Beta Process (BP), the Indian Buffet Process (IBP), and related sparseness-promoting techniques to infer a proper number of factors. The posterior density function on the model parameters is computed using Gibbs sampling and variational Bayesian (VB) analysis. RESULTS: Time-evolving gene-expression data are considered for respiratory syncytial virus (RSV), Rhino virus, and influenza, using blood samples from healthy human subjects. These data were acquired in three challenge studies, each executed after receiving institutional review board (IRB) approval from Duke University. Comparisons are made between several alternative means of per-forming nonparametric factor analysis on these data, with comparisons as well to sparse-PCA and Penalized Matrix Decomposition (PMD), closely related non-Bayesian approaches. CONCLUSIONS: Applying the Beta Process to the factor scores, or to the singular values of a pseudo-SVD construction, the proposed algorithms infer the number of factors in gene-expression data. For real data the "true" number of factors is unknown; in our simulations we consider a range of noise variances, and the proposed Bayesian models inferred the number of factors accurately relative to other methods in the literature, such as sparse-PCA and PMD. We have also identified a "pan-viral" factor of importance for each of the three viruses considered in this study. We have identified a set of genes associated with this pan-viral factor, of interest for early detection of such viruses based upon the host response, as quantified via gene-expression data.

We address the problem of recognizing the pose of an object category from video sequences capturing the object under small camera movements. This scenario is relevant in applications such as robotic object manipulation or autonomous navigation. We introduce a new algorithm where we model an object category as a collection of non parametric probability densities capturing appearance and geometrical variability within a small area of the viewing sphere for different object instances. By regarding the set of frames of the video as realizations of such probability densities, we cast the problem of object pose classification as the one of matching (i.e., comparing information divergence of) probably density functions in testing and training. Our work can be also related to statistical manifold learning. By performing dimensionality reduction on the manifold of learned PDFs, we show that the embedding in the 3D Euclidean space yield meaningful trajectories which can be parameterized by the pose coordinates on the viewing sphere, this enables an unsupervised learning procedure for pose classification. Our experimental results on both synthesized and real world data show promising results toward the goal of accurate and efficient pose classification of object categories from video sequences.

Due to the curse of dimensionality, high-dimensional data is often pre-processed with some form of dimensionality reduction for the classification task. Many common methods of supervised dimensionality reduction have focused on separating and collapsing the data near the class centroids. These methods often make assumptions on the distributions of the data classes - namely Gaussianity - which can lead to ad-hoc and sub-optimal implementation. In this paper we present a method of supervised dimensionality reduction which takes an information-geometric approach by maximizing the between class information distances. This is shown to have direct relation to the Chernoff and Bhattacharya performance bounds for classification error. We illustrate our methods on real data and compare to several existing methods.

We propose a new approach to adaptive system identification when the system model is sparse. The approach applies ℓ1relaxation, common in compressive sensing, to improve the performance of LMS-type adaptive methods. This results in two new algorithms, the zero-attracting LMS (ZA-LMS) and the reweighted zero-attracting LMS (RZA-LMS). The ZA-LMS is derived via combining a ℓ1norm penalty on the coefficients into the quadratic LMS cost function, which generates a zero attractor in the LMS iteration. The zero attractor promotes sparsity in taps during the filtering process, and therefore accelerates convergence when identifying sparse systems. We prove that the ZA-LMS can achieve lower mean square error than the standard LMS. To further improve the filtering performance, the RZA-LMS is developed using a reweighted zero attractor. The performance of the RZA-LMS is superior to that of the ZA-LMS numerically. Experiments demonstrate the advantages of the proposed filters in both convergence rate and steady-state behavior under sparsity assumptions on the true coefficient vector. The RZA-LMS is also shown to be robust when the number of non-zero taps increases.

We address covariance estimation under mean-squared loss in the Gaussian setting. Specifically, we consider shrinkage methods which are suitable for high dimensional problems with small number of samples (large p small n). First, we improve on the Ledoit-Wolf (LW) method by conditioning on a sufficient statistic via the Rao-Blackwell theorem, obtaining a new estimator RBLW whose mean-squared error dominates the LW under Gaussian model. Second, to further reduce the estimation error, we propose an iterative approach which approximates the clairvoyant shrinkage estimator. Convergence of this iterative method is proven and a closed form expression for the limit is determined, which is called the OAS estimator. Both of the proposed estimators have simple expressions and are easy to compute. Although the two methods are developed from different approaches, their structure is identical up to specific constants. The RBLW estimator provably dominates the LW method; and numerical simulations demonstrate that the OAS estimator performs even better, especially when n is much less than p.

In this paper, we propose a Bayesian model and a Monte Carlo Markov chain (MCMC) algorithm for reconstructing images that consist of only few non-zero pixels. An appropriate distribution that promotes sparsity is proposed as prior distribution for the pixel values. The hyperparameters involved in the modeling are also assigned prior distributions, resulting in a hierarchical model. A Gibbs sampler allows us to draw samples distributed according the full posterior of interest. These samples are then used to approximate standard maximum a posteriori (MAP) estimator. By conducting some simulations, we show that the proposed estimator clearly outperforms previous estimators proposed in the literature.

We consider principal component analysis (PCA) in decomposable Gaussian graphical models. We exploit the prior information in these models in order to distribute its computation. For this purpose, we reformulate the problem in the sparse inverse covariance (concentration) domain and solve the global eigenvalue problem using a sequence of local eigenvalue problems in each of the cliques of the decomposable graph. We demonstrate the application of our methodology in the context of decentralized anomaly detection in the Abilene backbone network. Based on the topology of the network, we propose an approximate statistical graphical model and distribute the computation of PCA.

To date, most studies on spam have focused only on the spamming phase of the spam cycle and have ignored the harvesting phase, which consists of the mass acquisition of email addresses. It has been observed that spammers conceal their identity to a lesser degree in the harvesting phase, so it may be possible to gain new insights into spammers' behavior by studying the behavior of harvesters, which are individuals or bots that collect email addresses. In this paper, we reveal social networks of spammers by identifying communities of harvesters with high behavioral similarity using spectral clustering. The data analyzed was collected through project honey pot, a distributed system for monitoring harvesting and spamming. Our main findings are (1) that most spammers either send only phishing emails or no phishing emails at all, (2) that most communities of spammers also send only phishing emails or no phishing emails at all, and (3) that several groups of spammers within communities exhibit coherent temporal behavior and have similar IP addresses. Our findings reveal some previously unknown behavior of spammers and suggest that there is indeed social structure between spammers to be discovered.

We consider the problems of clustering, classification, and visualization of high-dimensional data when no straightforward euclidean representation exists. In this paper, we propose using the properties of information geometry and statistical manifolds in order to define similarities between data sets using the Fisher information distance. We will show that this metric can be approximated using entirely nonparametric methods, as the parameterization and geometry of the manifold is generally unknown. Furthermore, by using multidimensional scaling methods, we are able to reconstruct the statistical manifold in a low-dimensional euclidean space; enabling effective learning on the data. As a whole, we refer to our framework as Fisher Information Nonparametric Embedding (FINE) and illustrate its uses on practical problems, including a biomedical application and document classification.

This paper presents a hierarchical Bayesian model to reconstruct sparse images when the observations are obtained from linear transformations and corrupted by an additive white Gaussian noise. Our hierarchical Bayes model is well suited to such naturally sparse image applications as it seamlessly accounts for properties such as sparsity and positivity of the image via appropriate Bayes priors. We propose a prior that is based on a weighted mixture of a positive exponential distribution and a mass at zero. The prior has hyperparameters that are tuned automatically by marginalization over the hierarchical Bayesian model. To overcome the complexity of the posterior distribution, a Gibbs sampling strategy is proposed. The Gibbs samples can be used to estimate the image to be recovered, e.g., by maximizing the estimated posterior distribution. In our fully Bayesian approach, the posteriors of all the parameters are available. Thus, our algorithm provides more information than other previously proposed sparse reconstruction methods that only give a point estimate. The performance of the proposed hierarchical Bayesian sparse reconstruction method is illustrated on synthetic data and real data collected from a tobacco virus sample using a prototype MRFM instrument.

The application that motivates this paper is molecular imaging at the atomic level. When discretized at subatomic distances, the volume is inherently sparse. Noiseless measurements from an imaging technology can be modeled by convolution of the image with the system point spread function (psf). Such is the case with magnetic resonance force microscopy (MRFM), an emerging technology where imaging of an individual tobacco mosaic virus was recently demonstrated with nanometer resolution. We also consider additive white Gaussian noise (AWGN) in the measurements. Many prior works of sparse estimators have focused on the case when H has low coherence; however, the system matrix H in our application is the convolution matrix for the system psf. A typical convolution matrix has high coherence. This paper, therefore, does not assume a low coherence H. A discrete-continuous form of the Laplacian and atom at zero (LAZE) p.d.f. used by Johnstone and Silverman is formulated, and two sparse estimators derived by maximizing the joint p.d.f. of the observation and image conditioned on the hyperparameters. A thresholding rule that generalizes the hard and soft thresholding rule appears in the course of the derivation. This so-called hybrid thresholding rule, when used in the iterative thresholding framework, gives rise to the hybrid estimator, a generalization of the lasso. Estimates of the hyperparameters for the lasso and hybrid estimator are obtained via Stein's unbiased risk estimate (SURE). A numerical study with a Gaussian psf and two sparse images shows that the hybrid estimator outperforms the lasso.

Local intrinsic dimension estimation has been shown to be useful for many tasks such as image segmentation, anomaly detection, and de-biasing global dimension estimates. Of particular concern with local dimension estimation algorithms is the high variance for high dimensions, leading to points which lie on the same manifold estimating at different dimensions. We propose adding adaptive 'neighborhood smoothing' - filtering over the generated dimension estimates to obtain the most probable estimate for each sample - as a method to reduce variance and increase algorithm accuracy. We present a method for defining neighborhoods using a geodesic distance, which constricts each neighborhood to the manifold of concern, and prevents smoothing over intersecting manifolds of differing dimension. Finally, we illustrate the benefits of neighborhood smoothing on synthetic data sets as well as towards diagnosing anomalies in router networks.

The problem of document classification considers categorizing or grouping of various document types. Each document can be represented as a bag of words, which has no straightforward Euclidean representation. Relative word counts form the basis for similarity metrics among documents. Endowing the vector of term frequencies with a Euclidean metric has no obvious straightforward justification. A more appropriate assumption commonly used is that the data lies on a statistical manifold, or a manifold of probabilistic generative models. In this paper, we propose calculating a low-dimensional, information based embedding of documents into Euclidean space. One component of our approach motivated by information geometry is the Fisher information distance to define similarities between documents. The other component is the calculation of the Fisher metric over a lower dimensional statistical manifold estimated in a nonparametric fashion from the data. We demonstrate that in the classification task, this information driven embedding outperforms both a standard PCA embedding and other Euclidean embeddings of the term frequency vector.

This paper addresses the problem of unmixing hyperspectral images contamined by additive colored noise. Each pixel of the image is modeled as a linear combination of pure materials (denoted as end-members) corrupted by an additive zero mean Gaussian noise sequence with unknown covariance matrix. Appropriate priors are defined ensuring positivity and additivity constraints on the mixture coefficients (denoted as abundances). These coefficients as well as the noise covariance matrix are then estimated from their joint posterior distribution. A Gibbs sampling strategy generates abundances and noise covariance matrices distributed according to the joint posterior. These samples are then averaged for minimum mean square error estimation.

This paper considers the image reconstruction problem when the original image is assumed to be sparse and when limited information of the point spread function (PSF) is available. In particular, we are interested in reconstructing the magnetization density given magnetic resonance force microscopy (MRFM) image data, and an alternating iterative algorithm is presented to solve this problem. Simulations demonstrate its performance not only in the reconstruction of the original image, but also in the recovery of the partially known PSF. In addition, we suggest the introduction of a smoothing penalty on allowable PSFs to improve the reconstruction.

We consider the problem of emitter tracking using received signal strengths (RSS) measured at a number of in-range access points (AP) when some of the AP locations are unknown. This can be formulated as a Euclidean distance matrix completion problem (EDMCP) to which an iterative distributed weighted multidimensional scaling (dwMDS) algorithm can be applied to simultaneously track emitters and localize APs. The algorithm is illustrated using real-time data collected by the University of California San Diego (UCSD) wireless topology discovery (WTD) project.

We propose a manifold learning approach to fiber tract clustering using a novel similarity measure between fiber tracts constructed from dual-rooted graphs. In particular, to generate this similarity measure, the chamfer or Hausdorff distance is initially employed as a local distance metric to construct minimum spanning trees between pairwise fiber tracts. These minimum spanning trees are effective in capturing the intrinsic geometry of the fiber tracts. Hence, they are used to capture the neighborhood structures of the fiber tract data set. We next assume the high-dimensional input fiber tracts to lie on low-dimensional non-linear manifolds. We apply Locally Linear Embedding, a popular manifold learning technique, to define a low-dimensional embedding of the fiber tracts that preserves the neighborhood structures of the high-dimensional data structure as captured by the method of dual-rooted graphs. Clustering is then performed on this low-dimensional data structure using the k-means algorithm. We illustrate our resulting clustering technique on both synthetic data and on real fiber tract data obtained from diffusion tensor imaging.

Summary form only given. Despite significant recent progress in automatic target exploitation (ATE) and recognition (ATR), current ATE systems do not meet the requirements of modern battlefield environments. Next generation ATE systems must actively manage sensor resources, aggregate sensed information across multiple platforms and diverse signaling modalities, and adapt to increasingly agile adversaries and operating conditions. Thus, the fundamental research challenge is to develop an integrated systems theory that jointly treats information fusion, control, and adaptation using multiple, dynamic multimodal sensor platforms in resource constrained environments.

This paper addresses the problem of sensor management for a large network of agile sensors. Sensor management refers to the process of dynamically retasking agile sensors in response to an evolving environment. Sensors may be agile in a variety of ways, e.g., the ability to reposition, point an antenna, choose sensing mode, or waveform. The goal of sensor management in a large network is to choose actions for individual sensors dynamically so as to maximize overall network utility. Sensor management in the multiplatform setting is a challenging problem for several reasons. First, the state space required to characterize an environment is typically of very high dimension and poorly represented by a parametric form. Second, the network must simultaneously address a number of competing goals. Third, the number of potential taskings grows exponentially with the number of sensors. Finally, in low communication environments, decentralized methods are required. The approach we present addresses these challenges through a novel combination of particle filtering for nonparametric density estimation, information theory for comparing actions, and physicomimetics for computational tractability. The efficacy of the method is illustrated in a realistic surveillance application by simulation, where an unknown number of ground targets are to be detected and tracked by a network of mobile sensors.

The context of this paper is adaptive waveform design for estimating parameters of an unknown channel under average energy constraints. This paper focuses on the simpler problem of adaptive waveform-amplitude design for which we obtain interesting analytical results. We treat an TV-step design problem where a fixed waveform can be transmitted into the channel N times with amplitudes that can be chosen as a function of past channel outputs. For N = 2 and a linear Gaussian channel model, we derive the optimal amplitude to transmit at the second step as a function of the first measurement. This adaptive 2-step energy allocation strategy yields a mean-squared error (MSE) improvement of at least 1.7 dB relative to the optimal non-adaptive strategy. Motivated by the optimal two-step strategy we propose a suboptimal adaptive TV-step strategy that can achieve an MSE improvement of more than 5 dB for N = 50. Applications of our results to MIMO and inverse scattering channel models are discussed.

This paper addresses the problem of sensor management for a large network of agile sensors. Sensor management, as defined here, is the process of dynamically retasking agile sensors in response to an evolving environment. Sensors may be agile in a variety of ways, e.g., the ability to reposition, point an antenna, choose sensing mode, or waveform. The goal of sensor management in a large network is to choose actions for individual sensors dynamically so as to maximize overall network utility. Sensor management in the multiplatform setting is a challenging problem for several reasons. First, the state space required to characterize an environment is typically of very high dimension and poorly represented by a parametric form. Second, the network must simultaneously address a number of competing goals. Third, the number of potential taskings grows exponentially with the number of sensors. Finally, in low-communication environments, decentralized methods are required. The approach we present in this paper addresses these challenges through a novel combination of particle filtering for nonparametric density estimation, information theory for comparing actions, and physicomimetics for computational tractability. The efficacy of the method is illustrated in a realistic surveillance application by simulation, where an unknown number of ground targets are detected and tracked by a network of mobile sensors.

Given the location of a relative maximum of the log-likelihood function, how to assess whether it is the global maximum? This paper investigates an existing statistical tool, which, based on asymptotic analysis, answers this question by posing it as a hypothesis testing problem. A general framework for constructing tests for global maximum is given. The characteristics of the tests are investigated for two cases: correctly specified model and model mismatch. A finite sample approximation to the power is given, which gives a tool for performance prediction and a measure for comparison between tests. The sensitivity of the tests to model mismatch is analyzed in terms of the Renyi divergence and the Kullback-Leibler divergence between the true underlying distribution and the assumed parametric class and tests that are insensitive to small deviations from the model are derived thereby overcoming a fundamental weakness of existing tests. The tests are illustrated for three applications: passive localization or direction finding using an array of sensors, estimating the parameters of a Gaussian mixture model, and estimation of superimposed exponentials in noise-problems that are known to suffer from local maxima.

We determine the optimum training strategy for a multiple-antenna wireless link in a Rician fading channel using a training based lower bound on capacity. We consider the standard Rician block fading channel where the channel coefficients are modeled as independent circular Gaussian random variables with non-zero means (the specular component). The specular component is known to both the transmitter and receiver. The channel coefficients of this model are constant over a block of T symbol periods but, independent over different blocks. For such a model, it is shown that the training based capacity, the optimum training signals, the training period, transmit and training energy are dependent on the Rician factor tau along with SNR rho, the number of transmit antennas M, the number of receive antennas N and the coherence interval T. Also, unlike in the case of Rayleigh fading channels, it can be shown using the lower bound for Rician fading channels that for low SNR Rician fading channels behave like a purely AWGN channel and the optimum strategy is to spend no effort in learning the channel. When SNR is not low and training is required then the optimum training period is as many symbol intervals as there are transmit antennas

We introduce a new similarity measure between data points suited for clustering and classification on smooth manifolds. The proposed measure is constructed from a dual rooted graph diffusion over the feature vector space, obtained by growing dual rooted minimum spanning trees (MST) between data points. This diffusion model for pairwise affinities naturally accommodates the case where the feature distribution is supported on a lower dimensional manifold. When this affinity measure is combined with labeled data, a semi-supervised classifier can be defined that handles both labeled and unlabeled data in a seamless manner. We will illustrate our method for both simulated ground truth and real partially labeled data sets.

In this paper, we evaluate the contribution of the classification constrained dimensionality reduction (CCDR) algorithm to the performance of several classifiers. We present an extension to previously introduced CCDR algorithm to multiple hypotheses. We investigate classification performance using the CCDR algorithm on hyperspectral satellite imagery data. We demonstrate the performance gain for both local and global classifiers and demonstrate a 10% improvement of the k-nearest neighbors algorithm performance. We present a connection between intrinsic dimension estimation and the optimal embedding dimension obtained using the CCDR algorithm

We consider the problem of optimal waveform selection. We would like to choose a small subset from a given set of waveforms that minimizes state prediction mean squared error (MSE) given the past observations. This differs from previous approaches to this problem since the optimal waveforms cannot be computed offline; it requires the previous observations. Since the optimal solution to this subset selection problem is combinatorially complex, we propose a convex relaxation of the problem and provide a low complexity suboptimal solution. We present a specific model and show that the performance of this suboptimal procedure approaches that of the optimal waveforms

The systematic inference of biologically relevant influence networks remains a challenging problem in computational biology. Even though the availability of high-throughput data has enabled us to use probabilistic models to infer the plausible structure of such networks, their true interpretation of the biology of the process is questionable. In this work, we propose a probabilistic network inference methodology, based on the Directed information criterion, which incorporates the biology of transcription within the framework, so as to enable experimentally verifiable inference. We use a publicly available embryonic kidney microarray dataset to demonstrate our results on the regulation of the Gata2/Gata3 genes.

This paper considers the detection of a Markov signal in additive white Gaussian noise (AWGN). Here, the Markov signal is taken to be a certain class of random walk processes. A closed form expression of the likelihood ratio (LR) is derived for a general Markov signal in AWGN. Then, under the conditions of low signal to noise ratio (SNR) and long observation time, necessary conditions are derived for the LR of the random walk to be approximated by a bank of filtered energy (FE) detectors, as well as by a single FE detector. The FE detector is an intuitive way to perform detection; however, it is not necessarily optimal. The results are applicable to the detection of an electron spin in a magnetic resonance force microscopy (MRFM) experiment

See through the wall (STTW) applications have become of high importance to law enforcement, homeland security and defense needs. In this work surface penetrating radar is simulated using basic physical principles of radar propagation. Wavenumber migration is employed to form 2D images of objects found behind a wall. It is shown that this technique cannot properly image with the wall present because of an unknown phase delay experienced by the electromagnetic waves as they pass through the wall. Two approaches are taken to estimate this phase by looking at the direct backscatter signal from the wall. The first is a dual phase approach, which uses a non-parametric technique to find the phase at every frequency. The second method is a dual frequency approach. The two frequencies are close enough together that the reflection coefficients are approximately equal. This approximation allows for more observations than unknown parameters. The surface reflection coefficient, back wall coefficient, and phase are simultaneously determined using an iterative, non-linear (Newton-Raphson) successive approximation algorithm. Comparisons are performed for a simple scenario of three point scatterers with and without phase correction.

In this paper, we consider the problem of image reconstruction from the noisy blurred version of an original image when the blurring operator is partially known and the original image is sparse. Using optimization transfer, we derive a novel iterative algorithm in closed-form that incorporates both sparseness and partial knowledge of the image. We demonstrate the performance of the algorithm using simulations.

Sparse image reconstruction is of interest in the fields of radioastronomy and molecular imaging. The observation is assumed to be a linear transformation of the image, and corrupted by additive white Gaussian noise. We study the usage of sparse priors in the empirical Bayes framework: it permits the selection of the hyperparameters of the prior in a data-driven fashion. Three sparse image reconstruction methods are proposed. A simulation study was performed using a binary-valued image and a Gaussian point spread function. In the range of signal to noise ratios considered, the proposed methods had better performance than sparse Bayesian learning (SBL).

In this paper, we provide a detailed geometric characterization of multivariate distributions that maximize Renyi entropy under covariance constraint. These distributions are shown to be marginals of the uniform distribution on the hypersphere for q > 1, and conditional distributions of projections of this uniform distribution in the case q > 1. This construction allows to build a natural convolution of random type for which these distributions are stable

We introduce a novel adaptive non-parametric anomaly detection approach, called GEM, that is based on the minimal covering properties of K-point entropic graphs when constructed on N training samples from a nominal probability distribution. Such graphs have the property that as N their span recovers the entropy minimizing set that supports at least = K/N (100)% of the mass of the Lebesgue part of the distribution. When a test sample falls outside of the entropy minimizing set an anomaly can be declared at a statistical level of significance = 1 - . A method for implementing this non-parametric anomaly detector is proposed that approximates this minimum entropy set by the influence region of a K-point entropic graph built on the training data. By implementing an incremental leave-one-out k-nearest neighbor graph on resampled subsets of the training data GEM can efficiently detect outliers at a given level of significance and compute their empirical p-values. We illustrate GEM for several simulated and real data sets in high dimensional feature spaces.

Distributed estimation of sensor location is a key enabling technology for sensor networks. This demonstration will provide an interactive display of distributed, cooperative localization, using wideband received signal-strength measurements, and the distributed weighted multi-dimensional scaling (dwMDS) algorithm.

A binary linear programming formulation of the graph edit distance for unweighted, undirected graphs with vertex attributes is derived and applied to a graph recognition problem. A general formulation for editing graphs is used to derive a graph edit distance that is proven to be a metric, provided the cost function for individual edit operations is a metric. Then, a binary linear program is developed for computing this graph edit distance, and polynomial time methods for determining upper and lower bounds on the solution of the binary program are derived by applying solution methods for standard linear programming and the assignment problem. A recognition problem of comparing a sample input graph to a database of known prototype graphs in the context of a chemical information system is presented as an application of the new method. The costs associated with various edit operations are chosen by using a minimum normalized variance criterion applied to pairwise distances between nearest neighbors in the database of prototypes. The new metric is shown to perform quite well in comparison to existing metrics when applied to a database of chemical graphs.

We consider the problem of estimating the endpoints (source and destination) of a transmission in a network based on partial measurement of the transmission path. Possibly asynchronous sensors placed at various points within the network provide the basis for endpoint estimation by indicating that a specific transmission has been intercepted at their assigned locations. During a training phase, test transmissions are made between various pairs of endpoints in the network and the sensors they activate are noted. Sensor activations corresponding to transmissions with unknown endpoints are also observed in a monitoring phase. A semidefinite programming relaxation is used in conjunction with the measurements and linear prior information to produce likely sample topologies given the data. These samples are used to generate Monte Carlo approximations of the posterior distributions of source/destination pairs for measurements obtained in the monitoring phase. The posteriors allow for maximum a posteriori (MAP) estimation of the endpoints along with computation of some resolution measures. We illustrate the method using simulations of random topologies

No convergent ordered subsets (OS) type image reconstruction algorithms for transmission tomography have been proposed to date. In contrast, in emission tomography, there are two known families of convergent OS algorithms: methods that use relaxation parameters, and methods based on the incremental expectation-maximization (EM) approach. This paper generalizes the incremental EM approach by introducing a general framework, "incremental optimization transfer." The proposed algorithms accelerate convergence speeds and ensure global convergence without requiring relaxation parameters. The general optimization transfer framework allows the use of a very broad family of surrogate functions, enabling the development of new algorithms. This paper provides the first convergent OS-type algorithm for (nonconcave) penalized-likelihood (PL) transmission image reconstruction by using separable paraboloidal surrogates (SPS) which yield closed-form maximization steps. We found it is very effective to achieve fast convergence rates by starting with an OS algorithm with a large number of subsets and switching to the new "transmission incremental optimization transfer (TRIOT)" algorithm. Results show that TRIOT is faster in increasing the PL objective than nonincremental ordinary SPS and even OS-SPS yet is convergent.

Accurate, distributed localization algorithms are needed for a wide variety of wireless sensor network applications. This article introduces a scalable, distributed weighted-multidimensional scaling (dwMDS) algorithm that adaptively emphasizes the most accurate range measurements and naturally accounts for communication constraints within the sensor network. Each node adaptively chooses a neighborhood of sensors, updates its position estimate by minimizing a local cost function and then passes this update to neighboring sensors. Derived bounds on communication requirements provide insight on the energy efficiency of the proposed distributed method versus a centralized approach. For received signal-strength (RSS) based range measurements, we demonstrate via simulation that location estimates are nearly unbiased with variance close to the Cramér-Rao lower bound. Further, RSS and time-of-arrival (TOA) channel measurements are used to demonstrate performance as good as the centralized maximum-likelihood estimator (MLE) in a real-world sensor network.

Given a relative maximum of the log-likelihood function, how to assess whether it is the global maximum? This paper investigates a statistical tool, which answers this question by posing it as a hypothesis testing problem. A general framework for constructing tests for the global maximum is given. The characteristics of the tests are investigated for two cases: correctly specified model and model mismatch. A finite sample approximation to the power is given, which gives a tool for performance prediction and a measure for comparison between tests. The tests are illustrated for two applications: estimating the parameters of a Gaussian mixture model and direction finding using an array of sensors - practical problems that are known to suffer from local maxima.

In this paper, we propose a nonlinear dimensionality reduction method aimed at extracting lower-dimensional features relevant for classification tasks. This is obtained by modifying the Laplacian approach to manifold learning through the introduction of class dependent constraints. Using synthetic data sets, we show that the proposed algorithm can greatly improve both supervised and semi-supervised learning problems.

Accurate, distributed localization algorithms are needed for a wide variety of wireless sensor network applications. This paper introduces a scalable, distributed weighted-multidimensional scaling (dwMDS) algorithm that adaptively emphasizes the most accurate range measurements available and naturally accounts for communication constraints within the sensor network. For received signal-strength (RSS) based range measurements, we demonstrate via simulation that location estimates are nearly unbiased with variance close to the Cramer-Rao lower bound (CRB). Further, RSS and time-of-arrival (TOA) channel measurements are used to demonstrate performance as good as the centralized maximum-likelihood estimator (MLE) in a real-world sensor network.

This paper highlights some fundamental issues involved in the study of large-scale dynamical systems. Two particular topics are discussed in some detail, one dealing with the management of active sensors via partially observable Markov decision processes, and the other dealing with the modeling, recognition and tracking of multi-function radars in an electronic warfare environment.

This paper addresses the problem of locating an acoustic source using a sensor network in a distributed manner, i.e., without transmitting the full data set to a central point for processing. This problem has been traditionally addressed through the nonlinear least squares or maximum likelihood framework. These methods, even though asymptotically optimal under certain conditions, pose a difficult global optimization problem. It is shown that the associated objective function may have multiple local optima and saddle points and hence any local search method might stagnate at a sub-optimal solution. In this paper, we formulate the problem as a convex feasibility problem and apply a distributed version of the projection onto convex sets (POCS) method. We give a closed form expression for the projection phase, which usually constitutes the heaviest computational aspect of POCS. Conditions are given under which, when the number of samples increases to infinity or in the absence of measurement noise, the convex feasibility problem has a unique solution at the true source location. In general, the method converges to a limit point or a limit cycle in the neighborhood of the true location. Simulation results show convergence to the global optimum with extremely fast convergence rates compared to the previous methods.

The paper addresses the problem of sensor scheduling for simultaneous target detection, tracking and identification. We consider sensors with agility in waveform and pointing direction. Scheduling decisions are made using an information based approach, where the merit of competing actions is judged by the information expected to be gained when taking the action. We focus on non-myopic scheduling, where the long-term ramifications of scheduling decisions are accounted for in decision making. Since an exact non-myopic solution is computationally prohibitive, we investigate two approximate approaches: direct approximation of Bellman's equation; reinforcement learning. We show, via simulation, that both techniques provide substantial gains over myopic scheduling.

We consider the problem of imaging a medium using an array of sensors. More specifically, we are interested in optimally designing a sequence of experiments for probing a medium in order to form an image of the scatterers present in the medium. We consider the case where the received signal is corrupted by noise. We derive an expression for the mean square error for estimating the scatter coefficients and find the optimal sequence scheme that minimizes this error. Using the expression for the minimum mean square error, we show that we can do better than any beamforming approach to imaging. In the process, we also find the optimal energy allocation between the sequence of experiments. Closed-form expressions for the optimal transmission scheme and the minimum mean square error are provided.

Many biological functions are executed as a module of coexpressed genes which can be conveniently viewed as a coexpression network. Genes are network vertices and significant pairwise coexpression are network edges. Traditional network discovery methods control either statistical significance or biological significance, but not both. We have designed and implemented a two-stage algorithm that controls both the statistical significance (false discovery rate, FDR) and the biological significance (minimum acceptable strength, MAS) of the discovered network. Based on the estimation of pairwise gene profile correlation, the algorithm provides an initial network discovery that controls only FDR, which is then followed by a second network discovery which controls both FDR and MAS. We illustrate the algorithm for discovery of coexpression networks for yeast galactose metabolism with controlled FDR and MAS.

Many bioinformatics problems can be tackled from a fresh angle offered by the network perspective. Directly inspired by metabolic network structural studies, we propose an improved gene clustering approach for inferring gene signaling pathways. Based on the construction of co-expression networks that consists of both significantly linear and nonlinear gene associations together with controlled biological and statistical significance, we can make accurate discovery of many transitively coexpressed genes and similarly coexpressed genes. Our approach tends to group functionally related genes into a tight cluster. We illustrate our approach and compare it to the traditional clustering approaches on a retinal gene expression dataset. The clustering method has been implemented in an R package "GeneNT" that is freely available from: http://www-personal.umich.edu//sup /spl sim//zhud/gene nt.htm/.

This paper proposes an algorithm to convert a T -stage stochastic decision problem with a continuous state space to a sequence of supervised learning problems. The optimization problem associated with the trajectory tree and random trajectory methods of Kearns, Mansour, and Ng, 2000, is solved using the Gauss-Seidel method. The algorithm breaks a multistage reinforcement learning problem into a sequence of single-stage reinforcement learning subproblems, each of which is solved via an exact reduction to a weighted-classification problem that can be solved using off-the-self methods. Thus the algorithm converts a reinforcement learning problem into simpler supervised learning subproblems. It is shown that the method converges in a finite number of steps to a solution that cannot be further improved by componentwise optimization. The implication of the proposed algorithm is that a plethora of classification methods can be applied to find policies in the reinforcement learning problem.

UNLABELLED: Many bioinformatics problems can be tackled from a fresh angle offered by the network perspective. Directly inspired by metabolic network structural studies, we propose an improved gene clustering approach for inferring gene signaling pathways from gene microarray data. Based on the construction of co-expression networks that consists of both significantly linear and non-linear gene associations together with controlled biological and statistical significance, our approach tends to group functionally related genes into tight clusters despite their expression dissimilarities. We illustrate our approach and compare it to the traditional clustering approaches on a yeast galactose metabolism dataset and a retinal gene expression dataset. Our approach greatly outperforms the traditional approach in rediscovering the relatively well known galactose metabolism pathway in yeast and in clustering genes of the photoreceptor differentiation pathway. AVAILABILITY: The clustering method has been implemented in an R package "GeneNT" that is freely available from: http://www.cran.org.

The problem of finding the maximum likelihood estimator of a commonly observed model, based on data collected by a sensor network under power and bandwidth constraints, is considered. In particular, a case where the sensors cannot fully share their data is treated. An iterative algorithm that relaxes the requirement of sharing all the data is given. The algorithm is based on a local Fisher scoring method and an iterative information sharing procedure. The case where the sensors share sub-optimal estimates is also analyzed. The asymptotic distribution of the estimates is derived and used to provide a means of discrimination between estimates that are associated with different local maxima of the log-likelihood function. The results are validated by a simulation.

In the manifold learning problem one seeks to discover a smooth low dimensional surface, i.e., a manifold embedded in a higher dimensional linear vector space, based on a set of n measured sample points on the surface. In this paper, we consider the closely related problem of estimating the manifold's intrinsic dimension and the intrinsic entropy of the sample points. Specifically, we view the sample points as realizations of an unknown multivariate density supported on an unknown smooth manifold. In previous work, we introduced a geometric probability method called the geodesic minimal spanning tree (GMST) to obtain asymptotically consistent estimates of manifold dimension and entropy. In this paper, we present a simpler method, based on the k-nearest neighbor (k-NN) graph that does not require estimation of geodesic distances on the manifold. The algorithm is applied to standard synthetic manifolds as well as real data sets consisting of images of faces.

If a dense network of static wireless sensors is deployed to measure a time-varying isotropic random field, then sensor data itself, rather than range measurements using specialized hardware, can be used to estimate a map of sensor locations. Furthermore, distributed and scalable sensor localization algorithms can be derived. We apply the manifold learning algorithms, Isomap, locally linear embedding (LLE), and Hessian LLE (HLLE). The HLLE-based estimator demonstrates the best bias and variance performance, but may not be robust for all random sensor deployments.

We propose a network topology estimation strategy using unicast end-to-end packet pair delay measurements that is based on mixture models for the delay covariances. An unsupervised learning algorithm is applied to estimate the number of mixture components and delay covariances. The leaf pairs are clustered by a MAP criterion and passed to a hierarchical topology construction algorithm to rebuild the tree. Results from an ns simulation show that our algorithm can identify a network tree with 8 leaf nodes.

Many interesting data sets, although high dimensional in nature, can be characterized by a low dimensional non linear parameterization, if, for example, the data set lies on a manifold. In this paper we consider the problem of estimating the manifold's intrinsic dimension and the intrinsic entropy of the data set. Specifically, we view the data as realizations of an unknown multivariate density supported on an unknown smooth manifold. We present a novel geometric approach, based on asymptotic properties of entropic graphs, to obtain asymptotically consistent estimates of the manifold dimension and the Renyi /spl alpha/-entropy of the data density on the manifold. The proposed algorithm simply constructs a minimal spanning tree (MST) sequence using a geodesic distance matrix and uses the overall lengths of the MSTs to compute the desired estimators. We apply the algorithm to standard synthetic manifolds as well as to real data sets.

Calculation of the differential entropy of the limiting density of a sequence of probability density functions (pdf) is an interesting mathematical problem and is important in asymptotic analysis of communication systems. In such cases, it would be of interest to know if the limit of the differential entropies H/sub n/, corresponding to the sequence of pdf f/sub n/, is equal to the differential entropy H, of the limiting pdf f. In this correspondence, we establish sufficient conditions under which H/sub n/ /spl rarr/ H.

In energy-limited wireless sensor networks, detection using 'censoring sensors' reduces the probability that a sensor must transmit, thereby saving energy. We introduce a hierarchical distributed detection scheme designed specifically for multihop networks. If a sensor's local likelihood ratio (LLR) crosses a threshold, it is sent to the next higher level sensor. A simple feedback scheme is also considered. We study the performance of a Gaussian change-of-mean detection system using this hierarchical censoring scheme, with and without feedback. We show that good detection performance can be achieved while significantly reducing sensor transmissions compared to the optimal detection system.

We investigate high-rate quantization for various detection and reconstruction loss criteria. A new distortion measure is introduced which accounts for global loss in best attainable binary hypothesis testing performance. The distortion criterion is related to the area under the receiver-operating-characteristic (ROC) curve. Specifically, motivated by Sanov's theorem, we define a performance curve as the trajectory of the pair of optimal asymptotic Type I and Type II error rates of the most powerful Neyman-Pearson test of the hypotheses. The distortion measure is then defined as the difference between the area-under-the-curve (AUC) of the optimal pre-encoded hypothesis test and the AUC of the optimal post-encoded hypothesis test. As compared to many previously introduced distortion measures for decision making, this distortion measure has the advantage of being independent of any detection thresholds or priors on the hypotheses, which are generally difficult to specify in the code design process. A high-resolution Zador-Gersho type of analysis is applied to characterize the point density and the inertial profile associated with the optimal high-rate vector quantizer. The analysis applies to a restricted class of high-rate quantizers that have bounded cells with vanishing volumes. The optimal point density is used to specify a Lloyd-type algorithm which allocates its finest resolution to regions where the gradient of the pre-encoded likelihood ratio has greatest magnitude.

Network security is important for information protection in open, secure, or covert communications. One such requirement is to achieve high-rate communications between clients, e.g., terminals or sensors, in the network while hiding information about the transmitted symbols, signal activity, or other sensitive data from an unintended receiver, e.g., an eavesdropper. For wireless links, the single-user capacity advantages of deployment of multiple antennas at the transmitter is well known. One of the principal conclusions of this paper is that proper exploitation of space-time diversity at the transmitter can also enhance information security and information-hiding capabilities. In particular, we show that significant gains are achievable when the transmitter and the client receiver are both informed about their channel while the transmitter and eavesdropper receiver are uniformed about their channel. More generally, we compare capacity limits for both informed and uninformed transmitter and informed receiver scenarios subject to low probability of intercept (LPI) and low probability of detection (LPD) constraints. For several general cases, we can characterize the LPI- and LPD-optimal transmitted source distributions and compare them to the standard optimal source distribution satisfying a power constraint. We assume the standard quasi-static flat Rayleigh-fading channel model for the transmitter-receiver pairs. This paper is a step toward answering the fundamental question: what are the qualitative and quantitative differences between the information-carrying capabilities of open space-time channels versus secure space-time channels?

Connexions is a new approach to authoring, teaching, and learning that aims to fully exploit modern information technology. Available free of charge to anyone under open-content and open-source licenses, Connexions offers custom-tailored, current course material, is adaptable to a wide range of learning styles, and encourages students to explore the links among courses and disciplines. In contrast to the traditional process of textbook writing and publishing, Connexions fosters world-wide, cross-institution communities of authors, instructors, and students, who collaboratively and dynamically fashion “modules” from which courses are constructed. We believe the ideas and philosophy embodied by Connexions have the potential to change the very nature of textbook writing and publishing, producing a dynamic, interconnected educational environment that is pedagogically sound, both time and cost efficient, and fun. This paper overviews the philosophy and technology behind Connexions and describes a nascent community developing material for DSP education.

We introduce a robust method for detecting evolutionary trends of gene expression from a temporal sequence of microarray data. In this method we perform gene clustering via multi-objective optimization to reveal genes with interesting and statistically significant temporal patterns. We illustrate this gene filtering methodology in the context of exploring the time trajectories of mouse retinal genes acquired at different points over the lifetimes of a population of mice. For 6 time points sampled over 24 mouse subjects, our method can reliably reveal genes whose expression level increases or decreases monotonically, hits a peak or valley at birth, or exhibits other trends.

We introduce rigorous definitions for two quantities of interest, diversity and degrees of freedom, that are used to quantify the advantages of a multiple antenna multiple-input multiple-output (MIMO) system when compared to a single-input single-output (SISO) system. These definitions are in a general setting which will allow the computation of these quantities for systems other than multiple antenna MIMO systems. We verify the effectiveness of the definitions by computing the quantities of interest for various existing examples.

As telecommunication networks grow larger and more complex, it is important to monitor internal link characteristics for operation, monitoring, and diagnosis purposes. Since router link monitoring is not practical due to high communication overhead, there has been considerable interest in monitoring from edge (end-to-end) observations. This paper focuses on the estimation of internal link delay distributions from edge measurements. Discrete and continuous delay models are introduced and we propose a new mixed finite mixture model for link delay probability density functions (p.d.f.). When collecting end-to-end unicast packet delays from edge nodes, we are able to estimate internal link delay distributions using the EM algorithm. Simulation results are given to illustrate our method.

Accounting for uncertainty in three-dimensional (3D) shapes is important in a large number of scientific and engineering areas including: biometrics, biomedical imaging, and multimodality image registration. It is well known that 3D star-shaped objects can be represented by Fourier descriptors such as spherical harmonics and double Fourier series. However, the statistics of these spectral shape models have not been widely explored. This article presents a spectral theory and its applications in 3D shape modeling. Spherical harmonic (SH) expansions over the unit sphere not only provide a low dimensional polarimetric parameterization of stochastic shape, but also correspond to the Karhunen-Loeve (K-L) expansion of any isotropic random field on the unit sphere. Spherical harmonic expansions permit estimation and detection tasks, such as optimal shape filtering, object registration, and shape classification, which can be performed directly in the spectral domain with low computational complexity.

Partial updating of LMS filter coefficients is an effective method for reducing the computational load and the power consumption in adaptive filter implementations. The sequential partial update LMS algorithm is one popular algorithm in this category. A first-order stability analysis of this algorithm was performed (Douglas, 1997) on wide sense stationary signals under the restrictive assumption of small step size parameter /spl mu/. The necessary and sufficient condition derived on /spl mu/ for convergence in the mean was identical to the one for guaranteeing stability in the mean of LMS. First-order sufficient conditions were derived (Godavarti et al., 1999) for stability without the aforementioned small /spl mu/ assumption. The sufficient region of convergence derived was smaller than that of regular LMS. In this paper, we establish that for stationary signals the sequential algorithm converges in mean for the same values of the step size parameter /spl mu/ for which the regular LMS does. In other words, we show that the conclusion drawn Douglas holds without the restrictive assumption of small /spl mu/. We also derive sufficient conditions for stability on /spl mu/ for cycle-stationary signals.

There has been considerable recent interest in applying maximal invariant (MI) hypothesis testing as an alternative to the generalized likelihood ratio (GLR) test. This interest has been motivated by several attractive theoretical properties of MI tests including: exact robustness to variation of nuisance parameters, finite-sample min-max optimality (in some cases), and distributional robustness. However, in the deep-hide target detection problem, there are regimes for which either of the MI and the GLR tests can outperform the other. We discuss conditions under which the MI tests can be expected to outperform the GLR tests in the context of a radar imaging and target detection application. We also show that the relative advantage of the MI tests is robust to boundary estimation errors.

Inference of network internal link characteristics has become an increasingly important issue for operating and evaluating large telecommunication networks. Since it is usually impractical to directly monitor each link along a specific path, end-to-end probes are sometimes used to collect link characteristic information at edge nodes of the network. This paper deals with unicast probing methods for estimation of link delay characteristics. Unicast traffic is easy to generate and is supported by almost every network currently in operation. Under the assumptions that link delays are spatially and temporally independent, we propose a bias corrected estimator for the internal link delay cumulant generating function (CGF) based on unicast probe end-to-end delay measurements. Through simulation we show that the proposed estimator attains a level of mean squared error comparable to link delay CGF estimates obtained from directly measured link delay statistics. We can use these CGF estimates to estimate delay mean, variance and level exceedance probabilities for each link.

Of increasing importance is estimation of internal link parameters in communications networks. Multicast probes are a way to gather statistics about internal links from edge node measurements. The problem of estimating link loss probabilities for a multicast distribution tree is examined. Our model assumes loss statistics are distributed to session participants by a network protocol such as RTCP. We propose a decentralized algorithm for ML estimation of the link loss probabilities in a chain of nodes rooted at the source node of the multicast distribution tree and terminating at a given leaf. An expression for the Cramer-Rao bound and an approximate form for the probability distribution function of the estimator are given. The performance of the algorithm is evaluated using computer simulations for a bottleneck detection application.

This paper presents an overview of some of the theory and application of stochastic minimal graphs in the context of entropy estimation for imaging applications. Stochastic graphs which span a set of extracted image features can be constructed to yield consistent estimators of Jensen's entropy difference for between pairs of images. Unlike traditional plug-in entropy estimates based on density estimation, stochastic graph methods provide direct estimates of these quantities. We review the stochastic graph approach to entropy estimation, compare convergence rates to that of plug-in estimators, and discuss a geo-registration application.

The solution of elliptic partial differential equations arises in 3D surface reconstruction and active contours. Most current approaches are iterative including finite element methods (FEM) and finite difference methods (FDM). We describe a fast spectral method for solving elliptic equations over the unit sphere. A double Fourier series expansion is applied to model convex or star-shaped 3D surfaces. The Helmholtz equation governing a diffusion on the unit sphere is solved by spectral methods using the double Fourier series as orthogonal basis functions. The optimization of the regularization parameter, which controls the tradeoff between denoising and matching high spatial frequencies, is studied for different 3D shapes and noise models. We show how the resultant solution can be combined with active contour methods to speed up 3D medical image segmentation. A number of examples and simulation results are presented to illustrate the algorithm.

This paper presents an overview of some of the recent theory and application of stochastic minimal graphs in the context of entropy estimation for imaging applications. Stochastic graphs which span a set of extracted image features can be constructed to yield consistent estimators of Jensen's entropy difference for between pairs of images. Unlike traditional plug-in entropy estimates based on density estimation, stochastic graph methods provide direct estimates of these quantities. We review the stochastic graph approach to entropy estimation, compare convergence rates to that of plug-in estimators, and discuss a geo-registration application.

In this paper we propose to simultaneously detect lane and pavement boundaries by fusing information from both optical and radar images. The boundaries are described with concentric circular models, whose parameters are compatible and will result in better conditioned estimation problems than previous parabolic models. The optical and radar imaging processes are represented with Gaussian and log-normal probability densities, with which we successfully avoid the ad hoc weighting scheme carried on the two likelihood functions. The multisensor fusion boundary detection problem is posed in a Bayesian framework and a joint maximum a posteriori (MAP) estimate is employed to locate the lane and pavement boundaries. Experimental results have shown that the fusion algorithm outperforms single sensor based boundary detection algorithms in a variety of road scenarios. And it also yields better boundary detection results than the fusion algorithm that took advantage of existing prior and likelihood formulations.

Registration of an image, the query or reference, to a database of rotated and translated exemplars constitutes an important image retrieval and indexing application which arises in biomedical imaging, digital libraries, georegistration, and other areas. Two important issues are the specification of a class of discriminatory and generalizable image features and determination of an appropriate image-dissimilarity measure to rank the closeness of the query image with respect to images in the database. The theoretically best set of features and dissimilarity measure are those which can be implemented with the lowest misregistration error rate. We study a method based on feature discrimination using feature coincidence trees and mutual /spl alpha/-information measures of feature correlation. Feature coincidence trees represent the commonality between pairs of images using joint histograms of many simple features, or tags, which are organized in a data structure similar to that of Y. Amit and D. Geman's randomized trees for shape recognition (see Neural Computation, vol.9, p.1545-88, 1997). The mutual alpha-information measure is a ranking discriminant applied to the joint histograms which is motivated by a large deviations framework for detection error rates. We illustrate the methodology in the context of registering ultrasound scans of human breast images.

This paper addresses a target detection problem in radar imaging for which the covariance matrix of unknown Gaussian clutter has block diagonal structure. This block diagonal structure is the consequence of a target lying along a boundary between two statistically independent clutter regions. Here, we design adaptive detection algorithms using both the generalized likelihood ratio (GLR) and the invariance principles. There has been considerable interest in applying invariant hypothesis testing as an alternative to the GLR test. This interest has been motivated by several attractive properties of invariant tests including: exact robustness to variation of nuisance parameters and possible finite-sample min-max optimality. However, in our deep-hide target detection problem, there are regimes for which neither the GLR nor the invariant tests uniformly outperforms the other. We discuss the relative advantages of GLR and invariance procedures in the context of this radar imaging and target detection application.

We consider the computational cutoff rate and its implications on signal design for the complex quasi-static Rayleigh flat-fading spatio-temporal channel under a peak-power constraint where neither transmitter nor receiver know the channel matrix. The cutoff rate has an integral representation which is an increasing function of the distance between pairs of complex signal matrices. When the analysis is restricted to finite-dimensional sets of signals, interesting characterizations of the optimal rate-achieving signal constellation can be obtained. For an arbitrary finite dimension, the rate-optimal constellation must admit an equalizer distribution, i.e., a positive set of signal probabilities which equalizes the average distance between signal matrices in the constellation. When the number N of receive antennas is large, the distance-optimal constellation is nearly rate-optimal. When the number of matrices in the constellation is less than the ratio of the number of time samples to the number of transmit antennas, the rate-optimal cutoff rate attaining constellation is a set of equiprobable mutually orthogonal unitary matrices. When the signal-to-noise ratio (SNR) is below a specified threshold, the matrices in the constellation are rank one and the cutoff rate is achieved by applying all transmit power to a single antenna and using orthogonal signaling. Finally, we derive recursive necessary conditions and sufficient conditions for a constellation to lie in the feasible set.

We relate the distinguishing features of the fixed point power-of-two step size LMS algorithm's learning curve to the precision of its data and coefficient variables. In particular, we show that the increase in the steady state MSE floor due to finite precision effects is determined primarily by data quantization while the decrease in convergence rate due to finite precision is determined by both data and coefficient quantization. We also derive a condition under which the slowdown phenomenon can be eliminated, given the reference variance and lower bounds on the minimum MSE and optimal weight vector magnitude.

Theoretical results have been established in non-parametric entropy estimation, based on asymptotic properties of minimal spanning trees (MST). A new application is proposed for the automatic extraction of time-frequency skeletons in the case of multicomponent chirp-like signals. The proposed method makes use of local maxima of a time-frequency distribution (considered as realizations of a 2D or 3D process), and exploits the efficiency of MSTs for density discrimination and clustering.

We present and compare adaptive detection algorithms developed for synthetic aperture radar (SAR) targets in structured clutter, utilizing both generalized likelihood ratio (GLR) tests and maximal invariant (MI) tests. We consider the problem of detecting a target straddling a known boundary between two independent clutter regions inducing a clutter covariance matrix with block diagonal structure. GLR and MI tests are presented for various clutter scenarios: two totally unknown clutter types, one of the clutter types known except for its variance, and one of the clutter types completely known. Numerical comparisons illustrate that GLR tests and MI tests are complementary-neither test strategy uniformly outperforms the other-suggesting that it may be worthwhile to hybridize these tests for overall optimal performance.

Registration is a fundamental task in image processing and quite a few registration techniques have been developed in various fields. In this paper we propose a novel graph-representation method for image registration with Renyi entropy as the dissimilarity metric between the images. The image matching is performed by minimizing the length of the minimum spanning tree (MST) which spans the graph generated from the overlapped images. Our method also takes advantage of the minimum k-point spanning tree (k-MST) approach to robustify the registration against spurious discrepancies in the images. The proposed algorithm is tested in two applications: registering magnetic resonance (MR) images, and registering an electro-optical image with a terrain height map. In both cases the algorithm is shown to be accurate and robust.

We discuss a method for classification of digitally modulated signals based on performing subspace decomposition on a positive definite matrix of higher order moments of the received signals. Specifically, we specialize a general approach originally introduced for detection and classification of noise contaminated patterns to the case of digitally modulated signals such as M-ary PSK and QAM. We consider two different classifiers: one that provides only satisfactory performance for high signal-to-noise ratio, and one that performs also well in the low SNR regime. The former has the additional advantage of being invariant to both unknown phase angle (rotation) and signal amplitude, and can be used for all QAM signal constellations (including M-ary PSK), whereas the latter is only used for discrimination of M-ary PSK signals. Using simulation, we analyze the performance of the proposed classifier for transmission over the additive white Gaussian noise channel and both coherent and non-coherent reception. Moreover, the robustness of the classifier against mismatched noise modeling is discussed.

Accelerated algorithms for maximum-likelihood image reconstruction are essential for emerging applications such as three-dimensional (3-D) tomography, dynamic tomographic imaging, and other high-dimensional inverse problems. In this paper, we introduce and analyze a class of fast and stable sequential optimization methods for computing maximum-likelihood estimates and study its convergence properties. These methods are based on a proximal point algorithm implemented with the Kullback-Liebler (KL) divergence between posterior densities of the complete data as a proximal penalty function. When the proximal relaxation parameter is set to unity, one obtains the classical expectation-maximization (EM) algorithm. For a decreasing sequence of relaxation parameters, relaxed versions of EM are obtained which can have much faster asymptotic convergence without sacrifice of monotonicity. We present an implementation of the algorithm using More's (1983) trust region update strategy. For illustration, the method is applied to a nonquadratic inverse problem with Poisson distributed data.

Treats a problem arising in the design of intelligent vehicles: automated detection of lane and pavement boundaries using forward-looking optical and radar imaging sensors mounted on an automobile. In previous work, lane and pavement boundaries have always been located separately. This separate detection strategy is problematic in situations when either the optical or the radar image is too noisy. We propose a Bayesian multisensor image fusion method to solve our boundary detection problem. This method makes use of a deformable template model to globally describe the boundaries of interest. The optical and radar imaging processes are described with random field likelihoods. The multisensor fusion boundary detection problem is reformulated as a joint MAP estimation problem. However, the joint MAP estimate is intractable, as it involves the computation of a notoriously difficult normalization constant, also known as the partition function. Therefore, we settle for the so-called empirical MAP estimate, as an approximation to the true MAP estimate. Several experimental results are provided to demonstrate the efficacy of the empirical MAP estimation method in simultaneously detecting lane and pavement boundaries. Fusion of multi-modal images is not only of interest to the intelligent vehicles community, but to others as well, such as biomedicine, remote sensing, target recognition. The method presented in the paper is also applicable to image fusion problems in these other areas.

Partial updating of LMS filter coefficients is an effective method for reducing the computational load and the power consumption in adaptive filter implementations. Only in the recent past has any work been done on deriving conditions for filter stability, convergence rate, and steady state error for the partial update LMS algorithm. Douglas (see IEEE Trans. Circuits and Systems-II: Analog and Digital Signal Processing, vol.44, p.209-16, 1997) derived approximate bounds on the step-size parameter /spl mu/ which ensure stability in-the-mean of the alternating even/odd index coefficient updating strategy. Unfortunately, due to the restrictiveness of the assumptions, these bounds are unreliable when fast convergence (large /spl mu/) is desired. In this paper, tighter bounds on /spl mu/ are derived which guarantee convergence in the mean of the coefficient sequence for the case of wide sense stationary signals.

Adaptive filters are used in a number of applications, many of which can benefit from a reduction in power. In this paper we present derivations of the approximate expressions used for the increase in mean square error of the LMS adaptive algorithm when the total processing power is decreased.

We consider a geometric coverage process consisting of a random number of disks, or grains, having random radii and positions in the plane. Our objective is granulometry: estimation of a parameter of the disk radius distribution, which is important in diverse applications such bio-assay, ballistics, and numerical taxonomy. These disks are only incompletely observed due to mutual occlusion, spatial blurring and additive noise. We use a measurement channel paradigm to derive an expectation-maximization (EM) type estimation algorithm and a distortion-rate lower bound on estimation error.

This paper treats automated detection of road and lane boundaries by fusing information from forward-looking optical and active W-band radar imaging sensors mounted on a motor vehicle. A deformable template model is used to globally describe the boundary shapes. The optical and radar imaging processes are characterized with random field likelihoods. The multisensor fusion edge detection problem is posed in a Bayesian framework and a joint MAP estimate is employed to locate the road and lane boundaries. Three optimization approaches (multi-resolution pseudo-exhaustive search, Metropolis algorithm, and Metropolis algorithm with pre-tuned curvature) are proposed to implement the joint MAT estimate. Experimental results are shown to demonstrate that the joint MAP algorithm operates robustly and efficiently in a variety of road scenarios.

Let /spl chi//sub n/=(x/sub 1/,...,x/sub n/), be an independent and identically distributed (i.i.d.) sample having multivariate distribution P. We derive almost sure (a.s.) limits for the power-weighted edge weight function of greedy approximations to a class of minimal graphs spanning k of the n samples. The class includes minimal k-point graphs constructed by the partitioning method of Ravi, Sundaram, Marathe, Rosenkrantz, and Ravi (see Proc. 5th Annu. ACM-SIAM Symp. Discrete Algorithms, Arlington, VA, p.546-55, 1994), where the edge weight function satisfies the quasi-additive property of Redmond and Yukich (see Ann. Appl. Probab., vol.4, no.4, p.1057-73, 1994). In particular, this includes greedy approximations to the k-point minimal spanning tree (k-MST), Steiner tree (k-ST), and the traveling salesman problem (k-TSP). An expression for the influence function of the minimal-weight function is given which characterizes the asymptotic sensitivity of the graph weight to perturbations in the underlying distribution. The influence function takes a form which indicates that the k-point minimal graph in d>1 dimensions has robustness properties in R/sup d/ which are analogous to those of rank-order statistics in one dimension. A direct result of our theory is that the log-weight of the k-point minimal graph is a consistent nonparametric estimate of the Renyi entropy of the distribution P. Possible applications of this work include: analysis of random communication network topologies, estimation of the mixing coefficient in /spl epsiv/-contaminated mixture models, outlier discrimination and rejection, clustering, and pattern recognition, robust nonparametric regression, two-sample matching, and image registration.

In this paper a minimax methodology is presented for combining information from two imaging modalities having different intrinsic spatial resolutions. The focus application is emission computed tomography (ECT), a low-resolution modality for reconstruction of radionuclide tracer density, when supplemented by high-resolution anatomical boundary information extracted from a magnetic resonance image (MRI) of the same imaging volume. The MRI boundary within the two-dimensional (2-D) slice of interest is parameterized by a closed planar curve. The Cramer-Rao (CR) lower bound is used to analyze estimation errors for different boundary shapes. Under a spatially inhomogeneous Gibbs field model for the tracer density a representation for the minimax MRI-enhanced tracer density estimator is obtained. It is shown that the estimator is asymptotically equivalent to a penalized maximum likelihood (PML) estimator with resolution-selective Gibbs penalty. Quantitative comparisons are presented using the iterative space alternating generalized expectation maximization (SAGE-FM) algorithm to implement the PML estimator with and without minimax weight averaging.

With the rising number of modulation types used in multi-user and multi-service digital communication systems, the need to find efficient methods for their discrimination in the presence of noise has become increasingly important. We present a new approach based on a pattern recognition method previously applied to word spotting problems in binary images. In this approach, a large number of spatial moments are arranged in a symmetric positive definite matrix for which eigendecomposition and noise subspace processing methods can be applied. The resultant denoised moment matrix has entries which are used in place of the raw moments for improved pattern classification. In this paper, we generalize the moment matrix technique to grey scale images and apply the technique to discrimination between M-ary PSK and QAM constellations in signal space. Invariance to unknown phase angle and signal amplitude is achieved by representing the in-phase and quadrature components of the signal in the complex plane, and computing joint moments of normalized magnitude and phase components.

A method for incorporating anatomical MRI boundary side information into penalized maximum likelihood (PML) emission computed tomography (ECT) image reconstructions using a set of averaged Gibbs weights was proposed by Hero and Piramuthu (see Proc. of IEEE/EURASIP Workshop on Nonlinear Signal and Image Processing, 1997). A quadratic penalty based on Gibbs weights was used to enforce smoothness constraints everywhere in the image except across the estimated boundary of the ROI. In this methodology, a limiting form of the posterior distribution of the MRI boundary parameters was used to average the Gibbs weights obtained by Titus, Hero and Fessler (see IEEE Int. Conf. on Image Processing, vol.2, Laussane, 1996). There is an improvement in performance over the method proposed by Titus et al., when the variance of boundary estimates from the MRI data becomes significant. Here, we present the empirical performance analysis of the proposed method of averaged Gibbs weights.

The authors previously presented a methodology for incorporating perfect extracted MRI anatomical boundary estimates to improve the performance of penalized likelihood (PL) emission computed tomography (ECT) image reconstruction and ECT tracer uptake estimation. This technique used a spatially variant quadratic Gibbs penalty which enforced smoothness everywhere in the ECT image except across the MRI-extracted boundary of the ROI. When high quality estimates of the anatomical boundary are available and MRI and ECT images are perfectly registered, the performance of this Gibbs penalty method is very close to that attainable using perfect side information, i.e., an errorless anatomical boundary estimate. However when the variance of the MRI-extracted boundary estimate becomes significant this method performs poorly. Here we present a modified Gibbs penalty function which accounts for errors in side information based on an asymptotic min-max robustness approach. The resulting penalty is implemented with a set of averaged Gibbs weights where the averaging is performed with respect to a limiting form of the min-max induced posterior distribution of the MRI boundary parameters. Examples are presented for tracer uptake estimation using the SAGE version of the EM algorithm and various parameterizations of the anatomical boundaries.

We give a novel method for performing statistically significant detection of specified object features which operates directly on X-ray (Gaussian) or radio-isotope (Poisson) tomographic projection data. The method is based on constructing an exact (1-/spl alpha/)100% confidence region on the object derived by backprojecting a projection-domain confidence region into object space. The projection-domain confidence region is a minimal volume hyper-rectangle specified by the projection data and the appropriate quantiles of the standard Gaussian or Poisson distribution. We implement the back-projection step using a very accurate bounded error estimation algorithm which sequentially approximates the feasible set (object-domain confidence region) given the data and its specified error bounds (known Gaussian or Poisson quantiles). By testing whether this object-domain (1-/spl alpha/)100% confidence region contains objects with hypothesized features we obtain a feature detection algorithm which has constant false alarm rate (CFAR) /spl alpha/ and is adaptive in the sense that no image reconstruction is required and no unknown nuisance parameters need be estimated.

In this paper, a method is introduced for incorporating perfectly registered MRI boundary information into a penalized likelihood emission reconstruction scheme. The boundary curve is modeled as a periodic spline whose coefficients are estimated from the MRI image. The resulting boundary estimate is mapped to a spatially variant set of Gibbs weights. When incorporated into a quadratic roughness penalty, these weights improve emission reconstruction bias/variance performance by preventing smoothing across the estimated boundary. Finally, we derive a new penalty function that accounts for the uncertainty inherent in the boundary estimates.

Different signal realizations generated from a given source may not appear the same. Time shifts, frequency shifts, and scales are among the signal variations commonly encountered. Time-frequency distributions (TFDs) covariant to time and frequency shifts and scale changes reflect these variations in a predictable manner. Based on such TFDs, representations invariant to these signal distortions are possible. Presented here are two approaches for discriminating between signal classes where within class translation and scale variation occur. The first method uses an auto-correlation followed by a scale transform to achieve the invariances. The second method treats the TFD as a two-dimensional probability density function and applies a transformation that removes the mean and variance to provide the shift and scale invariance. Each method employs discrimination mechanisms to yield powerful results.

One of the most challenging problems in automatic target recognition is reliable detection of targets in high clutter backgrounds. When the clutter statistics are unknown or highly variable, the false alarm rate of classical detection algorithms, e.g. the matched filter, cannot be controlled and target detection become unreliable. The reason for this is lack of robustness of the test statistics to clutter variations. We apply maximal invariants to design target detection algorithms which have constant false alarm rate yet maintain high target detection rate. Numerical comparisons are presented for multispectral and multisnapshot radar images which illustrate that significant gains are achievable using invariance approaches.

We present a method for the detection and classification of a spatial pattern in noise contaminated binary images which is based on performing subspace decomposition on a nonnegative definite matrix of higher order moments of the image. We introduce a method which uses normalized power moments or ascending factorial moments as descriptors. While the set of p-th order factorial moments are in one-to-one correspondence with the set of p-th order power moments, the computation of factorial moments is much more numerically stable than the power moments. Indeed, using factorial moments we are able to implement pattern classifiers with over 30% more moment descriptors. We illustrate these techniques for word classification in binary document images.

Three methods of detecting road edges in millimeter-wave radar images are presented. All of them are based on deformable template priors and random field likelihoods. The first method is formulated in a Bayesian setting and employs an adaptive MAP estimate. The second method is a modification of the first, using a novel weighting scheme. The third method is based on a three-region indicator matrix which is used to impose the non-linear constraints implicit on road geometry via addition of a sum of quasi-quadratic matrix forms to the log-normal likelihood. Unlike the first two methods, that employ the Metropolis algorithm to find the optimal road edges, the third method uses a deterministic recursive scheme designed to find the optimal indicator matrix. Experimental results are presented to show the advantages of these methods.

A maximum likelihood (ML) method for joint estimation of amplitude, phase, time delay, and data demodulation in a single-user direct sequence spread spectrum communication system is developed. The likelihood function is analytically intractable, so a recursive estimation algorithm is considered. The expectation maximization (EM) algorithm has been used in similar problems, however, in this case it is not computationally efficient. A variant of the EM algorithm, called space alternating generalized EM (SAGE), has been derived. We apply the SAGE algorithm to the sequence estimation problem in a way which results in simple sequential updates of all the estimated parameters. An important feature of the proposed algorithm is the use of a discrete wavelet decomposition of the received signal as a sufficient statistic. The consequence is that all the information is still available to the receiver, while the complicated estimation problem is considerably simplified. Computer simulations of a single user system were performed. It is shown that the algorithm has a fast convergence, and essentially achieves optimal performance.

This paper presents a statistically based method for spotting target words in documents. The crux of the method is the representation of a word by a spatial (planar) point process evolving on a regular lattice of coordinate pairs. This is accomplished by extracting the coordinate pairs, i.e. pixel locations, where the binary bitmap values of the word are non-zero. With this representation the word is completely determined by the spatial intensity function, i.e. the unnormalized spatial probability density function, associated with the extracted set of coordinate pairs. In this work, we use a finite number of moments of the intensity function to characterize the word. Location and scale invariance are obtained by transforming the coordinate pairs to have zero mean and unit variance. Finally, optimal detection strategies are applied to the moments to make the decision.

This paper presents a method for incorporating anatomical NMR boundary side information into penalized maximum likelihood (PML) emission image reconstructions. The NMR boundary is parameterized as a periodic spline curve of fixed order and number of knots that is known a priori. Maximum likelihood (ML) estimation of the spline coefficients yields an "extracted" boundary, which is used to define a set of Gibbs weights on the emission image space. These weights, when coupled with a quadratic penalty function, create an edge-preserving penalty that incorporates our prior knowledge effectively. Qualitative analysis demonstrates that our method results in smooth images that do not suffer loss of edge contrast, while quantitative estimates of bias and variance for various values of the smoothing parameter show an improvement over standard quadratically penalized maximum likelihood.

We develop a non-parametric method of nonlinear prediction based on adaptive partitioning of the phase space associated with the process. The partitioning method is implemented with a recursive tree-structured vector quantization algorithm which successively refines the partition by binary splitting where the splitting threshold is determined by a penalized maximum entropy criterion. A complexity penalty is derived and applied to protect against high statistical variability of the predictor structure. We establish an important relation between our tree-structured model for the process and generalized non-linear thresholded AR model (ART). We illustrate our method for two cases where classical linear prediction is ineffective: a chaotic "double-scroll" signal measured at the output of a Chua-type electronic circuit, and a simulated second order ART model.

The maximum likelihood (ML) estimation method for simultaneous amplitude, time delay, and data demodulation in direct sequence spread spectrum communication is proposed. The likelihood function is analytically intractable, so we consider a recursive estimation algorithm. The expectation-maximization (EM) algorithm has found increasing use in similar problems, however, for this case it is analytically intractable. A variant of the EM algorithm, called space alternating generalized EM (SAGE), has been derived. We apply the SAGE algorithm to the sequence estimation problem in a way which allows for simple sequential updates of the parameters. The resulting algorithm maximizes the penalized likelihood function, where the penalty is chosen to ensure good synchronization performance. Simulation results show that the algorithm has fast convergence, and essentially achieves optimal performance.

We give estimation error bounds and specify optimal estimators for continuous, closed boundary curves in an NMR image. The boundary is parameterized using periodic B-splines. A Cramer-Rao lower bound on mean-square-estimate error in the presence of system smoothing and Gaussian noise is derived, and the performance of maximum likelihood and penalized maximum likelihood estimators is compared to this bound. Finally, we comment on the usefulness of estimates of the boundary for providing anatomical side information in the reconstruction of functional tomographic images like those of a PET or SPECT system.

Most expectation-maximization (EM) type algorithms for penalized maximum-likelihood image reconstruction converge slowly, particularly when one incorporates additive background effects such as scatter, random coincidences, dark current, or cosmic radiation. In addition, regularizing smoothness penalties (or priors) introduce parameter coupling, rendering intractable the M-steps of most EM-type algorithms. This paper presents space-alternating generalized EM (SAGE) algorithms for image reconstruction, which update the parameters sequentially using a sequence of small "hidden" data spaces, rather than simultaneously using one large complete-data space. The sequential update decouples the M-step, so the maximization can typically be performed analytically. We introduce new hidden-data spaces that are less informative than the conventional complete-data space for Poisson data and that yield significant improvements in convergence rate. This acceleration is due to statistical considerations, not numerical overrelaxation methods, so monotonic increases in the objective function are guaranteed. We provide a general global convergence proof for SAGE methods with nonnegativity constraints.

This paper addresses the problem of finite sample simultaneous detection and estimation which arises when estimation of signal parameters is desired but signal presence is uncertain. In general, a joint detection and estimation algorithm cannot simultaneously achieve optimal detection and optimal estimation performance. We develop a multihypothesis testing framework for studying the tradeoffs between detection and parameter estimation (classification) for a finite discrete parameter set. Our multihypothesis testing problem is based on the worst case detection and worst case classification error probabilities of the class of joint detection and classification algorithms which are subject to a false alarm constraint. This framework leads to the evaluation of greatest lower bounds on the worst case decision error probabilities and a construction of decision rules which achieve these lower bounds. For illustration, we apply these methods to signal detection, order selection, and signal classification for a multicomponent signal in noise model. For two or fewer signals, an SNR of 3 dB and signal space dimension of N=10 numerical results are obtained which establish the existence of fundamental tradeoffs between three performance criteria: probability of signal detection, probability of correct order selection, and probability of correct classification. Furthermore, based on numerical performance comparisons between our optimal decision rule and other suboptimal penalty function methods, we observe that Rissanen's (1978) order selection penalty method is nearly min-max optimal in some nonasymptotic regimes.>

A new technique for modelling biological signals as a linear combination of non-orthogonal Gabor logons is described. The technique has been applied to two types of signals, event-related potentials (ERPs) and temporomandibular joint (TMJ) clicks. Examination of time-frequency representations of these signals revealed that they appear to consist of a small number of localized energy concentrations. Attempts to capture this apparent low dimensionality with the standard orthogonal Gabor expansion and the standard wavelet transform were unsuccessful. However, the non-orthogonal Gabor decomposition method described in this paper provides a compact, accurate signal representation and the parameters provide a good basis for ERP category and TMJ click classification.>

Computation of the Cramer-Rao bound involves inversion of the Fisher information matrix (FIM). The inversion can become computationally intractable when the number of unknown parameters is large. Hero et. al. (see IEEE Nuclear Science Symposium and Medical Imaging Conference, Orlando, 1983) has presented a recursive, monotonically convergent and computationally efficient algorithm to invert sub-matrices of the FIM corresponding to a small region of interest in image reconstruction. The convergence rate of this algorithm depends on a splitting matrix which can be interpreted as a complete-data FIM. We investigate the acceleration of the algorithm using several different choices of the complete-data FIM. We also present a conjugate gradient based algorithm which achieves a much faster convergence rate at the expense of monotone convergence. We apply the methods developed in this paper to emission tomography.>

We provide a methodology for specifying a set of simultaneous (1-/spl alpha/)% confidence intervals on the intensity of each image pixel for emission and transmission tomography. These intervals give a (1-/spl alpha/)% confidence region which, given a specific family of noise distributions, e.g. Gaussian or Poisson, is guaranteed to contain the actual image with probability at least 1-/spl alpha/. This region is a "set estimate" of the image which can be used to study confidence levels of popular image reconstructions such as filtered back projection, weighted-least-squares, and maximum likelihood. Alternatively, the set estimate can be used as a feasibility region from which particular image estimates can be selected based on additional criteria. A simulation for parallel ray projection geometries in emission tomography is given.>

We apply a uniform Cramer-Rao (CR) bound to study the bias-variance trade-offs in parameter estimation. The uniform CR bound is used to specify achievable and unachievable regions in the bias-variance trade-off plane. The applications considered are: (1) two-dimensional single photon emission computed tomography (SPECT) system, and (2) one dimensional edge localization.>

We give a recursive algorithm to calculate submatrices of the Cramer-Rao (CR) matrix bound on the covariance of any unbiased estimator of a vector parameter /spl theta/_. Our algorithm computes a sequence of lower bounds that converges monotonically to the CR bound with exponential speed of convergence. The recursive algorithm uses an invertible "splitting matrix" to successively approximate the inverse Fisher information matrix. We present a statistical approach to selecting the splitting matrix based on a "complete-data-incomplete-data" formulation similar to that of the well-known EM parameter estimation algorithm. As a concrete illustration we consider image reconstruction from projections for emission computed tomography.>

The authors develop a strategy for joint estimation of physiological parameters and myocardial boundaries using ECT (emission computed tomography). They construct an observation model to relate parameters of interest to the projection data and to account for limited ECT system resolution and measurement noise. The authors then use a maximum likelihood (ML) estimator to jointly estimate all the parameters directly from the projection data without reconstruction of intermediate images. They also simulate myocardial perfusion studies based on a simplified heart model to evaluate the performance of the model-based joint ML estimator and compare this performance to the Cramer-Rao lower bound. Finally, the authors discuss model assumptions and potential uses of the joint estimation strategy.

The authors have previously developed a model-based strategy for joint estimation of myocardial perfusion and boundaries using ECT (emission computed tomography). They have also reported difficulties with boundary estimation in low contrast and low count rate situations. Here they propose using boundary side information (obtainable from high resolution MRI and CT images) or boundary regularization to improve both perfusion and boundary estimation in these situations. To fuse boundary side information into the emission measurements, the authors formulate a joint log-likelihood function to include auxiliary boundary measurements as well as ECT projection measurements. In addition, they introduce registration parameters to align auxiliary boundary measurements with ECT measurements and jointly estimate these parameters with other parameters of interest from the composite measurements. In simulated PET O-15 water myocardial perfusion studies using a simplified model, the authors show that the joint estimation improves perfusion estimation performance and gives boundary alignment accuracy of <0.5 mm even at 0.2 million counts. They implement boundary regularization through formulating a penalized log-likelihood function. They also demonstrate in simulations that simultaneous regularization of the epicardial boundary and myocardial thickness gives comparable perfusion estimation accuracy with the use of boundary side information.

A modified expectation-maximization (EM) algorithm is used to estimate the time delay tau of the intensity lambda (t- tau ) of an inhomogeneous Poisson process N/sub t/, whose points are only partially observed as a noise contaminated output X(t) of a linear time-invariant filter excited by a train of delta functions: a filtered Poisson process. A modified EM algorithm is implemented by using a linear approximation to the conditional mean estimate of the increment dN/sub t/, given X and tau . Simulation results showing that the EM algorithm converges rapidly, that it achieves an improvement over conventional time delay estimation methods, and that its mean square error virtually achieves the Cramer-Rao (CR) lower bound for high count rates are presented.>

For a general discrete parameter signal model and a false alarm constraint, the authors give a general theorem which specifies lower bounds on worst-case probability of miss, worst-case probability of incorrectly specifying the number of parameters (order selection), and worst-case probability of parameter estimation error. These bounds are achievable by constrained min-max decision rules: the constrained min-max detector, the constrained min-max order selector, and the constrained min-max parameter estimator, respectively. As in previous work, the authors use the theory to study fundamental tradeoffs between achievable estimation, order selection, and detection performance for a multiple component signal model. Numerical results indicate that for the example studied, parameter estimation optimality entails very little loss in detection performance, while detection optimality severely sacrifices parameter estimation performance.>

A new criterion for adaptive beamsumming is introduced which explicitly accounts for mean and RMS signal amplitudes yet is relatively simple to implement. The adaptation criterion is expressed as a convex combination of squared-mean array-gain and mean-squared array-gain at the output of the beamsummer. Theoretical and practical motivation for the criterion is given. Simulations are provided which indicate that, relative to the classical beamsummer, the new method gives adaptive weights which have better convergence properties, allow better multiple signal resolution, and produce lower signal angle-of-arrival estimator variance.>

Edge localization occurs when an edge detector determines the location of an edge in an image. The authors use statistical parameter estimation techniques to derive bounds on achievable accuracy in edge localization. These bounds, known as the Cramer-Rao bounds, reveal the effect on localization of factors such as signal-to-noise ratio (SNR), extent of edge observed, scale of smoothing filter, and a priori uncertainty about edge intensity. By using continuous values for both image coordinates and intensity, the authors focus on the effect of these factors prior to sampling and quantization. They also analyze the Canny algorithm and show that for high SNR, its mean squared error is only a factor of two higher than the lower limit established by the Cramer-Rao bound. Although this is very good, the authors show that for high SNR, the maximum-likelihood estimator, which is also derived, virtually achieves the lower bound.>

A method for gauging the tradeoff between parameter estimation and order selection estimation performance for discrete parameters is developed. The method is based on evaluation of lower bounds on worst-case probability of estimation error and worst-case probability of order selection error subject to a constraint on maximum false alarm probability. Since each of the two bounds is derived by evaluating the performance of an optimal order estimator and an optimal parameter estimator, respectively, the bounds are achievable. It is shown that it is generally impossible to achieve simultaneously the order selection and parameter estimation lower bounds: there is a necessary compromise between estimation and order selection. The authors present numerical studies of these bounds for a common multiple signal model.>

Using limiting forms of the Chapman-Robbins (1951) version of the Barankin bound, a study is made of the effect of parameter constraints on local lower bounds on estimator covariance. One such limiting form is the Cramer-Rao bound, for which constraints are seen to induce an oblique projection of the columns of the inverse Fisher information matrix onto a linear subspace tangent to the parameter constraint set. Another limiting form is the Bhattacharyya bound, which is defined in terms of higher-order Fisher information. For the Bhattacharyya bound, parameter constraints induce a transformation of the higher-order Fisher information that depends on the tangent space projection operator and its derivatives.>

Edge localization occurs when an edge detection algorithm is able to accurately determine the location of an edge in an image. Edge localization is formulated as a parameter estimation problem, and the authors derive a Cramer-Rao bound on achievable accuracy as measured by mean squared error. The bound reveals the effect on localization of factors such as signal to noise ratio, observation window size, scale of smoothing filter, and a priori uncertainty about edge intensity. The authors analyze the Canny (1986) algorithm and show that the variance of its localization error is only a factor of two higher than the lower limit established by the Cramer-Rao bound. Although this is very good, it is shown that the maximum-likelihood estimator, which is derived in this work, virtually achieves the lower bound.>

The problem of estimation of time shift of an inhomogeneous casually filtered Poisson process in the presence of additive Gaussian noise is discussed. Approximate expressions for the likelihood function, the MAP estimator, and the MMSE estimator that becomes increasingly accurate as the per-unit-time density of superimposed filter responses becomes small are obtained. The optimal MAP estimator takes the form of a cascade of linear and memoryless nonlinear components. For smooth point process intensities, the performance of the MAP estimator is studied via local bias and local variance. A rate distortion type lower bound on the MSE of any estimator of time delay is then derived by identification of a communications channel that accounts for the mapping from time delay to observation process. Results of numerical studies of estimator performance are presented. Based on the examples considered it is concluded: (1) the small-error MSE of the nonlinear MAP estimator can be significantly better than the small-error MSE of the optimal linear estimator: (2) the rate distortion lower bound can be significantly tighter than the Poisson limited bounds determined in previous studies.>

An optimal technique for performing simultaneous signal detection and signal classification when the probability of false alarm (P/sub FA/) is constrained to be below a prespecified threshold is presented. A constrained max-min strategy that has the property of ensuring the best minimum level of performance among detection/classification procedures which satisfy the constraint is derived. The procedure compares a set of weighted likelihood ratios to a threshold, and if the threshold is exceeded it chooses the signal class with highest weighted likelihood. The technique is applied to the problem of detection and classification of a change in distribution of an independent sequence.>

A Chapman-Robbins form of the Barankin bound is used to derive a multiparameter Cramer-Rao (CR) type lower bound on estimator error covariance when the parameter theta in R/sup n/ is constrained to lie in a subset of the parameter space. A simple form for the constrained CR bound is obtained when the constraint set Theta /sub C/, can be expressed as a smooth functional inequality constraint. It is shown that the constrained CR bound is identical to the unconstrained CR bound at the regular points of Theta /sub C/, i.e. where no equality constraints are active. On the other hand, at those points theta in Theta /sub C/ where pure equality constraints are active the full-rank Fisher information matrix in the unconstrained CR bound must be replaced by a rank-reduced Fisher information matrix obtained as a projection of the full-rank Fisher matrix onto the tangent hyperplane of the full-rank Fisher matrix onto the tangent hyperplane of the constraint set at theta . A necessary and sufficient condition involving the forms of the constraint and the likelihood function is given for the bound to be achievable, and examples for which the bound is achieved are presented. In addition to providing a useful generalization of the CR bound, the results permit analysis of the gain in achievable MSE performance due to the imposition of particular constraints on the parameter space without the need for a global reparameterization.>

A general method is presented for approximating the global error performance of ML (maximum likelihood)-type multiparameter estimators. Comparisons between the global approximation to the mean square error for known and unknown nuisance parameters indicate the degree to which nuisance parameters degrade the performance of ML estimators. The results of a numerical study illustrate the implementation of the method for time delay estimation in cases of coherent interference and Doppler effect.>

A mutual information (MI) criterion for the evaluation of tomographic imaging systems is introduced. The MI quantifies the quality of the tomographic projections in terms of the transfer of information from a slice of a three-dimensional object to the raw data at the detectors, and it provides a relevant tradeoff between sensitivity and resolution. The authors consider the application of the MI criterion to aperture evaluation for one-dimensional linear and three-dimensional parallel slice single photon emission computed tomography (SPECT) geometries. For the ideal case of known emission times, analytic expressions that give a necessary and sufficient condition for an aperture to maximize MI can be derived. Otherwise, an upper bound on the MI can be derived. The authors present a numerical comparison between the MI of several popular aperture designs and the MI-optimal apertures presented here.>

Using rate distortion theory, lower bounds are developed for the mean-square error of estimates of a random parameter of an M-dimensional inhomogeneous Poisson process with respect to which the energy, i.e. the average number of points, is invariant. The bounds are derived without stringent assumptions on either the form of the intensity or the prior distribution of the parameter, and they can handle random nuisance parameters. The derivation makes use of a side-information averaging principle applied to the distortion-rate function and a maximum-entropy property of energy-constrained Poisson processes. Under the additional assumption of conditional entropy invariance of the point process with respect to the parameter of interest, an explicit bound is given which depends on the information discrimination between the inhomogeneous conditionally Poisson process and a nearly homogeneous Poisson process. The application of the explicit bound is illustrated through a treatment of the problems of time-shift estimation and relative time-shift estimation for Poisson streams.>

The author treats the problem of time delay estimation for inhomogeneous filtered Poisson processes in the presence of Gaussian noise when the time delay parameter is imbedded in the intensity function of the point process. This is an important estimation problem in the synchronization of optical communications receivers, and positron emission tomography. Approximate expressions for the maximum a posteriori (MAP) and the minimum mean square error (MMSE) estimators are obtained which become increasingly accurate as the product of the filter time-width and the Poisson intensity amplitude approach zero. Large sample approximations to the bias and the MSE are presented for the approximate MAP estimator.>

A method for modeling large errors in correlation-based time-delay estimation is developed in terms of level-crossing probabilities. The level-crossing interpretation for peak ambiguity leads directly to an exact expression for the probability of large error involving the hazard function associated with the level-crossing process. Two models for the distribution of the error over the level-crossing time yield approximations to the mean-square error (MSE) that involve the low-order (>

In this paper we will discuss a new class of performance approximations for maximum likelihood type bearing estimation systems. This class is based on the application of various point process models to a sequence of error prone points along the likelihood trajectory. The point process model is described by two quantities: the intensity function of the local maxima locations over the parameter space, and a selection rule for the global maximum from the set of local maxima. This class gives new estimators to the Mean-Square Error and specializes to the approximation techniques of [1] and [6].

An alternative method for estimating the time delay between two noisy waveforms containing a common signal is presented. The estimate is obtained by means of an approximation to the center of symmetry of a certain correlation function. For narrowband signals preliminary results indicate that the procedure is less sensitive to peak ambiguity which is inherent in the classical optimal estimator.