Matrix completion plays an important role in machine learning and signal processing, with applications ranging from recommender systems to image inpainting. Many approaches have been considered to solve the problem and some offer computationally efficient solutions. In particular, a highly-efficient random coordinate descent approach reduces the per-epoch computation dramatically. This paper is concerned with further improvement of computational efficiency to expand the range of problem sizes and conditions that can be solved. Momentum acceleration is a well-known method to improve the efficiency of iterative algorithms, but applying it to random coordinate descent methods without increasing the computational complexity is non-trivial. To address this challenge, we introduce a momentum-accelerated randomized coordinate descent for matrix completion approach that does not increase computational complexity by accelerating at the level of epochs. Additionally, we propose an analysis-driven, tuning-free method for step size selection. To that end, we offer a convergence rate analysis for the algorithm. Using numerical evaluations, we demonstrate the competitiveness of the method and verify the theoretical analysis.

Autoregressive models play an important role in a variety of applications including finance, engineering, sciences, and agriculture. While for some models (e.g., physics-based models) parameters are known, in other domains the parameters may not be available. This paper deals with the estimation of the parameters of an autoregressive model with exogenous variables. A significant body of literature has explored autoregressive model estimation across different estimation criteria, data availability, and parameterization; however, limited attention has been given to the estimation problem under stability constraints. The incorporation of stability constraints often results in increased computational complexity. As an efficient alternative, we propose to estimate stable ARX parameters using randomized coordinate descent. To demonstrate the efficiency of the proposed approach, we present an empirical convergence study and compare our approach to a state-of-the-art alternative.

Low-rank matrix completion, the process of estimating a low-rank matrix from a small subset of its entries, has many applications including collaborative filtering and system identification. Many algorithms have been considered to address this problem. Coordinate descent has been previously proposed to tackle scalability both in terms of runtime and space complexity. Due to the use of regularization in the method, the method provides no convergence guarantees. Additionally, the choice of the regularization parameter can significantly affect the algorithm performance. Here, we study a regularization-free randomized coordinate descent method that uses an efficient periodic refactorization to guarantee a linear convergence rate. To support the proposed algorithm, we provide an analysis of the algorithm asymptotic convergence rate alongside a per-iteration computational complexity analysis. Using numerical experiments, we verify the correctness of our analysis and illustrate the overall computation advantage of the proposed approach.

Vine stress resulting from soil water content (SWC) restrictions allows growers to improve grape and subsequent wine quality. In this work, we consider learning models that can forecast SWC to assist growers' irrigation decisions. In particular, we investigate training auto-regressive recurrent neural networks to make multi-day hourly forecasts of SWC based on historical data from soil-moisture sensors, irrigation sched-ules, and evapotranspiration estimates. Our work addresses two practical challenges in training such models. First, trained auto-regressive models are prone to error propagation, which quickly degrades longer-term forecasts. Second, it is difficult to learn the underlying causal relationship between irrigation and soil moisture due to the training data having limited coverage of the primary control input, irrigation. We propose a training strategy that combines one-step teacher forcing loss with a loss over multi-step autoregressive predictions and novel regularization terms to ensure SWC forecasts align with scientific models, effectively addressing the key challenges. We present results from five irrigation blocks with two cultivars, using datasets ranging from 2947 to 4784 hourly measurements of SWC, irrigation, and weather. Our methodology achieves precise SWC predictions and generates realistic forecasts for untrained irrigation scenarios.

This paper considers the problem of performing post-attack forensic analysis for a test-time attack on a machine learning model. A test-time attack can be represented as a mapping that receives a benign test example as the input and outputs a falsified version of it. Given a set of attacked examples in the post-attack time, our objective is to identify the correct attack mapping among the collection of candidate attack strategies with diverse objectives and constraints. We present an attack mapping identification method that utilizes a pre-attack example recovery mechanism as a feature extraction method. Using numerical experiments, we demonstrate the effectiveness of the proposed approach in detecting the correct attack mapping among a number of different candidate attack strategies.

