We consider synthesis and analysis of probability measures using the entropy-regularized Wasserstein-2 cost and its unbiased version, the Sinkhorn divergence. The synthesis problem consists of computing the barycenter, with respect to these costs, of reference measures given a set of coefficients belonging to the simplex. The analysis problem consists of finding the coefficients for the closest barycenter in the Wasserstein-2 distance to a given measure. Under the weakest assumptions on the measures thus far in the literature, we compute the derivative of the entropy-regularized Wasserstein-2 cost. We leverage this to establish a characterization of barycenters with respect to the entropy-regularized Wasserstein-2 cost as solutions that correspond to a fixed point of an average of the entropy-regularized displacement maps. This characterization yields a finite-dimensional, convex, quadratic program for solving the analysis problem when the measure being analyzed is a barycenter with respect to the entropy-regularized Wasserstein-2 cost. We show that these coefficients, as well as the value of the barycenter functional, can be estimated from samples with dimension-independent rates of convergence, and that barycentric coefficients are stable with respect to perturbations in the Wasserstein-2 metric. We employ the barycentric coefficients as features for classification of corrupted point cloud data, and show that compared to neural network baselines, our approach is more efficient in small training data regimes.

We propose the linear barycentric coding model (LBCM) which utilizes the linear optimal transport (LOT) metric for analysis and synthesis of probability measures. We provide a closed-form solution to the variational problem characterizing the probability measures in the LBCM and establish equivalence of the LBCM to the set of 2-Wasserstein barycenters in the special case of compatible measures. Computational methods for synthesizing and analyzing measures in the LBCM are developed with finite sample guarantees. One of our main theoretical contributions is to identify an LBCM, expressed in terms of a simple family, which is sufficient to express all probability measures on the closed unit interval. We show that a natural analogous construction of an LBCM in 2 dimensions fails, and we leave it as an open problem to identify the proper extension in more than 1 dimension. We conclude by demonstrating the utility of LBCM for covariance estimation and data imputation.

Recent research shows that large language models (LLMs) are vulnerable to hijacking attacks under the scenario of in-context learning (ICL) where LLMs demonstrate impressive capabilities in performing tasks by conditioning on a sequence of in-context examples (ICEs) (i.e., prompts with task-specific input-output pairs). Adversaries can manipulate the provided ICEs to steer the model toward attacker-specified outputs, effectively ''hijacking'' the model's decision-making process. Unlike traditional adversarial attacks targeting single inputs, hijacking attacks in LLMs aim to subtly manipulate the initial few examples to influence the model's behavior across a range of subsequent inputs, which requires distributed and stealthy perturbations. However, existing approaches overlook how to effectively allocate the perturbation budget across ICEs. We argue that fixed budgets miss the potential of dynamic reallocation to improve attack success while maintaining high stealthiness and text quality. In this paper, we propose BAM-ICL, a novel **b**udgeted **a**dversarial **m**anipulation hijacking attack framework for in-context learning. We also consider a more practical yet stringent scenario where ICEs arrive sequentially and only the current ICE can be perturbed. BAM-ICL mainly consists of two stages: In the offline stage, where we assume the adversary has access to data drawn from the same distribution as the target task, we develop a global gradient-based attack to learn optimal budget allocations across ICEs. In the online stage, where ICEs arrive sequentially, perturbations are generated progressively according to the learned budget profile. We evaluate BAM-ICL on diverse LLMs and datasets. The experimental results demonstrate that it achieves superior attack success rates and stealthiness, and the adversarial ICEs are highly transferable to other models.

In typical medical image classification problems, labeled data is scarce while unlabeled data is more available. Semi-supervised learning and self-supervised learning are two different research directions that can improve accuracy by learning from extra unlabeled data. Recent methods from both directions have reported significant gains on traditional benchmarks. Yet past benchmarks do not focus on medical tasks and rarely compare self- and semi- methods together on an equal footing. Furthermore, past benchmarks often handle hyperparameter tuning suboptimally. First, they may not tune hyperparameters at all, leading to underfitting. Second, when tuning does occur, it often unrealistically uses a labeled validation set that is much larger than the training set. Therefore currently published rankings might not always corroborate with their practical utility This study contributes a systematic evaluation of self- and semi- methods with a unified experimental protocol intended to guide a practitioner with scarce overall labeled data and a limited compute budget. We answer two key questions: Can hyperparameter tuning be effective with realistic-sized validation sets? If so, when all methods are tuned well, which self- or semi-supervised methods achieve the best accuracy? Our study compares 13 representative semi- and self-supervised methods to strong labeled-set-only baselines on 4 medical datasets. From 20000+ GPU hours of computation, we provide valuable best practices to resource-constrained practitioners: hy-perparameter tuning is effective, and the semi-supervised method known as MixMatch delivers the most reliable gains across 4 datasets.

