We introduce marginalization models (MAMs), a new family of generative models for high-dimensional discrete data. They offer scalable and flexible generative modeling by explicitly modeling all induced marginal distributions. Marginalization models enable fast approximation of arbitrary marginal probabilities with a single forward pass of the neural network, which overcomes a major limitation of arbitrary marginal inference models, such as any-order autoregressive models. MAMs also address the scalability bottleneck encountered in training any-order generative models for high-dimensional problems under the context of energy-based training, where the goal is to match the learned distribution to a given desired probability (specified by an unnormalized log-probability function such as energy or reward function). We propose scalable methods for learning the marginals, grounded in the concept of "marginalization self-consistency". We demonstrate the effectiveness of the proposed model on a variety of discrete data distributions, including images, text, physical systems, and molecules, for maximum likelihood and energy-based training settings. MAMs achieve orders of magnitude speedup in evaluating the marginal probabilities on both settings. For energy-based training tasks, MAMs enable any-order generative modeling of high-dimensional problems beyond the scale of previous methods. Code is available at github.com/PrincetonLIPS/MaM.

Length extrapolation permits training a transformer language model on short sequences that preserves perplexities when tested on substantially longer sequences.A relative positional embedding design, ALiBi, has had the widest usage to date.We dissect ALiBi via the lens of receptive field analysis empowered by a novel cumulative normalized gradient tool.The concept of receptive field further allows us to modify the vanilla Sinusoidal positional embedding to create Sandwich, the first parameter-free relative positional embedding design that truly length information uses longer than the training sequence.Sandwich shares with KERPLE and T5 the same logarithmic decaying temporal bias pattern with learnable relative positional embeddings; these elucidate future extrapolatable positional embedding design.

While deep generative models have succeeded in image processing, natural language processing, and reinforcement learning, training that involves discrete random variables remains challenging due to the high variance of its gradient estimation process. Monte Carlo is a common solution used in most variance reduction approaches. However, this involves time-consuming resampling and multiple function evaluations. We propose a Gapped Straight-Through (GST) estimator to reduce the variance without incurring resampling overhead. This estimator is inspired by the essential properties of Straight-Through Gumbel-Softmax. We determine these properties and show via an ablation study that they are essential. Experiments demonstrate that the proposed GST estimator enjoys better performance compared to strong baselines on two discrete deep generative modeling tasks, MNIST-VAE and ListOps.