In this paper, we investigate the problem of signal motif discovery. In the formulation considered, the goal is to find an unknown pattern (or motif) repeated across multiple data sets. This problem formulation can be applied to various domains, such as DNA sequence alignment and matching, motif discovery in time-series, and object detection and localization in images. We take the approach of minimizing an objective that is the sum over a measure of the difference between a candidate instance in each signal collection (or set) and the unknown pattern. Additionally, a non-negative instance dependent penalty is introduced. The proposed general objective can be used to capture well-known problems (e.g., blind joint time-delay estimation). Due to the non-convex nature of the problem and often the integer programming flavor of the approach, brute-force solution is non-polynomial and computationally prohibitive for large scale problems. We propose an efficient polynomial time (quadratic in the number of instances) bipartite graph based approximation to solve the problem. We provide a theoretical analysis for the proposed solution including bounds on the gap from the optimal solution and conditions for optimality . In particular, we show that the objective value for the proposed solution is no more than twice the objective value of the optimal solution. To illustrate the merit of the proposed approach, we present qualitative and quantitative empirical analysis of the proposed approach on several applications and compare our method to appropriate alternatives.

With increasing data volumes, the bottleneck in obtaining data for training a given learning task is the cost of manually labeling instances within the data. To alleviate this issue, various reduced label settings have been considered including semi-supervised learning, partial- or incomplete-label learning, multiple-instance learning, and active learning. Here, we focus on multiple-instance multiple-label learning with missing bag labels. Little research has been done for this challenging yet potentially powerful variant of incomplete supervision learning. We introduce a novel discriminative probabilistic model for missing labels in multiple-instance multiple-label learning. To address inference challenges, we introduce an efficient implementation of the EM algorithm for the model. Additionally, we consider an alternative inference approach that relies on maximizing the label-wise marginal likelihood of the proposed model instead of the joint likelihood. Numerical experiments on benchmark datasets illustrate the robustness of the proposed approach. In particular, comparison to state-of-the-art methods shows that our approach introduces a significantly smaller decrease in performance when the proportion of missing labels is increased.

We consider the problem of designing a robust classifier in the presence of an adversary who aims to degrade classification performance by elaborately falsifying the test instance. We propose a model-agnostic defense approach wherein the true class label of the falsified instance is inferred by analyzing its proximity to each class as measured based on class-conditional data distributions. We present a k-nearest neighbors type approach to perform a sample-based approximation of the aforementioned probabilistic proximity analysis. The proposed approach is evaluated on three different real-world datasets in a game-theoretic setting, in which the adversary is assumed to optimize the attack design against the employed defense approach. In the game-theoretic evaluation, the proposed defense approach significantly outperforms benchmarks in various attack scenarios, demonstrating its efficacy against optimally designed attacks.

Factorization-based gradient descent is a scalable and efficient algorithm for solving low-rank matrix completion. Recent progress in structured non-convex optimization has offered global convergence guarantees for gradient descent under certain statistical assumptions on the low-rank matrix and the sampling set. However, while the theory suggests gradient descent enjoys fast linear convergence to a global solution of the problem, the universal nature of the bounding technique prevents it from obtaining an accurate estimate of the rate of convergence. This paper performs a local analysis of the exact linear convergence rate of gradient descent for factorization-based symmetric matrix completion. Without any additional assumptions on the underlying model, we identify the deterministic condition for local convergence guarantee for gradient descent, which depends only on the solution matrix and the sampling set. More crucially, our analysis provides a closed-form expression of the asymptotic rate of convergence that matches exactly with the linear convergence observed in practice. To the best of our knowledge, our result is the first one that offers the exact linear convergence rate of gradient descent for matrix factorization in Euclidean space for matrix completion.

The hyperspectral unmixing problem arises in remote sensing, chemometrics, and biomedical engineering applications. The spectral signature of a single pixel in a hyperspectral cube can be represented as a non-negative combination of non-negative signatures from various materials contained in the physical region corresponding to the pixel (linear mixing). A less studied problem is associated with foreground extraction in an intimate (nonlinear) mixing model. We introduce a framework for foreground signature extraction based on a proposed patch model. We introduce identifiability conditions for the single and multiple patch cases. Using these conditions, we present an algorithm for the identifiable recovery of foreground signatures. Numerical experiments on real and synthetic data illustrate the efficacy of the proposed approach.

