Rohit Gupta, Jayakrishnan Unnikrishnan, Fan Fei, Sheng Liu, Son Tran, Mubarak Shah. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

In this paper, we propose VidLA, an approach for video-language alignment at scale. There are two major limitations of previous video-language alignment approaches. First, they do not capture both short-range and long-range temporal dependencies and typically employ complex hierarchical deep network architectures that are hard to integrate with existing pretrained image-text foundation models. To effectively address this limitation, we instead keep the network architecture simple and use a set of data tokens that operate at different temporal resolutions in a hierarchical manner, accounting for the temporally hierarchical nature of videos. By employing a simple two-tower architecture, we are able to initialize our video-language model with pretrained image-text foundation models, thereby boosting the final performance. Second, existing video-language alignment works struggle due to the lack of semantically aligned large-scale training data. To overcome it, we leverage recent LLMs to curate the largest video-language dataset to date with better visual grounding. Furthermore, unlike existing video-text datasets which only contain short clips, our dataset is enriched with video clips of varying durations to aid our temporally hierarchical data to-kens in extracting better representations at varying temporal scales. Overall, empirical results show that our proposed approach surpasses state-of-the-art methods on Multiple retrieval benchmarks, especially on longer videos, and performs competitively on classification benchmarks.

We introduce and study the problem of camera-radar fusion for 3-D depth reconstruction. This problem is motivated by autonomous driving applications, in which we can expect to have access to both front-facing camera and radar sensors. These two sensors are complementary in several respects: the camera is a passive sensor measuring azimuth and elevation; the radar is an active sensor measuring azimuth and range. Fusing their measurements is therefore beneficial. Our fusion solution uses a modified encoder-decoder deep convolutional neural network. We train and evaluate this network on over 100 000 samples collected in highway environments. Our results demonstrate an improvement in reconstruction accuracy and robustness from fusing the two sensors.

Motivated by requirements for future automotive radar, we study the problem of resolving target elevation from measurements by a one-dimensional horizontal radar antenna array. This is a challenging and ill-posed problem, since such measurements contain only indirect and highly ambiguous elevation cues. As a consequence, traditional model-based approaches fail. We instead propose to use a machine-learning-based approach that learns to exploit the subtle elevation cues and prior knowledge of the scene from the data. We design an encoder-decoder structured deep convolutional neural network that takes a radar return intensity image in the range-azimuth plane as input and produces a depth image in the elevation-azimuth plane as output. We train the network with over 200 000 radar frames collected in highway environments. Through experimental evaluations, we demonstrate the feasibility of resolving the highly ambiguous elevation information in such environments.

We study the problem of solving a linear sensing system when the observations are unlabeled. Specifically we seek a solution to a linear system of equations y = Ax when the order of the observations in the vector y is unknown. Focusing on the setting in which A is a random matrix with i.i.d. entries, we show that if the sensing matrix A admits an oversampling ratio of 2 or higher, then, with probability 1, it is possible to recover x exactly without the knowledge of the order of the observations in y. Furthermore, if x is of dimension K, then any 2K entries of y are sufficient to recover x. This result implies the existence of deterministic unlabeled sensing matrices with an oversampling factor of 2 that admit perfect reconstruction. The result is universal in that conditioned on the realization of matrix A, recovery is guaranteed for all possible choices of x. While the proof is constructive, it uses a combinatorial algorithm which is not practical, leaving the question of complexity open. We also analyze a noisy version of the problem and show that local stability is guaranteed by the solution. In particular, for every x, the recovery error tends to zero as the signal-to-noise ratio tends to infinity. The question of universal stability is unclear. In addition, we obtain a converse of the result in the noiseless case: If the number of observations in y is less than 2K, then with probability 1, universal recovery fails, i.e., with probability 1, there exist distinct choices of x which lead to the same unordered list of observations in y. We also present extensions of the result of the noiseless case to special cases with non-i.i.d. entries in A, and to a different setting in which the labels of a portion of the observations y are known. 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”, multi-target tracking applications, and in sampling signals in the presence of jitter.

