Research

In recent work we studied the problem of reconstructing a signal from random linear unlabeled measurements, i.e., when A is a random matrix. In a novel approach to studying this problem we obtained the surprising result that given 2K unlabeled random measurements, any K-dimensional signal can be uniquely recovered with probability one. This implies that accurate reconstruction can be guaranteed with unlabeled random measurements provided an oversampling factor of 2 or higher is employed while sampling the signal. In terms of applications, the unlabeled sensing problem is related to data association problems encountered in different domains including robotics where it is appears in a method called “simultaneous localization and mapping” (SLAM), multi-target tracking applications, and in sampling signals in the presence of jitter. We are currently investigating other implications of this result and related questions such as robustness to noise and unlabeled sensing with determinisitic sensing matrices.

J. Unnikrishnan, S. Haghighatshoar and M. Vetterli, "Unlabeled Sensing with Random Linear Measurements," submitted to IEEE Transactions on Information Theory, Nov. 2015.

Sampling theory for mobile sensing

We study the sampling of spatial fields using mobile sensors. We argue that, in a mobile sensing context, the primary cost of a sampling scheme arises from the energy spent in the movement of the sensors rather than in acquiring the samples. With this vision, we introduce a new metric, called the path density, which quantifies the total distance moved by the sensors per unit spatial volume of the field being sampled. We introduce the problem of designing mobile sensor trajectories with minimal path density for efficiently sampling a bandlimited field with mobile sensors. We obtain new sampling theorems that provide necessary and sufficient conditions for sampling and reconstructing bandlimited fields on various configurations of straight line trajectories. We identify the fundamental limit to the path density of a sampling scheme for sampling on parallel lines. These results are analogous to Landau's bounds on the sampling density of a set of points for pointwise sampling of bandlimited fields. For sampling schemes on arbitrary paths, we derive non-trivial lower bounds on the path density. Focusing on signal acquisition using mobile sensors, we demonstrate that a mobile sensor can induce spatial anti-aliasing by employing a time-domain filter prior to sampling. This leads to complete suppression of aliasing along one-dimension.

Besides mobile sensing applications like citizen sensing, these results are also relevant in Magnetic Resonance Imaging (MRI) where the scanning time is proportional to the length of the scanning trajectory in the Fourier domain, and also in image coding strategies that seek to sample images along straight lines.

J. Unnikrishnan and M. Vetterli, "Sampling High-Dimensional Bandlimited Fields on Low-Dimensional Manifolds" IEEE Transactions on Information Theory, 2013.

J. Unnikrishnan and M. Vetterli,  "Sampling and Reconstruction of Spatial Fields using Mobile Sensors"  IEEE Transactions on Signal Processing,  2013 .

K. Gröchenig, J. L. Romero, J. Unnikrishnan, and Martin Vetterli, "On Minimal Trajectories for Mobile Sampling of Bandlimited Fields" submitted to Applied and Computational Harmonic Analysis, Dec. 2013.

De-anonymization of private data by matching statistics

In some applications, such as surveys and crowd-sourcing, the information of interest is contained within the statistics of users' data, rather than in the data itself. We analyze the vulnerability of anonymized summary statistics in the form of histograms to de-anonymization attacks that make use of auxiliary information about the users' statistics. Studying this as a hypothesis testing problem, we derive an asymptotically optimal de-anonymization procedure for matching the anonymized histograms of the users to auxiliary observations from an independent experiment. Results from the experimental evaluation of our method suggest that anonymized statistical data from a wide range of datasets, including location statistics, call data statistics, and browsing history statistics, can be easily de-anonymized in the presence of independent auxiliary statistical information. The matching algorithm can also be used as a data analytics tool in applications such as matching of user-profiles across two different websites.

J. Unnikrishnan and F. M. Naini, " De-anonymizing Private Data by Matching Statistics" presented at Allerton Conference on Communication, Control, and Computing, 2013.

J. Unnikrishnan, "Asymptotically Optimal Matching of Observation Sequences to Source Distributions and Training Sequences" submitted to  IEEE Transactions on Information Theory. Revised July 2014.   [pdf]

Privacy-enhancement via exploitation of inter-user cooperation

We argue that, in a multi-user data processing system, trust among users can be exploited to enhance the privacy of users’ data. We consider a system in which each user has a set of users with whom she is willing to trust her information. Under this model, we introduce a novel low-complexity differentially private function computation scheme that leads to a significant improvement in the tradeoff between the privacy guaranteed to the users and the accuracy of the computation. Our solution is based on a novel scheme to partition users in a social network, modeled by a graph, into circles of trust.

A social network partitioned into circles of trust