The problem of making the classifier design resilient to test data falsification is considered. In the literature, a few countermeasures have been proposed to defend machine learning algorithms against test data falsification, but a common assumption employed therein is that feature entries of test data are equally vulnerable to falsification. When test data entries consist of data collected from various sources such as different types of sensor devices, vulnerability levels of data entries to falsification attacks can differ significantly depending on how data creation and transmission procedures are secured. In this paper, we present an attack-cost-aware adversarial learning framework that takes into account the (potentially inhomogeneous) vulnerability characteristics of test data entries in designing an attack-resilient classifier. We demonstrate the efficacy of the proposed approach using experiments with the MNIST handwritten digit database.

Histopathological image analysis is a challenging task due to a diverse histology feature set as well as due to the presence of large non-informative regions in whole slide images. In this paper, we propose a multiple-instance learning (MIL) method for image-level classification as well as for annotating relevant regions in the image. In MIL, a common assumption is that negative bags contain only negative instances while positive bags contain one or more positive instances. This asymmetric assumption may be inappropriate for some application scenarios where negative bags also contain representative negative instances. We introduce a novel symmetric MIL framework associating each instance in a bag with an attribute which can be either negative, positive, or irrelevant. We extend the notion of relevance by introducing control over the number of relevant instances. We develop a probabilistic graphical model that incorporates the aforementioned paradigm and a corresponding computationally efficient inference for learning the model parameters and obtaining an instance level attribute-learning classifier. The effectiveness of the proposed method is evaluated on available histopathology datasets with promising results.

This paper introduces the use of adaptive restart to accelerate iterative hard thresholding (IHT) for low-rank matrix completion. First, we analyze the local convergence of accelerated IHT in the non-convex setting of matrix completion problem (MCP). We prove the linear convergence rate of the accelerated algorithm inside the region near the solution. Our analysis poses a major challenge to parameter selection for accelerated IHT when no prior knowledge of the "local Hessian condition number" is given. To address this issue, we propose a simple adaptive restart algorithm for MCP to recover the optimal rate of convergence at the solution, as motivated in [1]. Our numerical result verifies the theoretical analysis as well as demonstrates the outstanding performance of the proposed algorithm.

We present a momentum-based accelerated iterative hard thresholding (IHT) for low-rank matrix completion. We analyze the convergence of the proposed Heavy Ball (HB) accelerated IHT near the solution and provide optimal step size parameters that guarantee the fastest rate of convergence. Since the optimal step sizes depend on the unknown structure of the solution matrix, we further propose a heuristic for parameter selection that is inspired by recent results in random matrix theory. Our experiment on a simple matrix completion setting verifies our analysis and illustrates the competitive rate of convergence that can be obtained with the proposed algorithm.

Clustering is widely used for exploratory data analysis in a variety of applications. Traditionally clustering is studied as an unsupervised task where no human inputs are provided. A recent trend in clustering is to leverage user provided side information to better infer the clustering structure in data. In this paper, we propose a probabilistic graphical model that allows user to provide as input the desired cluster sizes, namely the cardinality constraints. Our model also incorporates a flexible mechanism to inject control of the crispness of the clusters. Experiments on synthetic and real data demonstrate the effectiveness of the proposed method in learning with cardinality constraints in comparison with the current state-of-the-art.

Multiple-instance learning is a framework for learning from data consisting of bags of instances labeled at the bag level. A common assumption in multi-instance learning is that a bag label is positive if and only if at least one instance in the bag is positive. In practice, this assumption may be violated. For example, experts may provide a noisy label to a bag consisting of many instances, to reduce labeling time. Here, we consider generalized multi-instance learning, which assumes that the bag label is non-deterministically determined based on the number of positive instances in the bag. The challenge in this setting is to simultaneous learn an instance classifier and the unknown bag-labeling probabilistic rule. This paper addresses the generalized multi-instance learning using a discriminative probabilistic graphical model with exact and efficient inference. Experiments on both synthetic and real data illustrate the effectiveness of the proposed method relative to other methods including those that follow the traditional multiple-instance learning assumption.