Most users of online services have unique behavioral or usage patterns. These behavioral patterns can be exploited to identify and track users by using only the observed patterns in the behavior. We study the task of identifying users from statistics of their behavioral patterns. In particular, we focus on the setting in which we are given histograms of users' data collected during two different experiments. We assume that, in the first data set, the users' identities are anonymized or hidden and that, in the second data set, their identities are known. We study the task of identifying the users by matching the histograms of their data in the first data set with the histograms from the second data set. In recent works, the optimal algorithm for this user identification task is introduced. In this paper, we evaluate the effectiveness of this method on three different types of data sets with up to 50 000 users, and in multiple scenarios. Using data sets such as call data records, web browsing histories, and GPS trajectories, we demonstrate that a large fraction of users can be easily identified given only histograms of their data; hence, these histograms can act as users' fingerprints. We also verify that simultaneous identification of users achieves better performance compared with one-by-one user identification. Furthermore, we show that using the optimal method for identification indeed gives higher identification accuracy than the heuristics-based approaches in the practical scenarios. The accuracy obtained under this optimal method can thus be used to quantify the maximum level of user identification that is possible in such settings. We show that the key factors affecting the accuracy of the optimal identification algorithm are the duration of the data collection, the number of users in the anonymized data set, and the resolution of the data set. We also analyze the effectiveness of k-anonymization in resisting user identification attacks on these data sets.

In recent years, solutions to various hypothesis testing problems in the asymptotic setting have been proposed using the results from large deviation 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.

Consider a finite set of sources, each producing independent identically distributed observations that follow a unique probability distribution on a finite alphabet. We study the problem of matching a finite set of observed sequences to the set of sources under the constraint that the observed sequences are produced by distinct sources. In general, the number of sequences N may be different from the number of sources M, and only some K ≤ min {M, N} of the observed sequences may be produced by a source from the set of sources of interest. We consider two versions of the problem-one in which the probability laws of the sources are known and another in which the probability laws of the sources are unspecified but one training sequence from each of the sources is available. We show that both these problems can be solved using a sequence of tests that are allowed to produce no-match decisions. The tests ensure exponential decay of the probabilities of incorrect matching as the sequence lengths increase, and minimize the no-match decisions. Both the tests can be implemented using variants of the minimum weight-matching algorithm applied to a weighted bipartite graph. We also compare the performances obtained using these tests with those obtained using tests that do not consider the constraint that the sequences are produced by distinct sources. For the version of the problem in which the probability laws of the sources are known, we compute the rejection exponents and error exponents of the tests and show that the tests that make use of the constraint have better exponents than the tests that do not make use of this information.

We study the problem of privacy-preserving computation of functions of data that belong to users in a social network under the assumption that users are willing to share their private data with trusted friends in the network. We demonstrate that such trust relationships can be exploited to significantly improve the tradeoff between the privacy of users' data and the accuracy of the computation. Under a one-hop trust model we design an algorithm for partitioning the users into circles of trust and develop a differentially private scheme for computing the global function using results of local computations within each circle. We quantify the improvement in the privacy-accuracy tradeoff of our scheme with respect to other mechanisms that do not exploit inter-user trust. We verify the efficiency of our algorithm by implementing it on social networks with up to one million nodes. Applications of our method include surveys, elections, and recommendation systems.

This paper presents new sufficient conditions under which a field (or image) can be perfectly reconstructed from its samples on a union of two lattices that share a common coarse lattice. In particular, if samples taken on the first lattice can be used to reconstruct a field bandlimited to some spectral support region, and likewise samples taken on the second lattice can reconstruct a field bandlimited to another spectral support region, then under certain conditions, a field bandlimited to the union of these two spectral regions can be reconstructed from its samples on the union of the two respective lattices. These results generalize a previous perfect reconstruction theorem for Manhattan sampling, where data is taken at high density along evenly spaced rows and columns of a rectangular grid. Additionally, a sufficient condition is given under which the Landau lower bound is achieved.

Wikipedia has become a widely-used resource on signal processing. However, the freelance-editing model of Wikipedia makes it challenging to maintain a high content quality. We develop techniques to monitor the network structure and content quality of Signal Processing (SP) articles on Wikipedia. Using metrics to quantify the importance and quality of articles, we generate a list of SP articles on Wikipedia arranged in the order of their need for improvement. The tools we use include the HITS and PageRank algorithms for network structure, crowdsourcing for quantifying article importance and known heuristics for article quality.