F. M. Naini, J. Unnikrishnan, P. Thiran and M. Vetterli, "Privacy-Preserving Function Computation by Exploitation of Friendships in Social Networks" to be presented at ICASSP, Florence, Italy, 2014. 

Thresholds for asymptotically optimal hypothesis tests

In recent years solutions to various hypothesis testing problems in the asymptotic setting have been proposed using results from large deviations theory. Such tests are optimal in terms of appropriately  defined error-exponents. For the practitioner, however, error probabilities in the finite sample size setting are more important. In this paper we show how results on weak convergence of the test statistic can be used to obtain better approximations for the error probabilities in the finite sample size setting. While this technique is popular among statisticians for common tests, we demonstrate its applicability for several recently proposed asymptotically optimal tests, including tests for robust goodness of fit, homogeneity tests, outlier hypothesis testing, and graphical model estimation.

J. Unnikrishnan and D. Huang, "Weak Convergence Analysis of Asymptotically Optimal Hypothesis Tests" submitted to  IEEE Transactions on Information Theory, revised Oct 2015.

Dimensionality reduction for hypothesis testing on large-alphabet data

Many modern applications require hypothesis tests to be performed on data drawn from large alphabets. In such large alphabet problems, classical hypothesis tests tend to perform very poorly for moderate sample sizes. We quantify this disadvantage of optimal tests by identifying the limiting behavior of the test statistics used in classical solutions to the problems of universal and composite hypothesis testing. We then develop a new dimensionality reduction framework to address this issue. Our procedure allows the statistician to choose an appropriate test statistic so as to control the limiting bias and variance of the test statistic under the null hypothesis, and at the same time ensure good error performance against specific distributions under the alternate hypothesis. Our solution is based on a new relaxation of the Kullback-Leibler divergence, which we call the mismatched divergence. The   resulting test, called the mismatched test, can be interpreted as a generalization of the Generalized Likelihood Ratio Test (GLRT). A special case of this test is a test that is provably robust to uncertainties in distributions under the null hypothesis. The dimensionality reduction approach based on the mismatched divergence can be applied in very broad contexts including source coding, and filtering for Markov decision processes.

Acceptance region of the mismatched universal hypothesis test illustrated

J. Unnikrishnan, D. Huang, S. Meyn, A. Surana, and V. Veeravalli, “Universal and Composite Hypothesis Testing via Mismatched Divergence” IEEE Transactions on Information Theory, 2011.

Robust quickest change detection

Quickest change detection refers to the problem of quickly detecting an abrupt change in a system subject to a false alarm constraint. Applications include intrusion detection in computer networks and security systems, detection of fault onset in infrastructure of various kinds, and spectrum monitoring for opportunistic access to wireless networks. Most theoretical work on change detection is restricted to the setting where the exact pre-change and post-change distributions of the observations are known, which is often not the case in practice. We propose a novel robust solution to the quickest change detection problem when the exact pre-change and post-change distributions are not known, but these distributions are known to be in some uncertainty classes of distributions. Our solution optimizes the worst-case performance and outperforms the test that is based on the generalized likelihood ratio (GLRT); the GLRT is the benchmark procedure for change-detection when the exact distributions are not known.

J. Unnikrishnan, V. V. Veeravalli, and S. Meyn, “Minimax Robust Quickest Change Detection” IEEE Transactions on Information Theory, 2011.

Reinforcement learning for opportunistic spectrum access in cognitive radio systems

We design an opportunistic spectrum-access policy for cognitive radios in a primary user system that comprises multiple channels with time-varying usage. Using a partially observable Markov decision process (POMDP) model, we obtain a dynamic policy for channel selection that gives improved performance over the state-of-the-art. We also consider a system with imperfect knowledge of the primary statistics and introduce a novel learning-based selection policy that can simultaneously learn the unknown statistics.

J. Unnikrishnan and V. V. Veeravalli, “Algorithms for Dynamic Spectrum Access with Learning for Cognitive Radio” in IEEE Transactions on Signal Processing, 2010.

Cooperative spectrum sensing for cognitive radio

A basic requirement in a cognitive radio system is efficient spectrum sensing. We study cooperative spectrum sensing via energy detection, under the setting in which the cooperating cognitive radios receive correlated power levels due to correlated shadowing. We develop a novel scheme for fusing statistically-dependent decentralized decisions obtained from participating users in a cooperative spectrum sensing setup. As this scheme exploits the correlation between the users’ signals, it provides significant performance improvement over schemes that ignore the correlation.

J. Unnikrishnan and V. V. Veeravalli, “Cooperative Sensing for Primary Detection in Cognitive Radio” in IEEE Journal of Selected Topics in Signal Processing (JSTSP), Special Issue on Signal Processing and Networking for Dynamic Spectrum Access, 2008.