Exploiting hierarchical label structure for multi-label classification can significantly improve classification performance and also benefit the labeling process. Existing work either can not make use of such structure or assume the hierarchy is given as a prior. In practice, such hierarchy is not always available beforehand and it is desirable to learn it from data. Moreover, the labels in the training data may be incomplete due to inconsistent labeling process, which raises another learning challenge. This paper studies multi-label learning with a latent label hierarchy and incomplete label assignments. Our goal is to simultaneously learn the hierarchy as well as a multi-label classifier given the input features and incomplete label assignments. We propose a probabilistic model that captures the hierarchical structure and the incompleteness of the labels and introduce an Expectation-Maximization (EM) procedure for maximum likelihood estimation.

We study sparse gross error correction for state estimation in a non-linear sensing system. We consider a practical assumption that gross errors are sparse, and their locations tend to be invariant over a few consecutive measurement periods. Under the assumption, a robust state estimation and error correction algorithm using multiple measurement vectors is proposed based on local linear approximation of the nonlinear measurement model. Unlike existing approaches in the literature, the proposed method ensures that the estimated gross error locations are such that system is observable, i.e., the system state is uniquely identifiable. The proposed method was applied for power system AC state estimation of the IEEE 14-bus network and outperformed benchmark techniques.

In bioacoustics, automatic animal voice detection and recognition from audio recordings is an emerging topic for animal preservation. Our research focuses on bird bioacoustics, where the goal is to segment bird syllables from the recording and predict the bird species for the syllables. Traditional methods for this task addresses the segmentation and species prediction separately, leading to propagated errors. This work presents a new approach that performs simultaneous segmentation and classification of bird species using a Convolutional Neural Network (CNN) with encoder-decoder architecture. Experimental results on bird recordings show significant improvement compared to recent state-of-the-art methods for both segmentation and species classification.

We present an online method to learn recurring time-frequency patterns from spectrograms. Our method relies on a convolutive decomposition that estimates sequences of spectra into time-frequency patterns and their corresponding activation signals. This method processes one spectrogram at a time such that in comparison with a batch method, the computational cost is reduced proportionally to the number of considered spectrograms. We use a first-order stochastic gradient descent and show that a monotonically decreasing learning-rate works appropriately. Furthermore, we suggest a framework to classify spectrograms based on the estimated set of time-frequency patterns. Results, on a set of synthetically generated spectrograms and a real-world dataset, show that our method finds meaningful time-frequency patterns and that it is suitable to handle a large amount of data.

Recognizing and localizing a recurring pattern is a problem with a variety of applications such as classification and localization of home appliances from their activation signals and estimating the relative alignment between records of a natural repetitive electrocardiography (ECG) signals in Bio-medical data. Most common approaches for recognizing a recurring pattern are generative and focus on discovering and capturing the characteristics of the recurring pattern. One limitation of such generative approaches is that they are more sensitive to variations of the recurring signal. In this paper, we present a discriminative approach for finding a recurring pattern and localizing it within a collection of signals. We evaluate and compare our method to a generative approach [1] on both synthetic data and real-world home appliance data.

Labeling data for classification requires significant human effort. To reduce labeling cost, instead of labeling every instance, a group of instances (bag) is labeled by a single bag label. Computer algorithms are then used to infer the label for each instance in a bag, a process referred to as instance annotation. This task is challenging due to the ambiguity regarding the instance labels. We propose a discriminative probabilistic model for the instance annotation problem and introduce an expectation maximization framework for inference, based on the maximum likelihood approach. For many probabilistic approaches, brute-force computation of the instance label posterior probability given its bag label is exponential in the number of instances in the bag. Our contribution is a dynamic programming method for computing the posterior that is linear in the number of instances. We evaluate our method using both benchmark and real world data sets, in the domain of bird song, image annotation, and activity recognition. In many cases, the proposed framework outperforms, sometimes significantly, the current state-of-the-art MIML learning methods, both in instance label prediction and bag label prediction.