Through minimization of an appropriate loss function such as the InfoNCE loss, contrastive learning (CL) learns a useful representation function by pulling positive samples close to each other while pushing negative samples far apart in the embedding space. The positive samples are typically created using "label-preserving" augmentations, i.e., domain-specific transformations of a given datum or anchor. In absence of class information, in unsupervised CL (UCL), the negative samples are typically chosen randomly and independently of the anchor from a preset negative sampling distribution over the entire dataset. This leads to class-collisions in UCL. Supervised CL (SCL), avoids this class collision by conditioning the negative sampling distribution to samples having labels different from that of the anchor. In hard-UCL (H-UCL), which has been shown to be an effective method to further enhance UCL, the negative sampling distribution is conditionally tilted, by means of a hardening function, towards samples that are closer to the anchor. Motivated by this, in this paper we propose hard-SCL (H-SCL) wherein the class conditional negative sampling distribution is tilted via a hardening function. Our simulation results confirm the utility of H-SCL over SCL with significant performance gains in downstream classification tasks. Analytically, we show that in the limit of infinite negative samples per anchor and a suitable assumption, the H-SCL loss is upper bounded by the H-UCL loss, thereby justifying the utility of H-UCL for controlling the H-SCL loss in the absence of label information. Through experiments on several datasets, we verify the assumption as well as the claimed inequality between H-UCL and H-SCL losses. We also provide a plausible scenario where H-SCL loss is lower bounded by UCL loss, indicating the limited utility of UCL in controlling the H-SCL loss.1

This paper considers the use of recently proposed optimal transport-based multivariate goodness-of-fit (GoF) test statistics, namely rank energy and its variant the soft rank energy derived from entropy-regularized optimal transport, for unsupervised non-parametric change point detection (CPD) in multivariate time series data. We show that the soft rank energy enjoys both fast rates of statistical convergence and robust continuity properties which lead to strong performance on real datasets. Our analyses remove the need for resampling and out-of-sample extensions previously required to obtain such rates. Our theoretical results show that the rank energy suffers from the curse of dimensionality in statistical estimation and moreover can signal a change point from arbitrarily small perturbations, which leads to a high rate of false alarms in CPD. Additionally, under mild regularity conditions, we quantify the discrepancy between soft rank energy and rank energy in terms of the regularization parameter. Finally, we show our approach performs favorably in numerical experiments compared to several other optimal transport-based methods as well as maximum mean discrepancy (MMD), which is a popular multivariate GoF statistic.

Domain generalization aims to learn a model with good generalization ability, that is, the learned model should not only perform well on several seen domains but also on unseen domains with different data distributions. State-of-the-art domain generalization methods typically train a representation function followed by a classifier jointly to minimize both the classification risk and the domain discrepancy. However, when it comes to model selection, most of these methods rely on traditional validation routines that select models solely based on the lowest classification risk on the validation set. In this paper, we theoretically demonstrate a trade-off between minimizing classification risk and mitigating domain discrepancy, i.e., it is impossible to achieve the minimum of these two objectives simultaneously. Motivated by this theoretical result, we propose a novel model selection method suggesting that the validation process should account for both the classification risk and the domain discrepancy. We validate the effectiveness of the proposed method by numerical results on several domain generalization datasets.

We study the problem of designing hard negative sampling distributions for unsupervised contrastive representation learning. We propose and analyze a novel min-max framework that seeks a representation which minimizes the maximum (worst-case) generalized contrastive learning loss over all couplings (joint distributions between positive and negative samples subject to marginal constraints) and prove that the resulting min-max optimum representation will be degenerate. This provides the first theoretical justification for incorporating additional regularization constraints on the couplings. We re-interpret the min-max problem through the lens of Optimal Transport (OT) theory and utilize regularized transport couplings to control the degree of hardness of negative examples. Through experiments we demonstrate that the negative samples generated from our designed negative distribution are more similar to the anchor than those generated from the baseline negative distribution. We also demonstrate that entropic regularization yields negative sampling distributions with parametric form similar to that in a recent state-of-the-art negative sampling design and has similar performance in multiple datasets. Utilizing the uncovered connection with OT, we propose a new ground cost for designing the negative distribution and show improved performance of the learned representation on downstream tasks compared to the representation learned when using squared Euclidean cost.11Our code is publicly available at https://github.com/rjiang03/HCL-OT.

The framework of optimal transport has been leveraged to extend the notion of rank to the multivariate setting as corresponding to an optimal transport map, while preserving desirable properties of the resulting goodness-of-fit (GoF) statistics. In particular, the rank energy (RE) and rank maximum mean discrepancy (RMMD) are distribution-free under the null, exhibit high power in statistical testing, and are robust to outliers. In this paper, we point to and alleviate some of the shortcomings of these GoF statistics that are of practical significance, namely high computational cost, curse of dimensionality in statistical sample complexity, and lack of differentiability with respect to the data. We show that all these issues are addressed by defining multivariate rank as an entropic transport map derived from the entropic regularization of the optimal transport problem, which we refer to as the soft rank. We consequently propose two new statistics, the soft rank energy (sRE) and soft rank maximum mean discrepancy (sRMMD). Given n sample data points, we provide non-asymptotic convergence rates for the sample estimate of the entropic transport map to its population version that are essentially of the order n^(-1/2) when the source measure is subgaussian and the target measure has compact support. This result is novel compared to existing results which achieve a rate of n^(-1) but crucially rely on both measures having compact support. In contrast, the corresponding convergence rate of estimating an optimal transport map, and hence the rank map, is exponential in the data dimension. We leverage these fast convergence rates to show that the sample estimates of sRE and sRMMD converge rapidly to their population versions. Combined with the computational efficiency of methods in solving the entropy-regularized optimal transport problem, these results enable efficient rank-based GoF statistical computation, even in high dimensions. Furthermore, the sample estimates of sRE and sRMMD are differentiable with respect to the data and amenable to popular machine learning frameworks that rely on gradient methods. We leverage these properties towards showcasing their utility for generative modeling on two important problems: image generation and generating valid knockoffs for controlled feature selection.