Consider the task of sampling and reconstructing a bandlimited spatial field in R2using moving sensors that take measurements along their path. It is inexpensive to increase the sampling rate along the paths of the sensors but more expensive to increase the total distance traveled by the sensors per unit area, which we call the path density. In this paper, we introduce the problem of designing sensor trajectories that are minimal in path density subject to the condition that the measurements of the field on these trajectories admit perfect reconstruction of bandlimited fields. We study various possible designs of sampling trajectories. Generalizing some ideas from the classical theory of sampling on lattices, we obtain necessary and sufficient conditions on the trajectories for perfect reconstruction. We show that a single set of equispaced parallel lines has the lowest path density from certain restricted classes of trajectories that admit perfect reconstruction. We then generalize some of our results to higher dimensions. We first obtain results on designing sampling trajectories in higher dimensional fields. Further, interpreting trajectories as 1-D manifolds, we extend some of our ideas to higher dimensional sampling manifolds. We formulate the problem of designing κ-dimensional sampling manifolds ford-dimensional spatial fields that are minimal in manifold density, a natural generalization of the path density. We show that our results on sampling trajectories for fields in R2can be generalized to analogous results ond-dimensional sampling manifolds ford-dimensional spatial fields.

The classical approach to sampling time-invariant spatial fields uses static sensors distributed over space. We study a new approach involving mobile sensors that move through space measuring the field values along their paths. A single moving sensor can take measurements over a wide spatial area thus acting as a substitute for a potentially large number of static sensors. A moving sensor encounters the spatial field in its path in the form of a time-domain signal. Hence a time-domain anti-aliasing filter can be employed at the mobile sensor to limit the amount of out-of-band noise prior to sampling. We analytically quantify the advantage of mobile sensing over static sensing in rejecting out-of-band noise. We also demonstrate via simulations the improvement in reconstruction accuracy that can be obtained using mobile sensors and filtering in a temperature measurement problem.

Suppose we are given two independent strings of data from a known finite alphabet. We are interested in testing the null hypothesis that both the strings were drawn from the same distribution, assuming that the samples within each string are mutually independent. Among statisticians, the most popular solution for such a homogeneity test is the two sample chi-square test, primarily due to its ease of implementation and the fact that the limiting null hypothesis distribution of the associated test statistic is known and easy to compute. Although tests that are asymptotically optimal in error probability have been proposed in the information theory literature, such optimality results are not well-known and such tests are rarely used in practice. In this paper we seek to bridge the gap between theory and practice. We study two different optimal tests proposed by Shayevitz [1] and Gutman [2]. We first obtain a simplified structure of Shayevitz's test and then obtain limiting distributions of the test statistics used in both the tests. These results provide guidelines for choosing thresholds that guarantee an approximate false alarm constraint for finite length observation sequences, thus making these tests easy to use in practice. The approximation accuracies are demonstrated using simulations. We argue that such homogeneity tests with provable optimality properties could potentially be better choices than the chi-square test in practice.

We study the problem of sampling a high-dimensional bandlimited field on a union of shifted lattices under certain assumptions motivated by some practical sampling applications. Under these assumptions, we show that simple necessary and sufficient conditions for perfect reconstruction can be identified. We also obtain an explicit scheme for reconstructing the field from its samples on the various shifted lattices. We illustrate our results using examples.

We study the problem of parametric model-fitting in a finite alphabet setting. We characterize the weak convergence of the goodness-of-fit statistic with respect to an exponential family when the observations are drawn from some alternate distribution. We then study the effects of outliers on the model-fitting procedure by specializing our results to ∈-contaminated versions of distributions from the exponential family. We characterize the sensitivity of various distributions from the exponential family to outliers, and provide guidelines for choosing thresholds for a goodness-of-fit test that is robust to outliers in the data.

For the universal hypothesis testing problem, where the goal is to decide between the known null hypothesis distribution and some other unknown distribution, Hoeffding proposed a universal test in the nineteen sixties. Hoeffding's universal test statistic can be written in terms of Kullback-Leibler (K-L) divergence between the empirical distribution of the observations and the null hypothesis distribution. In this paper a modification of Hoeffding's test is considered based on a relaxation of the K-L divergence, referred to as the mismatched divergence. The resulting mismatched test is shown to be a generalized likelihood-ratio test (GLRT) for the case where the alternate distribution lies in a parametric family of distributions characterized by a finite-dimensional parameter, i.e., it is a solution to the corresponding composite hypothesis testing problem. For certain choices of the alternate distribution, it is shown that both the Hoeffding test and the mismatched test have the same asymptotic performance in terms of error exponents. A consequence of this result is that the GLRT is optimal in differentiating a particular distribution from others in an exponential family. It is also shown that the mismatched test has a significant advantage over the Hoeffding test in terms of finite sample size performance for applications involving large alphabet distributions. This advantage is due to the difference in the asymptotic variances of the two test statistics under the null hypothesis.