We study the problem of analyzing a large volume ofbioacoustic data collected in-situ with the goal of assessingthe biodiversity of bird species at the data collectionsite. We are interested in the class discoveryproblem for this setting. Specifically, given a large collectionof audio recordings containing bird and othersounds, we aim to automatically select a fixed size subsetof the recordings for human expert labeling suchthat the maximum number of species/classes is discovered.We employ a multi-instance multi-label representationto address multiple simultaneously vocalizingbirds with sounds that overlap in time, and proposenew algorithms for species/class discovery using thisrepresentation. In a comparative study, we show that theproposed methods discover more species/classes thancurrent state-of-the-art in a real world datasetof 92,095 ten-second recordings collected in field conditions.

In this paper, we present an approach for learning in the semi-supervised setting in the presence of novel class instances. In this setting, data consists of a labeled portion and an unlabeled portion that contains novel class instances along with unlabeled known class instances. Novel class instances are instances from concepts that do not have labeled training examples. This setting is appropriate for the case in which data is abundant and labeling the entire data is prohibitively expensive. We provide a model and an inference framework that allow for a direct control over the portion of novel class instances in the unlabeled data. Experiments on synthetic data demonstrate the usefulness of the proposed approach. Comparison to state-of-the-art approaches for learning in the presence of novel class instances using unlabeled data illustrates the advantage in using the proposed method in term of accuracy.

Activity recognition from sensor data has spurred a great deal of interest due to its impact on health care. Prior work on activity recognition from multivariate time series data has mainly applied supervised learning techniques which require a high degree of annotation effort to produce training data with the start and end times of each activity. In order to reduce the annotation effort, we present a weakly supervised approach based on multi-instance learning. We introduce a generative graphical model for multi-instance learning on time series data based on an auto-regressive hidden Markov model. Our model has a number of advantages, including the ability to produce both bag and instance-level predictions as well as an efficient exact inference algorithm based on dynamic programming.

A common framework of identifying bird species from audio recordings involves detecting bird song segments, which will be subsequently input to a classifier. In-field recordings are contaminated with various environmental noise. For such recordings, supervised segmentation has been observed to outperform unsupervised energy-based approaches. Prior supervised segmentation work considers only pixel-level predictions and ignores the supervision provided at the segment-level. We propose a hierarchical approach that learns to isolate bird song syllables based on both pixel-level and segment-level information. Experimental results suggest that our method outperforms an existing supervised method that learns only from pixel-level supervision.

Multi-instance multi-label learning (MIML) is a framework for learning in the presence of label ambiguity. In MIML, experts provide labels for groups of instances (bags), instead of directly providing a label for every instance. When labeling efforts are focused on a set of target classes, instances outside this set will not be appropriately modeled. For example, ornithologists label bird audio recordings with a list of species present. Other additional sound instances, e.g., a rain drop or a moving vehicle sound, are not labeled. The challenge is due to the fact that for a given bag, the presence or absence of novel instances is latent. In this paper, this problem is addressed using a discriminative probabilistic model that accounts for novel instances. We propose an exact and efficient implementation of the maximum likelihood approach to determine the model parameters and consequently learn an instance-level classifier for all classes including the novel class. Experiments on both synthetic and real datasets illustrate the effectiveness of the proposed approach.

We consider the problem of finding the same pattern in multiple sets. This problem can be applied in a variety of signal processing and machine learning problems including DNA sequencing and detection of electrical signatures. In our problem setting, each set contains only a single unknown pattern of interest among many other patterns. To understand the performance limitations associated with this setting, we focus on the evaluation of the Cramér-Rao lower bound (CRLB). We introduce a probabilistic model for the problem. The random position of a pattern in a given set gives rise to a mixture model and consequently a non trivial CRLB analysis. We present the derivation of the CRLB for the problem and provide a numerical evaluation of the CRLB. We verify our expression for the CRLB against the mean-squared-error of an iterative implementation of the maximum likelihood estimator.

We present an inference framework for automatic detection of activations of home appliances based on voltage envelope waveforms. We cast the problem of appliance detection and recognition as an inference problem. When the activation signatures are known, the problem reduces to a simple detection problem. When the activation signatures are unknown, the problem is reformulated as a blind joint delay estimation. Due to the non-convexity of the negative log-likelihood, finding a global optimal solution is a key challenge. Here, we introduce a novel algorithm to estimate the activation templates, which is guaranteed to yield an error within a factor of two of that of the optimal solution. We apply our method to a real-world dataset consisting of voltage waveform measurements of several appliances obtained in multiple homes over a few weeks. Based on ground truth data, we present a quantitative analysis of the proposed algorithm and alternative approaches.