The unlabeled sensing problem is to solve a noisy linear system of equations under unknown permutation of the measurements. We study a particular case of the problem where the permutations are restricted to be r-local, i.e. the permutation matrix is block diagonal with r×r blocks. Assuming a Gaussian measurement matrix, we argue that the r-local permutation model is more challenging compared to a recent sparse permutation model. We propose a proximal alternating minimization algorithm for the general unlabeled sensing problem that provably converges to a first order stationary point. Applied to the r-local model, we show that the resulting algorithm is efficient. We validate the algorithm on synthetic and real datasets. We also formulate the 1-d unassigned distance geometry problem as an unlabeled sensing problem with a structured measurement matrix.

Assessing the cognitive workload of human interactants in mixed-initiative teams is a critical capability for autonomous interactive systems to enable adaptations that improve team performance. Yet, it is still unclear, due to diverging evidence, which sensing modality might work best for the determination of human workload. In this paper, we report results from an empirical study that was designed to answer this question by collecting eye gaze and electroencephalogram (EEG) data from human subjects performing an interactive multi-modal driving task. Different levels of cognitive workload were generated by introducing secondary tasks like dialogue, braking events, and tactile stimulation in the course of driving. Our results show that pupil diameter is a more reliable indicator for workload prediction than EEG. And more importantly, none of the five different machine learning models combining the extracted EEG and pupil diameter features were able to show any improvement in workload classification over eye gaze alone, suggesting that eye gaze is a sufficient modality for assessing human cognitive workload in interactive, multi-modal, multi-task settings.

This paper considers the problem of measure estimation under the barycentric coding model (BCM), in which an unknown measure is assumed to belong to the set of Wasserstein-2 barycenters of a finite set of known measures. Estimating a measure under this model is equivalent to estimating the unknown barycentric coordinates. We provide novel geometrical, statistical, and computational insights for measure estimation under the BCM, consisting of three main results. Our first main result leverages the Riemannian geometry of Wasserstein-2 space to provide a procedure for recovering the barycentric coordinates as the solution to a quadratic optimization problem assuming access to the true reference measures. The essential geometric insight is that the parameters of this quadratic problem are determined by inner products between the optimal displacement maps from the given measure to the reference measures defining the BCM. Our second main result then establishes an algorithm for solving for the coordinates in the BCM when all the measures are observed empirically via i.i.d. samples. We prove precise rates of convergence for this algorithm—determined by the smoothness of the underlying measures and their dimensionality—thereby guaranteeing its statistical consistency. Finally, we demonstrate the utility of the BCM and associated estimation procedures in three application areas: (i) covariance estimation for Gaussian measures; (ii) image processing; and (iii) natural language processing.

We pursue tractable Bayesian analysis of generalized linear models (GLMs) for categorical data. GLMs have been difficult to scale to more than a few dozen categories due to non-conjugacy or strong posterior dependencies when using conjugate auxiliary variable methods. We define a new class of GLMs for categorical data called categorical-from-binary (CB) models. Each CB model has a likelihood that is bounded by the product of binary likelihoods, suggesting a natural posterior approximation. This approximation makes inference straightforward and fast; using well-known auxiliary variables for probit or logistic regression, the product of binary models admits conjugate closed-form variational inference that is embarrassingly parallel across categories and invariant to category ordering. Moreover, an independent binary model simultaneously approximates multiple CB models. Bayesian model averaging over these can improve the quality of the approximation for any given dataset. We show that our approach scales to thousands of categories, outperforming posterior estimation competitors like Automatic Differentiation Variational Inference (ADVI) and No U-Turn Sampling (NUTS) in the time required to achieve fixed prediction quality.

Domain generalization (DG) is a branch of transfer learning that aims to train the learning models on several seen domains and subsequently apply these pre-trained models to other unseen (unknown but related) domains. To deal with challenging settings in DG where both data and label of the unseen domain are not available at training time, the most common approach is to design the classifiers based on the domain-invariant representation features, i.e., the latent representations that are unchanged and transferable between domains. Contrary to popular belief, we show that designing classifiers based on invariant representation features alone is necessary but insufficient in DG. Our analysis indicates the necessity of imposing a constraint on the reconstruction loss induced by representation functions to preserve most of the relevant information about the label in the latent space. More importantly, we point out the trade-off between minimizing the reconstruction loss and achieving domain alignment in DG. Our theoretical results motivate a new DG framework that jointly optimizes the reconstruction loss and the domain discrepancy. Both theoretical and numerical results are provided to justify our approach.

Invariance-principle-based methods such as Invariant Risk Minimization (IRM), have recently emerged as promising approaches for Domain Generalization (DG). Despite promising theory, such approaches fail in common classification tasks due to mixing of true invariant features and spurious invariant features1. To address this, we propose a framework based on the conditional entropy minimization (CEM) principle to filter-out the spurious invariant features leading to a new algorithm with a better generalization capability. We show that our proposed approach is closely related to the well-known Information Bottleneck (IB) framework and prove that under certain assumptions, entropy minimization can exactly recover the true invariant features. Our approach provides competitive classification accuracy compared to recent theoretically-principled state-of-the-art alternatives across several DG datasets.