The popular criteria of optimality for quickest change detection procedures are the Lorden criterion, the Pollak criterion, and the Bayesian criterion. In this paper, a robust version of these quickest change detection problems is considered when the pre-change and post-change distributions are not known exactly but belong to known uncertainty classes of distributions. For uncertainty classes that satisfy a specific condition, it is shown that one can identify least favorable distributions (LFDs) from the uncertainty classes, such that the detection rule designed for the LFDs is optimal for the robust problem in a minimax sense. The condition is similar to that required for the identification of LFDs for the robust hypothesis testing problem originally studied by Huber. An upper bound on the delay incurred by the robust test is also obtained in the asymptotic setting under the Lorden criterion of optimality. This bound quantifies the delay penalty incurred to guarantee robustness. When the LFDs can be identified, the proposed test is easier to implement than the CUSUM test based on the Generalized Likelihood Ratio (GLR) statistic which is a popular approach for such robust change detection problems. The proposed test is also shown to give better performance than the GLR test in simulations for some parameter values.

Goodness-of-fit tests are statistical procedures used to test the hypothesis H0that a set of observations were drawn according to some given probability distribution. Decision thresholds used in goodness-of-fit tests are typically set for guaranteeing a target false-alarm probability. In many popular testing procedures results on the weak convergence of the test statistics are used for setting approximate thresholds when exact computation is infeasible. In this work, we study robust procedures for goodness-of-fit where accurate models are not available for the distribution of the observations under hypothesis H0. We develop procedures for setting thresholds in two specific examples - a robust version of the Kolmogorov-Smirnov test for continuous alphabets and a robust version of the Hoeffding test for finite alphabets.

We study the problem of robust quickest change detection where the pre-change and post-change distributions are not known exactly but belong to known uncertainty classes of distributions. Both Bayesian and minimax versions of the quickest change detection problem are considered. When the uncertainty classes satisfy some specific conditions, we identify least favorable distributions (LFD's) from the uncertainty classes, and show that the detection rule designed for the LFD's is optimal in a minimax sense. The condition is similar to that required for the existence of LFD's for the robust hypothesis testing problem studied by Huber.

The support vector machine (SVM) has emerged as one of the most popular approaches to classification and supervised learning. It is a flexible approach for solving the problems posed in these areas, but the approach is not easily adapted to noisy data in which absolute discrimination is not possible. We address this issue in this paper by returning to the statistical setting. The main contribution is the introduction of a statistical support vector machine (SSVM) that captures all of the desirable features of the SVM, along with desirable statistical features of the classical likelihood ratio test. In particular, we establish the following: (i) The SSVM can be designed so that it forms a continuous function of the data, yet also approximates the potentially discontinuous log likelihood ratio test. (ii) Extension to universal detection is developed, in which only one hypothesis is labeled (a semi-supervised learning problem). (iii) The SSVM generalizes the robust hypothesis testing problem based on a moment class. Motivation for the approach and analysis are each based on ideas from information theory. A detailed performance analysis is provided in the special case of i.i.d. observations. This research was partially supported by NSF under grant CCF 07-29031, by UTRC, Motorola, and by the DARPA ITMANET program. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF, UTRC, Motorola, or DARPA.

One of the main requirements of cognitive radio systems is the ability to reliably detect the presence of licensed primary transmissions. Previous works on the problem of detection for cognitive radio have suggested the necessity of user cooperation in order to be able to detect at the really low signal- to-noise ratios experienced in practical situations. We consider a system of cognitive radio users who cooperate with each other in trying to detect licensed transmissions. Assuming that the cooperating nodes use identical energy detectors, we model the received signals as correlated log-normal random variables and study the problem of fusing the decisions made by the individual nodes. We design a linear-quadratic (LQ) fusion strategy based on a deflection criterion for this problem, that takes into account the correlation between the nodes. Our simulation results show that the LQ detector significantly outperforms the counting rule, which is the fusion rule that is obtained by ignoring the correlation.