We consider the problem of finding unknown patterns that are recurring across multiple sets. For example, finding multiple objects that are present in multiple images or a short DNA code that is repeated across multiple DNA sequences. Earlier work on the topic includes a statistical modeling approach in which the same template is placed at a random position in multiple independent sets. Using mixture modeling, we propose an extension to the approach that allows the detection of multiple templates placed across multiple sets. Moreover, we present an expectation-maximization algorithm for jointly estimating multiple templates based on a mixture of non-Gaussian distributions. To address the non-convexity of the problem, a robust initialization method is presented and theoretical guarantees are provided. We evaluate the performance of the algorithm on both synthetic data and real-world data consisting of electrical voltage recordings of home appliance activations. Our results indicate that the proposed algorithm significantly improves the detection accuracy relative to the single pattern model.

We consider multi-view classification for the challenging scenario where, for some views, there are no labeled training examples. Several discriminative approaches have been recently proposed for special instances of this problem. Here, alternatively, we propose a generative semi-supervised mixture model across all views which, via marginalization, flexibly performs exact class inference, given any subset of available views. The proposed model is an extension of semi-supervised mixtures to a multi-view setting, as well as a semi-supervised extension of mixtures of factors analyzers (MFA)[1]. A novel EM algorithm with a computationally efficient E-step is derived for learning our multi-view model. Specialization of this formulation to the standard MFA problem also gives a reduced complexity E-step, compared to the original EM algorithm proposed for MFA. Our multi-view method is experimentally demonstrated on digit recognition using audio and lip video views, achieving competitive results with alternative, discriminative approaches.

In multi-instance multi-label (MIML) instance annotation, the goal is to learn an instance classifier while training on a MIML dataset, which consists of bags of instances paired with label sets, instance labels are not provided in the training data. The MIML formulation can be applied in many domains. For example, in an image domain, bags are images, instances are feature vectors representing segments in the images, and the label sets are lists of objects or categories present in each image. Although many MIML algorithms have been developed for predicting the label set of a new bag, only a few have been specifically designed to predict instance labels. We propose MIML-ECC (ensemble of classifier chains), which exploits bag-level context through label correlations to improve instance-level prediction accuracy. The proposed method is scalable in all dimensions of a problem (bags, instances, classes, and feature dimension), and has no parameters that require tuning (which is a problem for prior methods). In experiments on two image datasets, a bioacoustics dataset, and two artificial datasets, MIML-ECC achieves higher or comparable accuracy in comparison to several recent methods and baselines.

We present a colorimetric sensor array which is able to detect explosives such as DNT, TNT, HMX, RDX and TATP and identifying volatile organic compounds in the presence of water vapor in air. To analyze colorimetric sensors with statistical methods, a suitable representation of sensory readings is required. We present a new approach of extracting features from a colorimetric sensor array based on a color distribution representation. For each sensor in the array, we construct a K-nearest neighbor classifier based on the Hellinger distances between color distribution of a test compound and the color distribution of all the training compounds. The performance of this set of classifiers are benchmarked against a set of K-nearest neighbor classifiers that is based on traditional feature representation (e.g., mean or global mode). The suggested approach of using the entire distribution outperforms the traditional approaches which use a single feature.

Multiple measurement vector (MMV) problem addresses the recovery of a set of sparse vectors that have common sparsity pattern. In this paper, we consider a variant of the MMV problem where the common sparsity pattern is obfuscated by an additive noise. Specifically, we study the conditions for perfect reconstruction of the original sparsity pattern. Based on these, we develop a tuning-free algorithm for recovering jointly sparse solutions via the transfer optimization approach. We provide a preliminary numerical evaluation to illustrate our approach.

A multi-channel mixed-signal noise source with uniform amplitude distribution is presented. Cross-coupled, counter-propagating linear feedback shift registers are used to produce mutually independent binary distributed noises, which in turn generates mutually independent uniformly-distributed discrete-analog noises after digital-to-analog conversion. A stochastic comparator offset cancellation technique based on the proposed analog noise source is demonstrated. Applications include energy-efficient stochastic ADCs and high-density analog built-in self-test.