In several applications, including imaging of deformable objects while in motion, simultaneous localization and mapping, and unlabeled sensing, we encounter the problem of recovering a signal that is measured subject to unknown permutations. In this paper we take a fresh look at this problem through the lens of optimal transport (OT). In particular, we recognize that in most practical applications the unknown permutations are not arbitrary but some are more likely to occur than others. We exploit this by introducing a regularization function that promotes the more likely permutations in the solution. We show that, even though the general problem is not convex, an appropriate relaxation of the resulting regularized problem allows us to exploit the well-developed machinery of OT and develop a tractable algorithm.

Robust machine learning formulations have emerged to address the prevalent vulnerability of deep neural networks to adversarial examples. Our work draws the connection between optimal robust learning and the privacy-utility tradeoff problem, which is a generalization of the rate-distortion problem. The saddle point of the game between a robust classifier and an adversarial perturbation can be found via the solution of a maximum conditional entropy problem. This information-theoretic perspective sheds light on the fundamental tradeoff between robustness and clean data performance, which ultimately arises from the geometric structure of the underlying data distribution and perturbation constraints.

Adversarial examples have recently exposed the severe vulnerability of neural network models. However, most of the existing attacks require some form of target model information (i.e., weights/model inquiry/architecture) to improve the efficacy of the attack. We leverage the information-theoretic connections between robust learning and generalized rate-distortion theory to formulate a universal adversarial example (UAE) generation algorithm. Our algorithm trains an offline adversarial generator to minimize the mutual information between the label and perturbed data. At the inference phase, our UAE method can efficiently generate effective adversarial examples without high computation cost. These adversarial examples in turn allow for developing universal defenses through adversarial training. Our experiments demonstrate promising gains in improving the training efficiency of conventional adversarial training.

Many time series can be modeled as a sequence of segments representing high-level discrete states, such as running and walking in a human activity application. Flexible models should describe the system state and observations in stationary ``pure-state'' periods as well as transition periods between adjacent segments, such as a gradual slowdown between running and walking. However, most prior work assumes instantaneous transitions between pure discrete states. We propose a dynamical Wasserstein barycentric (DWB) model that estimates the system state over time as well as the data-generating distributions of pure states in an unsupervised manner. Our model assumes each pure state generates data from a multivariate normal distribution, and characterizes transitions between states via displacement-interpolation specified by the Wasserstein barycenter. The system state is represented by a barycentric weight vector which evolves over time via a random walk on the simplex. Parameter learning leverages the natural Riemannian geometry of Gaussian distributions under the Wasserstein distance, which leads to improved convergence speeds. Experiments on several human activity datasets show that our proposed DWB model accurately learns the generating distribution of pure states while improving state estimation for transition periods compared to the commonly used linear interpolation mixture models.

Two common problems in time series analysis are the decomposition of the data stream into disjoint segments that are each in some sense "homogeneous" - a problem known as Change Point Detection (CPD) - and the grouping of similar nonadjacent segments, a problem that we call Time Series Segment Clustering (TSSC). Building upon recent theoretical advances characterizing the limiting distribution-free behavior of the Wasserstein two-sample test (Ramdas et al. 2015), we propose a novel algorithm for unsupervised, distribution-free CPD which is amenable to both offline and online settings. We also introduce a method to mitigate false positives in CPD and address TSSC by using the Wasserstein distance between the detected segments to build an affinity matrix to which we apply spectral clustering. Results on both synthetic and real data sets show the benefits of the approach.

In this paper, we study the problem of learning compact (low-dimensional) representations for sequential data that captures its implicit spatio-temporal cues. To maximize extraction of such informative cues from the data, we set the problem within the context of contrastive representation learning and to that end propose a novel objective via optimal transport. Specifically, our formulation seeks a low-dimensional subspace representation of the data that jointly (i) maximizes the distance of the data (embedded in this subspace) from an adversarial data distribution under the optimal transport, a.k.a. the Wasserstein distance, (ii) captures the temporal order, and (iii) minimizes the data distortion. To generate the adversarial distribution, we propose a novel framework connecting Wasserstein GANs with a classifier, allowing a principled mechanism for producing good negative distributions for contrastive learning, which is currently a challenging problem. Our full objective is cast as a subspace learning problem on the Grassmann manifold and solved via Riemannian optimization. To empirically study our formulation, we provide experiments on the task of human action recognition in video sequences. Our results demonstrate competitive performance against challenging baselines.

We consider the problem of incentivization and optimal control of autonomous vehicles for improving traffic congestion. In our scenario, autonomous vehicles must be incentivized in order to participate in traffic improvement. Using the theory and methods of optimal transport, we propose a constrained optimization framework over dynamics governed by partial differential equations, so that we can optimally select a portion of vehicles to be incentivized and controlled. The goal of the optimization is to obtain a uniform distribution of vehicles over the spatial domain. To achieve this, we consider two types of penalties on vehicle density, one is the$L^{2}$cost and the other is a multiscale-norm cost, commonly used in fluid-mixing problems. To solve this nonconvex optimization problem, we introduce a novel algorithm, which iterates between solving a convex optimization problem and propagating the flow of uncontrolled vehicles according to the Lighthill-Whitham-Richards model. We perform numerical simulations, which suggest that the optimization of the$L^{2}$cost is ineffective while optimization of the multiscale norm is effective. The results also suggest the use of a dedicated lane for this type of control in practice.