Relative positional embeddings (RPE) have received considerable attention since RPEs effectively model the relative distance among tokens and enable length extrapolation. We propose KERPLE, a framework that generalizes relative position embedding for extrapolation by kernelizing positional differences. We achieve this goal using conditionally positive definite (CPD) kernels, a class of functions known for generalizing distance metrics. To maintain the inner product interpretation of self-attention, we show that a CPD kernel can be transformed into a PD kernel by adding a constant offset. This offset is implicitly absorbed in the Softmax normalization during self-attention. The diversity of CPD kernels allows us to derive various RPEs that enable length extrapolation in a principled way. Experiments demonstrate that the logarithmic variant achieves excellent extrapolation performance on three large language modeling datasets. Our implementation and pretrained checkpoints are released at~\url{https://github.com/chijames/KERPLE.git}.

We consider the problem of estimating states (e.g., position and velocity) and physical parameters (e.g., friction, elasticity) from a sequence of observations when provided a dynamic equation that describes the behavior of the system. The dynamic equation can arise from first principles (e.g., Newton’s laws) and provide useful cues for learning, but its physical parameters are unknown. To address this problem, we propose a model that estimates states and physical parameters of the system using two main components. First, an autoencoder compresses a sequence of observations (e.g., sensor measurements, pixel images) into a sequence for the state representation that is consistent with physics by including a simulation of the dynamic equation. Second, an estimator is coupled with the autoencoder to predict the values of the physical parameters. We also theoretically and empirically show that using Fourier feature mappings improves generalization of the estimator in predicting physical parameters compared to raw state sequences. In our experiments on three visual and one sensor measurement tasks, our model imposes interpretability on latent states and achieves improved generalization performance for long-term prediction of system dynamics over state-of-the-art baselines.

Despite its experimental success, Model-based Reinforcement Learning still lacks a complete theoretical understanding. To this end, we analyze the error in the cumulative reward using a contraction approach. We consider both stochastic and deterministic state transitions for continuous (non-discrete) state and action spaces. This approach doesn’t require strong assumptions and can recover the typical quadratic error to the horizon. We prove that branched rollouts can reduce this error and are essential for deterministic transitions to have a Bellman contraction. Our analysis of policy mismatch error also applies to Imitation Learning. In this case, we show that GAN-type learning has an advantage over Behavioral Cloning when its discriminator is well-trained.

We consider the problem of reinforcement learning when provided with (1) a baseline control policy and (2) a set of constraints that the learner must satisfy. The baseline policy can arise from demonstration data or a teacher agent and may provide useful cues for learning, but it might also be sub-optimal for the task at hand, and is not guaranteed to satisfy the specified constraints, which might encode safety, fairness or other application-specific requirements. In order to safely learn from baseline policies, we propose an iterative policy optimization algorithm that alternates between maximizing expected return on the task, minimizing distance to the baseline policy, and projecting the policy onto the constraint-satisfying set. We analyze our algorithm theoretically and provide a finite-time convergence guarantee. In our experiments on five different control tasks, our algorithm consistently outperforms several state-of-the-art baselines, achieving 10 times fewer constraint violations and 40% higher reward on average.

While safe reinforcement learning (RL) holds great promise for many practical applications like robotics or autonomous cars, current approaches require specifying constraints in mathematical form. Such specifications demand domain expertise, limiting the adoption of safe RL. In this paper, we propose learning to interpret natural language constraints for safe RL. To this end, we first introduce HAZARDWORLD, a new multi-task benchmark that requires an agent to optimize reward while not violating constraints specified in free-form text. We then develop an agent with a modular architecture that can interpret and adhere to such textual constraints while learning new tasks. Our model consists of (1) a constraint interpreter that encodes textual constraints into spatial and temporal representations of forbidden states, and (2) a policy network that uses these representations to produce a policy achieving minimal constraint violations during training. Across different domains in HAZARDWORLD, we show that our method achieves higher rewards (up to11x) and fewer constraint violations (by 1.8x) compared to existing approaches. However, in terms of absolute performance, HAZARDWORLD still poses significant challenges for agents to learn efficiently, motivating the need for future work.

Prior work has shown that low-rank matrix factorization has infinitely many critical points, each of which is either a global minimum or a (strict) saddle point. We revisit this problem and provide simple, intuitive proofs of a set of extended results for low-rank and general-rank problems. We couple our investigation with a known invariant manifold M0 of gradient flow. This restriction admits a uniform negative upper bound on the least eigenvalue of the Hessian map at all strict saddles in M0. The bound depends on the size of the nonzero singular values and the separation between distinct singular values of the matrix to be factorized.

Gaussian processes (GPs) are flexible priors for modeling functions. However, their success depends on the kernel accurately reflecting the properties of the data. One of the appeals of the GP framework is that the marginal likelihood of the kernel hyperparameters is often available in closed form, enabling optimization and sampling procedures to fit these hyperparameters to data. Unfortunately, point-wise evaluation of the marginal likelihood is expensive due to the need to solve a linear system; searching or sampling the space of hyperparameters thus often dominates the practical cost of using GPs. We introduce an approach to the identification of kernel hyperparameters in GP regression and related problems that sidesteps the need for costly marginal likelihoods. Our strategy is to "amortize" inference over hyperparameters by training a single neural network, which consumes a set of regression data and produces an estimate of the kernel function, useful across different tasks. To accommodate the varying dimension and cardinality of different regression problems, we use a hierarchical self-attention-based neural network that produces estimates of the hyperparameters which are invariant to the order of the input data points and data dimensions. We show that a single neural model trained on synthetic data is able to generalize directly to several different unseen real-world GP use cases. Our experiments demonstrate that the estimated hyperparameters are comparable in quality to those from the conventional model selection procedures, while being much faster to obtain, significantly accelerating GP regression and its related applications such as Bayesian optimization and Bayesian quadrature. The code and pre-trained model are available at https://github.com/PrincetonLIPS/AHGP.

Advanced brain imaging analysis methods, including multivariate pattern analysis (MVPA), functional connectivity, and functional alignment, have become powerful tools in cognitive neuroscience over the past decade. These tools are implemented in custom code and separate packages, often requiring different software and language proficiencies. Although usable by expert researchers, novice users face a steep learning curve. These difficulties stem from the use of new programming languages (e.g., Python), learning how to apply machine-learning methods to high-dimensional fMRI data, and minimal documentation and training materials. Furthermore, most standard fMRI analysis packages (e.g., AFNI, FSL, SPM) focus on preprocessing and univariate analyses, leaving a gap in how to integrate with advanced tools. To address these needs, we developed BrainIAK (brainiak.org), an open-source Python software package that seamlessly integrates several cutting-edge, computationally efficient techniques with other Python packages (e.g., Nilearn, Scikit-learn) for file handling, visualization, and machine learning. To disseminate these powerful tools, we developed user-friendly tutorials (in Jupyter format; https://brainiak.org/tutorials/) for learning BrainIAK and advanced fMRI analysis in Python more generally. These materials cover techniques including: MVPA (pattern classification and representational similarity analysis); parallelized searchlight analysis; background connectivity; full correlation matrix analysis; inter-subject correlation; inter-subject functional connectivity; shared response modeling; event segmentation using hidden Markov models; and real-time fMRI. For long-running jobs or large memory needs we provide detailed guidance on high-performance computing clusters. These notebooks were successfully tested at multiple sites, including as problem sets for courses at Yale and Princeton universities and at various workshops and hackathons. These materials are freely shared, with the hope that they become part of a pool of open-source software and educational materials for large-scale, reproducible fMRI analysis and accelerated discovery.

We explore transferring learning between fMRI datasets. A method is introduced to improve prediction accuracy on a primary fMRI dataset by jointly learning a model using other secondary fMRI datasets. We assume the secondary datasets are directly or indirectly linked to the primary dataset through sets of partially shared subjects. This method is particularly useful when the primary dataset is small. Using six fMRI datasets linked by various subsets of shared subjects, we show that the method yields improved performance in various predictive tasks. Our tests are performed on a variety of regions of interest in the brain and across various stimuli.

There is growing interest in understanding the impact of architectural parameters such as depth, width, and the type of activation function on the performance of a neural network. We provide an upper-bound on the number of free parameters a ReLU-type neural network needs to exactly fit the training data. Whether a net of this size generalizes to test data will be governed by the fidelity of the training data and the applicability of the principle of Occam's Razor. We introduce the concept of s-separability and show that for the special case of (c-1)-separable training data with c classes, a neural network with (d + 2c) parameters can achieve 100% training classification accuracy, where d is the dimension of data. It is also shown that if the number of free parameters is at least (d+ 2p), where p is the size of the training set, the neural network can memorize each training example. Finally, a framework is introduced for finding a neural network achieving a given training error, subject to an upper-bound on layer width.

Practical limitations on the duration of individual fMRI scans have led neuroscientist to consider the aggregation of data from multiple subjects. Differences in anatomical structures and functional topographies of brains require aligning data across subjects. Existing functional alignment methods serve as a preprocessing step that allows subsequent statistical methods to learn from the aggregated multi-subject data. Despite their success, current alignment methods do not leverage the labeled data used in the subsequent methods. In this work we propose a semi-supervised scheme that simultaneously learns the alignment and performs the analysis. We derive a specific instance of the scheme using the Shared Response Model for alignment and Multinomial Logistic Regression for classification. In our experiments this method improves the average classification accuracy from 65.5% to 68.5%, and from 5.3% to 6.1% over the independently-trained methods. Furthermore, our method achieves similar prediction with almost half the samples used for alignment.

This paper is a survey of dictionary screening for the lasso problem. The lasso problem seeks a sparse linear combination of the columns of a dictionary to best match a given target vector. This sparse representation has proven useful in a variety of subsequent processing and decision tasks. For a given target vector, dictionary screening quickly identifies a subset of dictionary columns that will receive zero weight in a solution of the corresponding lasso problem. These columns can be removed from the dictionary prior to solving the lasso problem without impacting the optimality of the solution obtained. This has two potential advantages: it reduces the size of the dictionary, allowing the lasso problem to be solved with less resources, and it may speed up obtaining a solution. Using a geometrically intuitive framework, we provide basic insights for understanding useful lasso screening tests and their limitations. We also provide illustrative numerical studies on several datasets.

The scale of functional magnetic resonance image data is rapidly increasing as large multi-subject datasets are becoming widely available and high-resolution scanners are adopted. The inherent low-dimensionality of the information in this data has led neuroscientists to consider factor analysis methods to extract and analyze the underlying brain activity. In this work, we consider two recent multi-subject factor analysis methods: the Shared Response Model and the Hierarchical Topographic Factor Analysis. We perform analytical, algorithmic, and code optimization to enable multi-node parallel implementations to scale. Single-node improvements result in 99χ and 2062x speedups on the two methods, and enables the processing of larger datasets. Our distributed implementations show strong scaling of 3.3x and 5.5χ respectively with 20 nodes on real datasets. We demonstrate weak scaling on a synthetic dataset with 1024 subjects, equivalent in size to the biggest fMRI dataset collected until now, on up to 1024 nodes and 32,768 cores.

Multi-subject fMRI data is critical for evaluating the generality and validity of findings across subjects, and its effective utilization helps improve analysis sensitivity. We develop a shared response model for aggregating multi-subject fMRI data that accounts for different functional topographies among anatomically aligned datasets. Our model demonstrates improved sensitivity in identifying a shared response for a variety of datasets and anatomical brain regions of interest. Furthermore, by removing the identified shared response, it allows improved detection of group differences. The ability to identify what is shared and what is not shared opens the model to a wide range of multi-subject fMRI studies.

Recent studies have suggested that the critical aspect of sparse representation-based classification (SRC) is collaborative representation, rather than sparsity. This has given rise to fast collaborative representation-based classification using 2-norm regularized least squares (CRC-RLS). This paper digs deeper into the difference between SRC and CRC-RLS. We show that linear coding schemes such as CRC-RLS share a common pairwise boundary class B. Moreover, the corresponding pairwise classifiers can be realized by quadratic SVMs. Using three datasets, we show empirically that collaborative representations are not always required, and that a quadratic SVM has superior generalization over CRC-RLS, with fast classification times. However, SRC exhibits the best prediction accuracy. This leads us to posit that the nonlinear coding of SRC is a key attribute.

We propose a novel collaborative denoising scheme for multi-subject fMRI data. The scheme assumes that subjects experience a common, synchronous stimulus and uses the across-subject shared response structure to jointly denoise each subject's fMRI response along the spatial or voxel domain. Denoising is accomplished by learning subject-specfic orthonormal bases that yield sparse representations in a common transform domain. We provide empirical results using a real-world, multi-subject fMRI dataset.

A support vector machine (SVM) regularized with the Pairwise Elastic Net (PEN) penalty is used to automatically select a sparse set of brain voxel clusters based on the fMRI responses to two stimuli classes. This requires solving the PEN-SVM quadratic program. We show how to design the PEN regularization to encode, in a graph-based fashion, the pairwise similarity structure of the voxel fMRI responses and how to control the spatial locality of the encoding using a voxel searchlight. The voxel similarity encoding is reflected in the sparse structure of the weights of trained PEN-SVM and these weights automatically select a sparse set of voxel clusters. We empirically demonstrate the effectiveness of the approach using a real-world, multi-subject fMRI dataset.

Recently, methods of screening the lasso problem have been developed that use the target vector x to quickly identify a subset of columns of the dictionary that will receive zero weight in the solution. Current classes of screening tests are based on bounding the dual lasso solution within a sphere or the intersection of a sphere and a half space. Stronger tests are possible but are more complex and incur a higher computational cost. To investigate this, we determine the optimal screening test when the dual lasso solution is bounded within the intersection of a sphere and two half spaces, and empirically investigate the trade-off that this test makes between screening power and computational efficiency. We also compare its performance both in terms of rejection power and efficiency to existing test classes. The new test always has better rejection, and for an interesting range of regularization parameters, offers better computational efficiency.

Screening for lasso problems is a means of quickly reducing the size of the dictionary needed to solve a given instance without impacting the optimality of the solution obtained. We investigate a sequential screening scheme using a selected sequence of regularization parameter values decreasing to the given target value. Using analytical and empirical means we give insight on how the values of this sequence should be chosen and show that well designed sequential screening yields significant improvement in dictionary reduction and computational efficiency for lightly regularized lasso problems.

Solving a lasso problem is a practical approach for acquiring a sparse representation of a signal with respect to a given dictionary. Driven by the demand for sparse representations over large-scale data in machine learning and statistics, we explore lasso screening tests. These enhance solution efficiency via the elimination of codewords absent in the optimal solution prior to detailed computation. On basis of the concept of a region test and the recently introduced dome test, we propose the 2-codeword test, which uses two codewords together in a correlation screening test. In addition to the rejection rate as the performance measure, we introduce an innovative way to access the performance of a screening test, called the uncertainty measure, via a comparison with the optimal test.

We investigate connections between the generalized lasso and the standard lasso problem. We show by an efficient direct construction, that the generalized lasso problem is reducible to a subspace constrained lasso. We then derive the dual of the subspace constrained lasso. This dual problem can be projected to the dual of a standard lasso problem with a modified dictionary. Finally, we discuss the application of these ideas to image approximation using the 2D fused lasso.

The lasso problem, least squares with a ℓ1regularization penalty, has been very successful as a tool for obtaining sparse representations of data in terms of given dictionary. It is known, but not widely appreciated, that the lasso problem need not have a unique solution. Sufficient conditions which ensure uniqueness of the solution are known but necessary and sufficient conditions have been elusive. We present three structural results on the lasso problem. First, we show that when the dictionary has more columns than rows, it is always possible to ensure that the dictionary has full row rank. Next we show that the feasible set for the dual lasso problem is bounded if and only if the dictionary has full row rank. Lastly, we give necessary and sufficient conditions for the uniqueness of a lasso solution.

We consider the problem of detecting stimulus driven changes in brain functional connectivity. Estimating functional connectivity from fMRI data sampled over a small time period is difficult - there is simply not enough data to permit reliable estimates. We investigate the use of a sparse Gaussian graphical model regularized by a graph learned from data sampled over a longer time period. We establish a framework to identify the changes in brain connectivity driven by short-term stimuli. Results of experiments on both synthetic and real fMRI data illustrate the attributes of our methods as well as the difficulty of the problem.

Representing a vector as a sparse linear combination of codewords, e.g. by solving a lasso problem, lies at the heart of many machine learning and statistics applications. To improve the efficiency of solving lasso problems, we systematically investigate lasso screening, a process that quickly identifies dictionary entries that won't be used in the optimal sparse representation, and hence can be removed from the problem. We propose a general test called an R region test that unifies existing screening tests and we derive a particular instance called the dome test. This test is stronger than existing screening tests and can be executed in linear-time as a two-pass test with a memory footprint of only three codewords.

We offer a regularized, kernel extension of the multi-set, orthogonal Procrustes problem, or hyperalignment. Our new method, called Kernel Hyperalignment, expands the scope of hyperalignment to include nonlinear measures of similarity and enables the alignment of multiple datasets with a large number of base features. With direct application to fMRI data analysis, kernel hyperalignment is well-suited for multi-subject alignment of large ROIs, including the entire cortex. We conducted experiments using real-world, multi-subject fMRI data.

Despite the tremendous success of wavelet-based image regularization, we still lack a comprehensive understanding of the exact factor that controls edge preservation and a principled method to determine the wavelet decomposition structure for dimensions greater than 1. We address these issues from a machine learning perspective by using tree classifiers to underpin a new image regularizer that measures the complexity of an image based on the complexity of the dyadic-tree representations of its sublevel sets. By penalizing unbalanced dyadic trees less, the regularizer preserves sharp edges. The main contribution of this paper is the connection of concepts from structured dyadic-tree complexity measures, wavelet shrinkage, morphological wavelets, and smoothness regularization in Besov space into a single coherent image regularization framework. Using the new regularizer, we also provide a theoretical basis for the data-driven selection of an optimal dyadic wavelet decomposition structure. As a specific application example, we give a practical regularized image denoising algorithm that uses this regularizer and the optimal dyadic wavelet decomposition structure.

We pose a modified version of the two-sided orthogonal Procrustes problem subject to a grouping constraint, and offer an efficient solution method. This problem has applications in weighted graph matching. Simulation results indicate that the algorithm can effectively use the grouping information to greatly improve estimation accuracy in the presence of noise.

This paper presents a sparse approach of solving the one-sided Procrustes problem with special orthogonal constraint. By leveraging a planar decomposition common to all rotation matrices, a new constraint is introduced into this classical problem in the form of a sparsity-inducing norm. We call the resulting optimization problem the Rotational Lasso. Experimental results are presented from a synthetic dataset.

The Support Vector Machine (SVM) methodology is an effective, supervised, machine learning method that gives state-of-the-art performance for brain state classification from functional magnetic resonance brain images (fMRI). Due to the poor scalability of SVM (cubic in the number of training points) and the massive size of fMRI images, a SVM analysis is usually performed after data collection. Recent advances in real-time fMRI applications, such as Brain Computer Interfaces, require a fast and reliable classification method running in synchronization with the image collection. We design an online Kernel SVM (OKSVM) algorithm based on the Sequential Minimization Optimization (SMO) method, that is fast (training on each new image within 1 sec), has memory and time cost that scales linearly with the number of points used, and yields comparable prediction performance to an offline SVM. We analyze the method's performance by testing it on real fMRI data sets, and show that OKSVM performs well at greatly reduced computational cost. Our work provides a feasible online Kernel SVM for real-time fMRI experiments, and can be used to guide for the design of similar online classifiers in fMRI cognitive state classification.

Real-time functional magnetic resonance imaging (rtfMRI) enables classification of brain activity during data collection thus making inference results accessible to both the subject and experimenter during the experiment. The major challenge of rtfMRI is the potential loss of inference accuracy due to the resource limitations that rtfMRI imposes. For example, many widely-used analysis methods in off-line neuroimaging are too time-consuming for rtfMRI. We develop an online, real-time, conjugate gradient (rtCG) algorithm that learns to classify brain states as data is being collected. The algorithm is closely connected to partial least squares (PLS), a popular off-line analysis method. We give a theoretical comparison with PLS and show that the algorithm generates identical results to PLS for appropriate initial conditions. However, in practice using an alternative initial condition yields faster convergence. Experimental results show that the online rtCG classifier: is fast (training time <; 0.5s), is accurate (prediction accuracy ≈ 90%), can adapt to a varying stimulus, and yields better classification performance than standard PLS applied to a sliding window of recent data.

We propose a new multichannel image denoising algorithm. To exploit important inter-channel dependencies, we first use dynamic programming to learn an explicit dyadic tree representation of the common structure of the channels. Based on this dyadic tree, optimal Haar wavelet thresholding is then applied to denoise the image. In addition to the original channels, the algorithm can employ multiple derived channels to improve tree learning. Experimental results confirm that the approach improves multichannel image denoising performance both in PSNR and in edge preservation.

Learning sparse representations on data adaptive dictionaries is a state-of-the-art method for modeling data. But when the dictionary is large and the data dimension is high, it is a computationally challenging problem. We explore three aspects of the problem. First, we derive new, greatly improved screening tests that quickly identify codewords that are guaranteed to have zero weights. Second, we study the properties of random projections in the context of learning sparse representations. Finally, we develop a hierarchical framework that uses incremental random projections and screening to learn, in small stages, a hierarchically structured dictionary for sparse representations. Empirical results show that our framework can learn informative hierarchical sparse representations more efficiently.

We propose an algorithm for detecting bridges and estimating geodesic distances from a set of noisy samples of an underlying manifold. Finding geodesics on a nearest neighbors graph is known to fail in the presence of bridges. Our method detects bridges using global statistics via a Markov random walk and denoises the nearest neighbors graph using “surrogate” weights. We show experimentally that our method outperforms methods based on local neighborhood statistics.

We propose a new approach to semi-supervised clustering that utilizes boosting to simultaneously learn both a similarity measure and a clustering of the data from given instance-level must-link and cannot-link constraints. The approach is distinctive in that it uses a supervising feedback loop to gradually update the similarity while at the same time guiding an underlying unsupervised clustering algorithm. Our approach is grounded in the theory of boosting. We provide three examples of the clustering algorithm on real datasets.

We investigate a technique for estimating level sets of functionals on the 2-sphere. The surface of the sphere is finely partitioned using a tree decomposition and a candidate level set is obtained by minimizing a regularized cost on the tree. A cycle spinning scheme, implemented as an ensemble classification method, is developed to decrease the variance of the tree-based estimate. Both constructions are compatible with many existing hierarchical discretizations of the 2-sphere, e.g. HEALPix and HTM. We present simulation results of a synthetic data set and an fMRI data set.

In this paper we reveal a connection between the coefficients of the morphological wavelet transform and complexity measures of dyadic tree representations of level sets. This leads to better understanding of the edge preserving property that has been discovered in both areas. As an immediate application, we examine a depth-adaptive soft thresholding scheme on morphological wavelet coefficients in which the threshold decays geometrically as the resolution increases. A greater decay rate gives greater preference towards unbalanced trees and this can control edge enhancement in denoised signals.

We propose a two component method for denoising multidimensional signals, e.g. images. The first component uses a dynamic programing algorithm of complexity O (N log N) to find an optimal dyadic tree representation of a given multidimensional signal of N samples. The second component takes a signal with given dyadic tree representation and formulates the denoising problem for this signal as a Second Order Cone Program of size O (N). To solve the overall denoising problem, we apply these two algorithms iteratively to search for a jointly optimal denoised signal and dyadic tree representation. Experiments on images confirm that the approach yields denoised signals with improved PSNR and edge preservation.

Diffusion Maps (DiffMaps) has recently provided a general framework that unites many other spectral manifold learning algorithms, including Laplacian Eigenmaps, and it has become one of the most successful and popular frameworks for manifold learning to date. However, Diffusion Maps still often creates unnecessary distortions, and its performance varies widely in response to parameter value changes. In this paper, we draw a previously unnoticed connection between DiffMaps and spring-motivated methods. We show that DiffMaps has a physical interpretation: it finds the arrangement of high-dimensional objects in low-dimensional space that minimizes the elastic energy of a particular spring network. Within this interpretation, we recognize the root cause of a variety of problems that are commonly observed in the Diffusion Maps output, including sensitivity to user-specified parameters, sensitivity to sampling density, and distortion of boundaries. We then show how to exploit the connection between Diffusion Map and spring criteria to create a method that can be efficiently applied post hoc to alleviate these commonly observed deficiencies in the Diffusion Maps output.

As an alternative to standard PCA, matrix-based image dimensionality reduction methods have recently been proposed and have gained attention due to reported computational efficiency and robust performance in classification. We unify all of these methods through one concept: Separable Principle Component Analysis (SPCA).We show that the proposed matrix methods are either equivalent to, special cases of, or approximations to SPCA. We include performance comparisons of the methods on two face data sets and a handwritten digit data set. The empirical results indicate that two existing methods, BD-PCA and its variant NGLRAM, are very good, efficiently computable, approximate solutions to practical SPCA problems.

We propose a boosting algorithm that seeks to minimize the AdaBoost exponential loss of a composite classifier using only a sparse set of base classifiers. The proposed algorithm is computationally efficient and in test examples produces composite classifiers that are sparser and generalize as well those produced by Adaboost. The algorithm can be viewed as a coordinate descent method for the l1-regularized Adaboost exponential loss function.

We explore sparse regression for effective feature selection and classification in face identity and expression recognition. We argue that sparse regression in pixel space is inappropriate. We propose instead a method which combines the virtues of sparse regression with projection methods such as PCA and FDA. The method can learn a sparse set of discriminative projections and increase recognition accuracy beyond that achievable by FDA.We demonstrate this by performance comparisons on three face data sets.

The inter-subject alignment of functional MRI (fMRI) data is important for improving the statistical power of fMRI group analyses. In contrast to existing anatomically-based methods, we propose a novel multi-subject algorithm that derives a functional correspondence by aligning spatial patterns of functional connectivity across a set of subjects. We test our method on fMRI data collected during a movie viewing experiment. By cross-validating the results of our algorithm, we show that the correspondence successfully generalizes to a secondary movie dataset not used to derive the alignment.

By adding a spatial regularization kernel to a standard loss function formulation of the boosting problem, we develop a framework for spatially informed boosting. From this regularized loss framework we derive an efficient boosting algorithm that uses additional weights/priors on the base classifiers. We prove that the proposed algorithm exhibits a ``grouping effect, which encourages the selection of all spatially local, discriminative base classifiers. The algorithms primary advantage is in applications where the trained classifier is used to identify the spatial pattern of discriminative information, e.g. the voxel selection problem in fMRI. We demonstrate the algorithms performance on various data sets.

We provide a detailed analysis of the use of minimal spanning graphs as an alignment method for registering multimodal images. This yields an efficient graph theoretic algorithm that, for the first time, jointly estimates both an alignment measure and a viable descent direction with respect to a parameterized class of spatial transformations. We also show how prior information about the interimage modality relationship from prealigned image pairs can be incorporated into the graph-based algorithm. A comparison of the graph theoretic alignment measure is provided with more traditional measures based on plug-in entropy estimators. This highlights previously unrecognized similarities between these two registration methods. Our analysis gives additional insight into the tradeoffs the graph-based algorithm is making and how these will manifest themselves in the registration algorithm's performance.

This paper examines the problem of registering images using an information theoretic metric (e.g., entropy) estimated using a Euclidean minimum spanning tree (EMST). The objective is to find an extremum of the metric with respect to a vector of free parameters. One of the major difficulties posed by such graph theoretic metrics is concurrently obtaining gradient information as the metric is computed. Obtaining the gradient is a first step in efficiently optimizing the metric. Our main contribution is to show how to obtain a gradient-based descent direction from the computation of the EMST metric. We also indicate how this can be used for optimizing image registration over a vector set of parameters and provide some preliminary experimental results.

Given a set of synchronized video sequences of a dynamic scene taken by different cameras, we address the problem of creating a virtual video of the scene from a novel viewpoint. A key aspect of our algorithm is a method for recursively propagating dense and physically accurate correspondences between the two video sources. By exploiting temporal continuity and suitably constraining the correspondences, we provide an efficient framework for synthesizing realistic virtual video. The stability of the propagation algorithm is analyzed, and experimental results are presented.

Compared to a geometric approach, image based rendering applied to 3D view reconstruction does not require 3D model construction and does not depend on the complexity of the environment. But the large number of images needed for rendering poses a problem of compression and storage. MPEG style algorithms can be used to efficiently compress the data. If the image set has to be accessed through a communication channel, the available bit rate can become a limiting factor in interactive walkthroughs. As the compressed video stream from an MPEG encoder comprises variable rate traffic, different buffering and prefetching techniques can be used to smooth the data rate and thus efficiently utilize the available bit rate. Many interesting aspects arise due to the 2D nature of the problem.

We demonstrate that in some situations, perceptual quality can be maintained using an approach based on synthesizing "virtual" images of a scene that match frames from a source video clip. We use this algorithm for interpolation of video frames in the time domain, using a small amount of information to construct an approximation of the original video. Our algorithm is well-suited for the limitations in bandwidth and complexity characteristic of wireless multimedia channels. Since the approach is based on estimating functions of the underlying camera motion parameters, it can capture relationships between image correspondences that extend across many (perhaps hundreds) of video frames. Each interpolated image can be rendered using only a few tens of bytes of side information, and the rendering process itself has low computational requirements. We present experimental results to demonstrate that for certain types of video, our algorithm can give significant perceptual improvement over MPEG-4 coded video at the same low bit rate.

The estimation of the parameters of a projective transformation that relates the coordinates of two image planes is a standard problem that arises in image and video mosaicking, virtual video, and problems in computer vision. This problem is often posed as a least squares minimization problem based on a finite set of noisy point samples of the underlying transformation. While in some special cases this problem can be solved using a linear approximation, in general, it results in an 8-dimensional nonquadratic minimization problem that is solved numerically using an 'off-the-shelf' procedure such as the Levenberg-Marquardt algorithm. We show that the general least squares problem for estimating a projective transformation can be analytically reduced to a 2-dimensional nonquadratic minimization problem. Moreover, we provide both analytical and experimental evidence that the minimization of this function is computationally attractive. We propose a particular algorithm that is a combination of a projection and an approximate Gauss-Newton scheme, and experimentally verify that this algorithm efficiently solves the least squares problem.

This paper is concerned with the efficient temporal propagation of correspondences between frames of two video sequences, an integral component of many video processing tasks. The main contribution is a framework for the recursive propagation of these correspondences. The propagation consists of a time update step and a measurement update step. The time update depends only on the dynamics of the rotating source cameras, while the measurement update can be tailored to any member of a general class of image correspondence algorithms. Using these results, the correspondence between points of each frame pair can be propagated and updated in a fraction of the time required to estimate correspondences anew at every frame. We discuss an application of the recursive correspondence propagation framework to the creation of virtual video. Previous virtual view algorithms have been used to generate synthetic video of a static scene, in which objects seem frozen in time. In contrast, the algorithms described here allow the creation of "true" virtual video, in the sense that the synthetic video evolves dynamically along with the scene. While virtual video is our motivating application, the recursive correspondence propagation framework applies to any two-camera video application in which correspondence is difficult and prohibitively time-consuming to estimate by processing frame pairs independently.

The problem of aligning images arises in many applications, such as mosaicing, video stabilization, medical imaging, aerial photography, etc. If the images form a long sequence, then the conventional approach of sequential registration leads to unstable error growth. To avoid this, additional measurements of registration parameters between images in some local neighborhood can be used to limit the error growth and greatly improve the performance. We propose different approaches to the analytical evaluation of the performance of this estimation as a function of the sequence length and the maximum distance of allowed measurements.

As digital video becomes more pervasive, efficient ways of searching and annotating video according to content will be increasingly important. Such tasks arise, for example, in the management of digital video libraries for content-based retrieval and browsing. We develop tools based on camera motion for analyzing and annotating a class of structured video using the low-level information available directly from MPEG-compressed video. In particular, we show that in certain structured settings, it is possible to obtain reliable estimates of camera motion by directly processing data easily obtained from the MPEG format. Working directly with the compressed video greatly reduces the processing time and enhances storage efficiency. As an illustration of this idea, we have developed a simple basketball annotation system which combines the low-level information extracted from an MPEG stream with the prior knowledge of basketball structure to provide high-level content analysis, annotation, and browsing for events such as wide-angle and close-up views, fast breaks, probable shots at the basket, etc. The methods used in this example should also be useful in the analysis of high-level content of structured video in other domains.

The paper presents an approach for region based video mosaicing, treating moving objects separately from the background, and with improved ghost-like noise elimination. The mosaic images show the moving objects superimposed over a stationary background. Conventional technologies can reduce the ghost-like noise that occurs from moving objects by using temporal median filtering, but its efficiency depends on the ratio between the speeds of the camera and the moving object. Our technology eliminates these noises more efficiently by using segmented images of a spatio-temporal video sequence. Segmentation is performed using a novel technique that uses different configurations of quad-trees for the initial separation in the split-and-merge process. The segmented images are also used to display tracked moving objects on the panoramic image.

The usefulness of a video database relies on whether the video of interest can be easily located. To allow exploring, browsing, and retrieving videos according to their visual content, efficient techniques for evaluating the visual similarity between different video clips are necessary. We present a framework for measuring video similarity across different resolutions-both spatial and temporal. In particular, the video clips to be compared can be properly aligned through the use of suitable weighting functions and alignment constraints. Dynamic programming techniques are employed to obtain the video similarity measure with a reasonable computational cost. An application to searching MPEG compressed video by example is presented to demonstrate the potential use of the proposed video similarity measure.

Selecting image features whose correspondences can be accurately established between images is a key step in many image processing problems, such as camera and object motion estimation, 3D structure reconstruction, and image registration. In this paper, we present a new method of selecting good features for estimating motion from images. Our approach is different from other existing approaches in that we formulate feature tracking as a signal parameter estimation problem, give a quantitative measure of feature quality in terms of how accurately the feature can be tracked, and can adaptively select features with different shapes and sizes which depend on the local variations of the images. Through the analysis of this feature quality measure, we can characterize the basic properties that allow a feature to be well tracked. Some experimental results are shown to demonstrate the advantages and robustness of the proposed method.

We derive a six parameter system to estimate and compensate the effects of camera motion-zoom, pan, tilt and swing. As compared to other existing methods, this model describes more precisely the effect of different kinds of camera motions. A recursive least-squares estimator has been used to solve for the motion parameters. Experiments suggest that our algorithm converges to satisfactory results when about 10 pairs of corresponding pairs between two image frames are available.

A discrete event system (DES) is a dynamic system that evolves in accordance with the abrupt occurrence, at possibly unknown irregular intervals, of physical events. Such systems arise in a variety of contexts ranging from computer operating systems to the control of complex multimode processes. A control theory for the logical aspects of such DESs is surveyed. The focus is on the qualitative aspects of control, but computation and the related issue of computational complexity are also considered. Automata and formal language models for DESs are surveyed.>