Multi-instance multi-label learning (MIML) is a framework for supervised classification where the objects to be classified are bags of instances associated with multiple labels. For example, an image can be represented as a bag of segments and associated with a list of objects it contains. Prior work on MIML has focused on predicting label sets for previously unseen bags. We instead consider the problem of predicting instance labels while learning from data labeled only at the bag level. We propose Rank-Loss Support Instance Machines, which optimize a regularized rank-loss objective and can be instantiated with different aggregation models connecting instance-level predictions with bag-level predictions. The aggregation models that we consider are equivalent to defining a "support instance" for each bag, which allows efficient optimization of the rank-loss objective using primal sub-gradient descent. Experiments on artificial and real-world datasets show that the proposed methods achieve higher accuracy than other loss functions used in prior work, e.g., Hamming loss, and recent work in ambiguous label classification.

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.

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.

Recent work in machine learning considers the problem of identifying bird species from an audio recording. Most methods require segmentation to isolate each syllable of bird call in input audio. Energy-based time-domain segmentation has been successfully applied to low-noise, single-bird recordings. However, audio from automated field recorders contains too much noise for such methods, so a more robust segmentation method is required. We propose a supervised time frequency audio segmentation method using a Random Forest classifier, to extract syllables of bird call from a noisy signal. When applied to a test data set of 625 field-collected audio segments, our method isolates 93.6% of the acoustic energy of bird song with a false positive rate of 8.6%, outperforming energy thresholding.

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.

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.

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 investigate the achievable throughput regions for scenarios involving prioritized transmissions. Prioritized transmissions are useful in many multimedia networking applications where the transmitted data have an inherent hierarchy such that a piece of data at one level is only useful if all the pieces of data at all the lower levels are present. Formally, the prioritized transmission refers to the notion that, given M prioritized packets in the decreasing order of importance, a1, a2, ..., amto be delivered to a receiver, then the packet aiis useful to a receiver only if it has received all packets ajwith j < i successfully. Thus, the prioritized throughput can be abstractly represented j - 1 where j is the position of the first lost packet. In this paper we investigate the achievable throughput regions of prioritized transmissions from a source to multiple receivers via a shared and lossy channel. We assume that the source is an oracle such that it knows precisely whether a packet is lost or received at any receiver in any future time slot, thus it can schedule the packet transmission in such a way to maximize the receiver throughputs. We show that using network coding technique, the achievable throughput region for the broadcast scenarios can be substantially enlarged. Furthermore, for some erasure patterns, the achievable throughput region using network coding technique is optimal in the sense that no scheme can do better.

Our goal is to automatically identify which species of bird is present in an audio recording using supervised learning. Devising effective algorithms for bird species classification is a preliminary step toward extracting useful ecological data from recordings collected in the field. We propose a probabilistic model for audio features within a short interval of time, then derive its Bayes risk-minimizing classifier, and show that it is closely approximated by a nearest-neighbor classifier using Kullback-Leibler divergence to compare histograms of features. We note that feature histograms can be viewed as points on a statistical manifold, and KL divergence approximates geodesic distances defined by the Fisher information metric on such manifolds. Motivated by this fact, we propose the use of another approximation to the Fisher information metric, namely the Hellinger metric. The proposed classifiers achieve over 90% accuracy on a data set containing six species of bird, and outperform support vector machines.

In this paper, we present new probabilistic models for identifying bird species from audio recordings. We introduce the independent syllable model and consider two ways of aggregating frame level features within a syllable. We characterize each syllable as a probability distribution of its frame level features. The independent frame independent syllable (IFIS) model allows us to distinguish syllables whose feature distributions are different from one another. The Markov chain frame independent syllable (MCFIS) model is introduced for scenarios where the temporal structure within the syllable provides significant amount of discriminative information. We derive the Bayes risk minimizing classifier for each model and show that it can be approximated as a nearest neighbour classifier. Our experiments indicate that the IFIS and MCFIS models achieve 88.26% and 90.61% correct classification rates, respectively, while the equivalent SVM implementation achieves 86.15%.

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.

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.

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

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.

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

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

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 components used in communication systems are nonlinear and have a peak power or peak amplitude constraint. Nonlinearity generates distortions and thus signal-to-noise-and-distortion ratio (SNDR) is an appropriate performance measure. In this paper, we are interested in finding the nonlinear mapping that maximizes the SNDR subject to the peak amplitude constraint. The answer is a soft limiter with gain calculated based on the noise power and the probability density function of the input amplitude. We also investigate a bounding relationship between the SNDR and capacity of the nonlinear channel. The results of this paper can be applied for efficient transmission of high peak-to-average power ratio signals or for optimal linearization of nonlinear devices.