The low-tubal-rank tensor model has been recently proposed for real-world multidimensional data. In this paper, we study the low-tubal-rank tensor completion problem, i.e., to recover a third-order tensor by observing a subset of its elements selected uniformly at random. We propose a fast iterative algorithm, called Tubal-AltMin, that is inspired by a similar approach for low-rank matrix completion. The unknown low-tubal-rank tensor is represented as the product of two much smaller tensors with the low-tubal-rank property being automatically incorporated, and Tubal-AltMin alternates between estimating those two tensors using tensor least squares minimization. First, we note that tensor least squares minimization is different from its matrix counterpart and nontrivial as the circular convolution operator of the low-tubal-rank tensor model is intertwined with the sub-sampling operator. Secondly, the theoretical performance guarantee is challenging since Tubal-AltMin is iterative and nonconvex. We prove that 1) Tubal-AltMin generates a best rank-r approximate up to any predefined accuracy ε at an exponential rate, and 2) for an n × n × k tensor M with tubal-rank r ≪ n, the required sampling complexity is O((nr2kIIMIIF2log3n)/σ2rk), where σ̅rk is the rk-th singular value of the block diagonal matrix representation of M in the frequency domain, and the computational complexity is O(n2r2k3logn log(n/ε)). Finally, on both synthetic data and real-world video data, evaluation results show that compared with tensor-nuclear norm minimization using alternating direction method of multipliers (TNN-ADMM), Tubal-AltMin-Simple (a simplified implementation of Tubal-AltMin) improves the recovery error by several orders of magnitude. In experiments, Tubal-AltMin-Simple is faster than TNN-ADMM by a factor of 5 for a 200 × 200 × 20 tensor.

Real-world data sets often provide several types of information about the same set of entities, showing us how they interact from different viewpoints. These data sets are well represented by multi-view graphs, which consist of multiple edge sets across the same set of nodes. Combining multiple views improves the quality of inferences drawn from the underlying data, which has led to increased interest in developing efficient multi-view graph embedding methods. We propose an algorithm, C-RSP, that generates a common (C) embedding of a multi-view graph using Randomized Shortest Paths (RSP). This algorithm generates a dissimilarity measure between nodes by minimizing the expected cost of random walks between any two nodes across all views of the graph, in doing so encoding both the local and global structure of the graph. We test C-RSP on both real and synthetic data and show that it outperforms benchmark algorithms at embedding and clustering tasks.

Using the matrix product state (MPS) representation of the recently proposed tensor ring (TR) decompositions, in this paper we propose a TR completion algorithm, which is an alternating minimization algorithm that alternates over the factors in the MPS representation. This development is motivated in part by the success of matrix completion algorithms that alternate over the (low-rank) factors. We propose a novel initialization method and analyze the computational complexity of the TR completion algorithm. The numerical comparison between the TR completion algorithm and the existing algorithms that employ a low rank tensor train (TT) approximation for data completion shows that our method outperforms the existing ones for a variety of real computer vision settings, and thus demonstrates the improved expressive power of tensor ring as compared to tensor train.

Cellular network providers collect and use a wide variety of data for assessing the service quality experienced by their smartphone users. The data is essential for tasks ranging from event detection, problem diagnosis, impact analysis, coverage and capacity planning, load balancing, and performance optimization. For example, service quality measurements and data from drive-by tests provide useful and detailed information about different aspects of quality of service such as dropped calls due to handovers or radio interference. However, a major challenge for effective service quality management in operational setup is the presence of missing or unavailable data. Furthermore, the cellular data is inherently multidimensional, i.e. is a function of several variables such as location, device type, and time. Motivated by recent advances in handling multidimensional data, we propose to use tensor algebraic models and methods for cellular data prediction. The main idea is to model the data as a low rank tensor and use a rank constrained interpolation for data prediction. We focus on two recently proposed algebraic models employing two different notions of tensor rank. We test and compare the performance of the two approaches on real-world data sets collected from an operational cellular network and indicate the regimes in which one method is superior to the other. Based on these observations the proposed algorithm chooses the best of the two approaches using cross-validation.

In this paper, we consider tensor completion under adaptive sampling of tensor (a multidimensional array) fibers. Tensor fibers or tubes are vectors obtained by fixing all but one index of the array. This sampling is in contrast to the cases considered so far where one performs an adaptive element-wise sampling. In this context we exploit a recently proposed algebraic framework to model tensor data [1] and model the underlying data as a tensor with low tensor tubal-rank. Under this model we then present an algorithm for adaptive sampling and recovery, which is shown to be nearly optimal in terms of sampling complexity. We apply this algorithm for robust estimation of RF fingerprints for accurate indoor localization. We show the performance on real and synthetic data sets. Compared to existing methods, that are primarily based on non-adaptive matrix completion methods, adaptive tensor completion achieves significantly better performance.

Tensor robust principal component analysis (PCA) approaches have drawn considerable interests in many applications such as background subtraction, denoising, and outlier detection, etc. In this paper we propose an online tensor robust PCA where the multidimensional data (tensor) is revealed sequentially in online mode, and tensor PCA is updated based on the latest estimation and the newly collected data. Compared to the tensor robust PCA in batch mode, we significantly reduce the required memory and improve the computation efficiency. Application on fusing cloud-contaminated satellite images demonstrates that the proposed method shows superiority in both convergence speed and performance compared to the state-of-the-art approaches.

In this paper, we present a novel unsupervised method for detecting outliers in image databases, when the images are misaligned by action of transformations forming a group. The main idea is that when the aligned data lie in a low dimensional subspace, the misaligned data, assuming that the group size is small, will lie in a low dimensional group-invariant subspace. We then explicitly exploit this additional algebraic property and propose an algorithm for detecting outliers that is robust to data misalignment. We perform extensive comparison with current state of the art methods and show the superior performance of our algorithm.

In this paper we present deterministic analysis of sufficient conditions for sparse subspace clustering under missing data, when data is assumed to come from a Union of Subspaces (UoS) model. In this context we consider two cases, namely Case I when all the points are sampled at the same co-ordinates, and Case II when points are sampled at different locations. We show that results for Case I directly follow from several existing results in the literature, while results for Case II are not as straightforward and we provide a set of dual conditions under which, perfect clustering holds true. We provide extensive set of simulation results for clustering as well as completion of data under missing entries, under the UoS model. Our experimental results indicate that in contrast to the full data case, accurate clustering does not imply accurate subspace identification and completion, indicating the natural order of relative hardness of these problems.

Computational methods to engineer cellular metabolism promise to play a critical role in producing pharmaceutical, repairing defective genes, destroying cancer cells, and generating biofuels. Elementary Flux Mode (EFM) analysis is one such powerful technique that has elucidated cell growth and regulation, predicted product yield, and analyzed network robustness. EFM analysis, however, is a computationally daunting task because it requires the enumeration of all independent and stoichiometrically balanced pathways within a cellular network. We present in this paper an EFM enumeration algorithm, termed graphical EFM or gEFM. The algorithm is based on graph traversal, an approach previously assumed unsuitable for enumerating EFMs. The approach is derived from a pathway synthesis method proposed by Mavrovouniotis et al. The algorithm is described and proved correct. We apply gEFM to several networks and report runtimes in comparison with other EFM computation tools. We show how gEFM benefits from network compression. Like other EFM computational techniques, gEFM is sensitive to constraint ordering; however, we are able to demonstrate that knowledge of the underlying network structure leads to better constraint ordering. gEFM is shown to be competitive with state-of-the-art EFM computational techniques for several networks, but less so for networks with a larger number of EFMs.

Indoor localization is a supporting technology for a broadening range of pervasive wireless applications. One promising approach is to locate users with radio frequency fingerprints. However, its wide adoption in real-world systems is challenged by the time- and manpower-consuming site survey process, which builds a fingerprint databasea priorifor localization. To address this problem, we visualize the 3-D RF fingerprint data as a function of locations (x-y) and indices of access points (fingerprint), as atensorand use tensor algebraic methods for anadaptivetubal-sampling of this fingerprint space. In particular, using a recently proposed tensor algebraic framework in[1], we capture the complexity of the fingerprint space as a low-dimensional tensor-column space. In this formulation, the proposed scheme exploits adaptivity to identify reference points which are highly informative for learning this low-dimensional space. Further, under certain incoherency conditions, we prove that the proposed scheme achieves bounded recovery error and near-optimal sampling complexity. In contrast to several existing work that rely on random sampling, this paper shows that adaptivity in sampling can lead to significant improvements in localization accuracy. The approach is validated on both data generated by the ray-tracing indoor model which accounts for the floor plan and the impact of walls and the real world data. Simulation results show that, while maintaining the same localization accuracy of existing approaches, the amount of samples can be cut down by$71$percent for the high SNR case and$55$percent for the low SNR case.

In this paper we propose novel methods for completion (from limited samples) and de-noising of multilinear (tensor) data and as an application consider 3-D and 4- D (color) video data completion and de-noising. We exploit the recently proposed tensor-Singular Value Decomposition (t-SVD)[11]. Based on t-SVD, the notion of multilinear rank and a related tensor nuclear norm was proposed in [11] to characterize informational and structural complexity of multilinear data. We first show that videos with linear camera motion can be represented more efficiently using t-SVD compared to the approaches based on vectorizing or flattening of the tensors. Since efficiency in representation implies efficiency in recovery, we outline a tensor nuclear norm penalized algorithm for video completion from missing entries. Application of the proposed algorithm for video recovery from missing entries is shown to yield a superior performance over existing methods. We also consider the problem of tensor robust Principal Component Analysis (PCA) for de-noising 3-D video data from sparse random corruptions. We show superior performance of our method compared to the matrix robust PCA adapted to this setting as proposed in [4].

This paper studies distributed averaging of arbitrary vectors in the presence of network interference by casting an algebraic structure over the interference. While communicating locally with its neighbors for consensus, each agent causes an additive interference, lying on a low-dimensional subspace, in other communication links. We consider a particular case when this interference subspace depends only on the inter-ferer, referred to as uniform outgoing interference. We show that consensus is possible in a low-dimensional subspace of the initial conditions whose dimension is complimentary to the largest interference subspace across all of the agents. In this context, we derive a global information alignment and a local pre-conditioning, followed by local consensus iterations to ensure subspace consensus. We further provide the conditions under which this subspace consensus recovers the exact average. The analytical results are illustrated graphically to describe the setup and the information alignment scheme.