In this paper, we propose a baseband nonlinear transformation technique to improve the overall communication system performance, under the peak power constraint. A closed-form expression is derived for the signal-to-noise-and-distortion ratio (SNDR) of certain nonlinear transformations. A strategy for SNR-adaptive optimum clipping is proposed. For orthogonal frequency division multiplexing (OFDM), we show that the optimal clipping ratio leads to an SNDR improvement of 5-7 dB and accompanying decrease in symbol-error-rate. By applying an iterative symbol detection and clipping noise mitigation algorithm at the receiver, we demonstrate that clipping in OFDM can lead to large performance gains.

When a non-constant envelope signal goes through a nonlinear power amplifier, spectral regrowth (broadening) appears at the output of the power amplifier. To satisfy regulatory requirements on out-of-band emissions, spectral regrowth must be contained. We derive a novel closed-form expression for the output power spectral density when the power amplifier is quasi-memoryless and cyclostationarity of the digitally modulated input is taken into account. We compare our results with the conventional analysis where stationary input is assumed. We emphasize the importance of paying attention to the cyclostationary nature of the input when excess bandwidth is present.

The polynomial model is commonly used in predistorter design. However, the conventional polynomial model exhibits numerical instabilities when high-order terms are included. We introduce a novel set of orthogonal polynomial basis functions for predistorter modeling. Theoretically, the conventional and the orthogonal polynomial models are "equivalent", and thus should have the same performance. In practice, however, the two approaches can perform quite differently in the presence of quantization noise and with finite precision processing. Simulation results show that the orthogonal polynomials can alleviate the numerical instability problem associated with the conventional polynomials and generally yield better predistortion linearization performance.

Power amplifiers (PAs) are inherently nonlinear devices and are used in virtually all communications systems. Digital baseband predistortion is a highly cost effective way to linearize the PAs, but most existing architectures assume that the PA has a memoryless nonlinearity. For wider bandwidth applications such as WCDMA, PA memory effects can no longer be ignored, and memoryless predistortion has limited effectiveness. In this paper, we model the PA as a Wiener system and construct a Hammerstein predistorter, obtained using an indirect learning architecture. Linearization performance is demonstrated on a 3-carrier UMTS signal.

A comparison is made between the spectral regrowth of quadrature phase shift keyed (QPSK) and offset QPSK (OQPSK) signals as they go through nonlinear amplifications. Contrary to existing approaches that assume the power amplifier input is Gaussian, our analysis is carried out without the Gaussian assumption, by using higher-order statistics. We show that it is possible to assess quantitatively whether and how much OQPSK is beneficial in reducing spectral regrowth. Simple closed form formulas are obtained when the pulse shape filter is time-limited. A particular measure of spectral broadening is also provided.

The problem of using antenna array measurements to estimate the bearing of a mobile communications user surrounded by local scatterers is considered. The concept of "partial coherence" is introduced to account for the temporal as well as spatial correlation effects often encountered in mobile radio propagation channels. A simple, intuitive parametric model for temporal channel correlation is presented. The result is an overall spatio-temporal channel model which is more realistic than formerly proposed models (which assume either full or zero temporal channel correlation). Thus, previously posed bearing estimation problems for a "distributed" or "scattered" source are generalized to a joint spatio-temporal parameter estimation problem. A study of the associated Cramer-Rao Bound for the case of known transmitted signal of constant modulus indicates that the inherent accuracy limitations associated with this generalized problem lie somewhere between the cases of zero and full temporal correlation and become more severe as temporal channel correlation increases.