Nonnegative matrix factorization (NMF) has been shown to be identifiable under the separability assumption, under which all the columns(or rows) of the input data matrix belong to the convex cone generated by only a few of these columns(or rows) [1]. In real applications, however, such separability assumption is hard to satisfy. Following [4] and [5], in this paper, we look at the Linear Programming (LP) based reformulation to locate the extreme rays of the convex cone but in a noisy setting. Furthermore, in order to deal with the large scale data, we employ First-Order Methods (FOM) to mitigate the computational complexity of LP, which primarily results from a large number of constraints. We show the performance of the algorithm on real and synthetic data sets.

Wireless physiological sensors are often limited by energy consumption of the hardware. Power consumption is typically related to the amount of data being transmitted, conventionally the Nyquist rate which is twice the bandwidth of the signal. However, if the signals are sparse in a known basis, compressed sensing facilitates accurate reconstruction of data when sampled below the Nyquist rate. Thus, power consumption at the sensor node could be improved, which would allow long-term use of wireless physiological sensors. We have implemented a random sampling based compressed analog to information converter (AIC) in 90nm CMOS technology. Sufficiently sparse signals were reconstructed using the ℓ1-minimization algorithm. Here we present experimental results that demonstrate reconstruction of non-sparse signals, in this case EEG, by using an ℓ1, 2regularization algorithm exploiting group sparsity. These results demonstrate the performance achievable by physical compressed sensing AIC systems for brain computer interface applications.

This paper presents several strategies for spectral de-noising of hyperspectral images and hypercube reconstruction from a limited number of tomographic measurements. In particular we show that the non-noisy spectral data, when stacked across the spectral dimension, exhibits low-rank. On the other hand, under the same representation, the spectral noise exhibits a banded structure. Motivated by these features we show that the de-noised spectral data and the unknown spectral noise and the respective bands can be simultaneously estimated through the use of a low-rank and simultaneous sparse minimization operation without prior knowledge of the noisy bands. This result is novel for for hyperspectral imaging applications. In addition, we show that imaging for the Computed Tomography Imaging Systems (CTIS) can be improved under limited angle tomography by using low-rank penalization. For both of these cases we exploit the recent results in the theory of low-rank matrix completion using nuclear norm minimization.

Applications that require wireless wideband spectrum sensing are often limited by energy consumption of the sensing hardware. The power consumption is typically directly related to the amount of data transmitted. The emerging theory of compressed sensing provides a framework for reconstructing the sensed spectrum with fewer samples than are produced from Nyquist rate sampling. We have implemented a compressed sensing analog-to-information converter (AIC) in 90nm CMOS technology that allows complete reconstruction of a sparse spectrum consisting of discrete frequency bands. Typically, ℓ1-minimization based algorithms are used to reconstruct the original signal for compressed sensing. However, these algorithms do not perform well as signal sparsity decreases. This limitation can be mitigated by using ℓ1,2regularization based algorithms that exploit group sparsity. We present experimental results comparing the performance of both types of algorithms for reconstructing discrete frequency bands sampled with this AIC. These results demonstrate the performance achievable by physical AIC systems that utilize compressed sensing theory.

In this work we propose a novel algorithm for multiple-event localization for Hydraulic Fracture Monitoring (HFM) through the exploitation of the sparsity of the observed seismic signal when represented in a basis consisting of space time propagators. We provide explicit construction of these propagators using a forward model for wave propagation which depends non-linearly on the problem parameters - the unknown source location and mechanism of fracture, time and extent of event, and the locations of the receivers. Under fairly general assumptions and an appropriate discretization of these parameters we first build an over-complete dictionary of generalized Radon propagators and assume that the data is well represented as a linear superposition of these propagators. Exploiting this structure we propose sparsity penalized algorithms and workflow for super-resolution extraction of time overlapping multiple seismic events from single well data.

We propose a novel broadband method to extract the dispersion curves for multiple overlapping dispersive modes from borehole acoustic data. The proposed approach exploits a first order Taylor series approximation of the dispersion curve in a band around a given (center) frequency in terms of the phase and group slowness at that frequency. Under this approximation, the acoustic signal in a given band can be represented as a superposition of broadband propagators each of which is parameterized by the slowness pair above. These broadband propagators can be viewed as elements from an overcomplete dictionary representation and under the assumption that the number of modes is small compared to the size of the dictionary, it turns out that an appropriately reshaped support image of the coefficient vector synthesizing the signal (using the given dictionary representation) exhibits column sparsity. Our main contribution lies in identifying this feature and proposing a complexity regularized algorithm for support recovery with an ℓ1type simultaneous sparse penalization. Note that support recovery in this context amounts to recovery of the broadband propagators comprising the signal and hence extracting the dispersion, namely, the group and phase slownesses of the modes. We evaluate the performance of the proposed method on synthetic data with known dispersions and show its accuracy in extraction and robustness to the presence of heavy noise and strong interference from time overlapped modes.

In this paper, we derive information theoretic performance bounds to sensing and reconstruction of sparse phenomena from noisy projections. We consider two settings: output noise models where the noise enters after the projection and input noise models where the noise enters before the projection. We consider two types of distortion for reconstruction: support errors and mean-squared errors. Our goal is to relate the number of measurements, m , and SNR, to signal sparsity, k, distortion level, d, and signal dimension, n . We consider support errors in a worst-case setting. We employ different variations of Fano's inequality to derive necessary conditions on the number of measurements and SNR required for exact reconstruction. To derive sufficient conditions, we develop new insights on max-likelihood analysis based on a novel superposition property. In particular, this property implies that small support errors are the dominant error events. Consequently, our ML analysis does not suffer the conservatism of the union bound and leads to a tighter analysis of max-likelihood. These results provide order-wise tight bounds. For output noise models, we show that asymptotically an SNR of ((n)) together with (k (n/k)) measurements is necessary and sufficient for exact support recovery. Furthermore, if a small fraction of support errors can be tolerated, a constant SNR turns out to be sufficient in the linear sparsity regime. In contrast for input noise models, we show that support recovery fails if the number of measurements scales as o(n(n)/SNR), implying poor compression performance for such cases. Motivated by the fact that the worst-case setup requires significantly high SNR and substantial number of measurements for input and output noise models, we consider a Bayesian setup. To derive necessary conditions, we develop novel extensions to Fano's inequality to handle continuous domains and arbitrary distortions. We then develop a new max-likelihood analysis over the set of rate distortion quantization points to characterize tradeoffs between mean-squared distortion and the number of measurements using rate-distortion theory. We show that with constant SNR the number of measurements scales linearly with the rate-distortion function of the sparse phenomena.

A crucial task for a network of cognitive radios is to detect occupied frequency bands, to protect transmissions of primary users, and to identify spectrum holes to maximize the utilization of wasted resources. This paper is motivated by the need to account for challenging constraints that naturally arise in such applications such as channel model uncertainties and demanding sensitivity constraints of the sensing devices. We propose false discovery rate (FDR) based cooperative strategies to sense the occupancy of the spectrum. The strategies we propose could either be used to maximize bandwidth utilization or to provide guarantees on incurred interference levels. The proposed strategies are robust to significant uncertainties such as lack of CSI, fading and shadowing effects. The key idea of the paper is that the twin objectives of bandwidth utilization and interference control can significantly benefit from group testing across all channels in contrast to conventionally employed channel-by-channel detection strategy. Furthermore, it is shown that the cooperative sensing strategy significantly reduces sensitivity requirements. We quantify the effect of channel occupancy rate on the required cooperation degree for achieving a guaranteed level of primary user protection.

In this paper we present a novel framework for automatic extraction of dispersion characteristics from acoustic array data. Traditionally high resolution narrow-band array processing techniques such as Prony's polynomial method and forward backward matrix pencil method have been applied to this problem. Fundamentally these techniques extract the dispersion components frequency by frequency in the wavenumber-frequency transform domain of the array data. The dispersion curves are subsequently extracted by a supervised post processing and labelling of the extracted wavenumber estimates, making such an approach unsuitable for automated processing. Moreover, this frequency domain processing fails to exploit useful time information. In this paper we present a method that addresses both these issues. It consists in taking the continuous wavelet transform (CWT) of the array data and then applying a wide-band array processing technique based on a modified Radon transform on the resulting coefficients to extract the dispersion curve(s). The time information retained in the CWT domain is useful not only for separating the components present but also for extracting group slowness estimates. The latter help in the automated extraction of smooth dispersion curves. In this paper we will introduce this new method referred to as the exponential projected Radon transform (EPRT) in the CWT domain and limit ourselves to the analysis for the case of one dispersive mode. We will apply the method to synthetic and real data sets and compare the performance with existing methods.

This paper deals with throughput scaling laws for random ad hoc wireless networks in a rich scattering environment. We develop schemes to optimize the ratio lambda(n) of achievable network sum capacity to the sum of the point-to-point capacities of source-destinations (S-D) pairs operating in isolation. Our focus in this paper is on fixed signal-to-noise ratio (SNR) networks, i.e., networks where the worst case SNR over the S-D pairs is fixed independent of n. For such fixed SNR networks, which include fixed area networks as a special case, we show that collaborative strategies yield a scaling law of lambda(n)=Omega(1/n1/3) in contrast to multihop strategies which yield a scaling law of lambda(n)=Theta(1/radicn). While networks where worst case SNR goes to zero do not preclude the possibility of collaboration, multihop strategies achieve optimal throughput. The plausible reason is that the gains due to collaboration cannot offset the effect of vanishing receive SNR. This suggests that for fixed SNR networks, a network designer should look for network protocols that exploit collaboration

This paper describes the capacity scaling in wireless ad-hoc networks with probability error. A Rayleigh fading environment with rich scattering with a standard model of wave propagation in space is presented. The performance achieved with a decentralized implementation at the receiver clusters by using repetition coding in joint detection, thus forms a distributed MIMO architecture.

We consider the problem of classifying among a set of M hypothesis with N distributed noisy sensors. The N sensors can collaborate over a finite link-capacity network. The task is to arrive at a consensus about the event after exchanging such messages. In contrast to the conventional decentralized detection approach, wherein the bit rates for each link is explicitly constrained, our approach is based on high-rate limit perspective. We apply a variant of belief propagation as a strategy for collaboration to arrive at a solution to the distributed classification problem. We show that the message evolution can be reformulated as the evolution of a linear dynamical system, which is primarily characterized by network connectivity. It turns out that consensus is almost always reached by the sensors for any arbitrary network. We then derive conditions under which the consensus is the centralized MAP estimate and show that this is achieved with O(M log/sub 2/ N) bits.