Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

RESEARCH

General Description


(original photo courtesy of Philip Greenspun) 		The focus of our work is on the development of efficient algorithms for signal and image processing problems. More specifically, we address real-world problems with large dimensionality for which computationally efficient data analysis is a primary concern. Such problems arise in a wide range of areas: geophysical inverse problems (oceanography, groundwater hydrology), remote sensing problems (automatic target recognition from synthetic aperture radar), and non-destructive evaluation problems (medical imaging using tomography). We address problems in these areas by applying (1) methods in signal and image processing, (2) the theory of optimal statistical estimation and detection, and (3) multiscale methods. The following reserach summaries provide details on specific projects.

Current Student/Staff Research Summaries

Recent/Past Student/Staff Research Summaries

  • Research Summary, Jason Williams (completed Ph.D, 1/2007)

    • Current Research


    Variational Methods for Array Processing in the Presence of Uncertainties, Mujdat Cetin

    This research addresses sensor array processing problems by using an optimization-based framework. One such problem of interest is source localization in the presence of uncertainties in sensor locations. By exploiting an explicit model of the data collection geometry, sensor parameters, and statistically motivated constraints on the unknowns, the objective is to develop effective and robust variational schemes for information extraction.

    Research Summary, Sujay Sanghavi

    Research Summary Text

    Research Summary, Venkat Chandrasekaran

    Research Summary Text

    Research Summary, Lei Chen

    Research Summary Text

    A Multipole-motivated Hierarchical Model for Inference in Large-scale GMRFs, Myung Jin Choi

    The main focus of this research is developing efficient methods to estimate approximate means and error variances in large-scale Gauss-Markov random fields (GMRFs).   This problem arises in a variety of applications, but it is challenging when the number of variables is large and measurements are noisy and sparse.  The multiscale tree models, developed at SSG,  introduce auxiliary variables which represent the field of interest at coarser resolutions and compute the estimates by passing messages between parent-child pairs, which is highly efficient but results in blocky artifacts in the estimation results.

    I am currently developing a pyramidal graph which allows message passings between neighbors at the same resolution as well as between parent-child pairs.   The inference algorithm on the model is motivated by the multipole method, which uses interactions between particle clusters to evaluate far-field potentials rapidly. Unlike many existing hierarchical models (e.g. multigrid methods), the pyramidal graph forms an MRF, so various techniques developed for efficient inference in graphical models can be applied.   I am also interested in utilizing the pyramidal structure to update the estimates rapidly without restarting the algorithm from scratch when measurements are added or new prior knowledge (e.g. existence of discontinuities in the field) of a local region is provided.

    Research Summary, Ayres Fan

    Research Summary Text

    Research Summary, Emily Fox

    Research Summary Text

    Tractable Methods for Inference and Learning in Graphical Models, Jason Johnson

    Approximate Inference by Recursive Cavity Modeling
    * Recursive cavity modeling (RCM) is an approximate inference method for MRFs that blends exact recursive inference with variational methods that minimize relative entropy. The key idea is to build cavity models of subfields. Each cavity model provides a tractable, approximate model for statistics on the boundary of a subfield that is useful for inference outside of the subfield. Using a nested dissection procedure, these cavity models and a complementary set of blanket models can be built up recursively. Ultimately, this leads to approximate computation of the marginal distribution of each variable in the MRF.
    * Model thinning plays an important role in this approach. This involves selecting a tractable approximation to a given MRF based on a sub-graph of the MRF (e.g., a cavity or blanket model in RCM), which requires both selection of a sub-graph and parameter optimization to minimize relative entropy over the class of MRFs defined on this sub-graph (an information projection). An efficient information projection method was developed using chordal graph embedding and exploiting certain tractable representations of Fisher information for MRFs defined on chordal graphs.

    Maximum-Entroy Relaxation for Learning Graphical Structure
    (with Venkat Chandrasekaran)
    * Maximum entropy relaxation (MER) is a convex optimization approach for thinning MRF models that was originally formulated as a method to select cavity models in the context of Jason's RCM algorithm. The usual approach to model thinning is to select a tractable approximation to a given MRF, based on a sub-graph of the original MRF, which involves both selection of a sub-graph and parameter optimization in the class of MRFs defined on that sub-graph to minimize relative entropy. Because sub-graph selection is combinatorial, the MER approach was formulated as a tractable alternative that simultaneously selects both the sub-graph and corresponding parameters through solution of a convex optimization problem. Formally, we seek to maximize entropy subject to a relaxed set of marginal constraints, which require that the marginals of the relaxed distribution are close to the corresponding marginals in the orginal distribution in the sense of relative entropy.
    * In joint work with Venkat, this idea was formalized in an exponential family representation for Gaussian and Boltzmann models. An approach was developed to solve these problems using a modified primal-dual interior point method, which exploits sparsity of Fisher information in chordal MRFs, and an incremental method for identifying the active set of constraints in the MER problem.

    Lagrangian Relaxation for Intractable Graphical Models
    (with Dmitry M. Malioutov)
    Lagrangian relaxation (LR) is an approximate method to estimate the most probable configuration of an intractable MRF. LR is formulated with respect to an augmented graphical model, which includes replicas of the nodes and edges of the original graph. By dualizing the constraint that replicated variables (and, more generally, replicated features) must be equal in any valid assignment, we obtain a relaxed, convex "dual" problem, which is tractable to solve provided the augmented graph has a low tree width. In particular, if the augmented graph is chosen to correspond to a set of spanning trees of the original graph, then we recover essentially the same formalism as in the tree-reweighted max-product approach developed by Martin Wainwright. More generally, we allow relaxations based on small sub-graphs, narrow sub-graphs, "unwound" computation trees and multiscale representations. These extensions can lead to reduced duality gaps and faster convergence in the iterative methods used to solve the dual problem.

    Walk-Sum Analysis for Gaussian Graphical Models
    (with Dmitry M. Malioutov, Venkat Chandrasekaran)
    An interesting spin-off of Jason's work in GMRFs has been the novel walk-sum interpretation of inference in Gaussian graphical models. In a technical report, Jason introduced the class of walk-summable models; characterized some important, easily identified sub-classes of these models and provided a walk-sum analysis of certain iterative estimation algorithms, namely, the Gauss-Jacobi iteration, the (stationary) embedded-tree (ET) algorithm and a special-case of the cyclic, two-tree ET iteration. Later on, in joint work with Dmitry Malioutov, this picture was further refined and applied to give a new interpretation of Gaussian belief propagation, which was therefore shown to converge in walk-summable models. Later still, Venkat and Jason generalized the walk-sum interpretation of ET to a much broader class of algorithms, including iterations based on arbitrary (non-cyclic) sequences of tractable sub-graphs.

    Network-constrained decision problems, O. Patrick Kreidl

    This research addresses a fundamental class of statistical decision problems (e.g., large-scale hypothesis-testing) under the assumptions that measurements are distributed over multiple sensors and there exist explicit costs or constraints on the available algorithmic resources (e.g., computation, communication, memory). Such assumptions apply in a variety of forward-looking engineering developments, including (1) wireless sensor networks, in which every symbol exchanged is a power drain and brings the communicating nodes closer to expiration, and (2) real-time network security, in which extremely fast sensing rates and quality-of-service objectives at each node can tolerate only minimal computation/memory per cycle. Our work extends the models and methods at the intersection of team decision theory and graph-based probabilistic inference, culminating in a new class of efficient message-passing algorithms to be executed "offline" (i.e., before processing measurements) by which the nodes "self-organize" (i.e., iteratively couple the parameters of their local processing rules) in order to mitigate the loss in performance resulting from the explicit "online" resource constraints (i.e., the constraints when making decisions from measurements).

    Research Summary, Dmitry Malioutov

    Research Summary Text

    Research Summary, Vincent Tan

    I have been working on the use of convex optimization and information theoretic techniques to learn probabilistic graphical models for the specific purpose of hypothesis testing/classification. This work has been extended to sequentially and jointly learning increasingly complex probability models defined on graphical models for discriminating between two hypotheses. The formulation is based on successively maximizing a symmetrized version of the KL divergence, which provide bounds on the probability of error. Recently, I have also looked at sequential querying of random variables defined on a graph for optimal hypothesis testing.

    Anisotropy Characterization in Wide-Angle SAR Imaging Using Sparse Signal Approximation, Kush Varshney

    Imagery formed from wide-angle synthetic aperture radar (SAR) measurements has fine cross-range resolution in principle. However, conventional SAR image formation techniques assume isotropic scattering, which is not valid with wide-angle apertures.  Also, the spatial location of scattering centers may migrate as a function of viewing angle across the aperture. The problem of jointly forming images and characterizing anisotropy as well as characterizing scattering center migration in wide-angle SAR is considered in the research. The approach not only compensates for anisotropy and migration in the image formation process, but gives much more information, useful for scene interpretation, than a simple image would. 

    A method based on a sparse representation of anisotropic scattering with an overcomplete dictionary composed of atoms with varying levels of angular persistence is presented. Solved as an inverse problem, the result is a complex-valued, aspect-dependent response for each scatterer in a scene. The non-parametric approach jointly considers all scatterers within one system of equations.  The choice of the overcomplete dictionary incorporates prior knowledge of anisotropy, but the method is flexible enough to admit solutions that may not match a family of parametric functions. Sparsity is enforced through regularization based on the l_p quasi-norm, p<1, leading to a non-convex minimization problem. A quasi-Newton method is applied to the problem and a novel graph-structured algorithm is developed and also applied. Results are demonstrated on synthetic examples and realistic examples with XPatch data, including the backhoe public release dataset.

    Recent/Past Research


    Research Summary, Jason L. Williams

    Research Summary Text

    Multiresolution Modeling from Data and Partial Specifications, D. Tucker

    In this research, we study a recently developed class of models, called multiscale models, which is well-suited to represent a wide variety of random processes. The advantage of this type of model is in providing an extremely efficient estimation algorithm which is a generalization of the traditional Kalman filter and Rauch-Tung-Striebel smoother. Multiscale models and the associated estimation algorithm have been shown to be useful in a number of applications including image processing, remote sensing, and geophysics.

    In particular, we focus on the problem of constructing multiscale models from data and partial covariance information. Previous research in this area has provided an algorithm which builds a multiscale model to match the covariance of a given process of interest. However, this approach requires complete knowledge of the covariance and the capability to store it, and for problems of even moderate size, this type of complete characterization is an overwhelmingly large data storage problem. To circumvent this problem, we seek methods to construct multiscale models based solely on realizations (sample paths) of the process, with no assumed knowledge of the covariance. In addition, we examine the problem of positive definite covariance extension with the specific goal of constructing multiscale models from partial covariance information.

    Estimation and modeling of stochastic processes defined by graphs, Martin Wainwright

    In broad overview, I am interested in stochastic processes defined by graphical models, and associated problems of modeling and estimation. The nodes of a singly-connected graphs (i.e., trees) can be partially ordered in scale, which gives rise to powerful algorithms for many problems. In contrast, straightforward solution to these same problems are prohibitively complex for more general graphs of any substantial size. As a result, there is considerable interest in developing tractable techniques for graphs with loops. More specifically, I am currently working on the following problems:
    (a) an embedded trees (ET) algorithm for exact estimation of Gaussian processes on graphs with cycles. [Work with Erik Sudderth & Alan Willsky. Abstract / Full Text (70K  ps.gz) / Full Text (1.4M  pdf)
    (b) techniques for approximate estimation of discrete processes on graphs with cycles. [Report in preparation. Work with Tommi Jaakkola and Alan Willsky].
    (c) modeling natural image statistics with random cascades of Gaussian scale mixtures on graphical models, and their application to image processing problems. [Work with Eero Simoncelli & Alan Willsky] Abstract / Full Text (236K  ps.gz) / Full Text (3M  pdf)

    Surface Reflectance Estimation and Real-World Illumination Statistics. Ron O. Dror

    How do you tell a sheet of white paper from a polished mirror given a single photograph of each surface in unknown surroundings? In principle, the mirror could look exactly like any other surface; after all, it just reflects its surroundings. In practice, humans can differentiate mirrors and paper surfaces so easily that we often take that ability for granted. In the real world, illumination is not arbitrary. Humans recognize the mirror because it reflects the world, and they know in some statistical sense what the world looks like. Humans also know what paper, rough metal, or shiny plastic look like under real-world illumination conditions.

    Alan Willsky, Eward Adelson, and I are building a computer vision system with a similar ability to recognize surface reflectance properties under unknown illumination. Our current system applies machine learning techniques to identify relationships between surface reflectance and the wavelet statistics of appropriately warped surface images. Such algorithms will allow computer visions systems to recognize materials and to estimate shape and motion more robustly. They may also provide a convenient method to capture surface properties essential to realistic computer graphics.

    In parallel with this work, I am collaborating with Roland Fleming in the Brain and Cognitive Sciences Department to elucidate the mechanisms which humans use to recognize surface reflectance and material properties. I have also worked with Thomas Leung, now at Fuji, to characterize the statistical regularities of real-world illumination.

    Sensor Arrays and Information Theoretic Fusion, Alex Ihler

    Large arrays of sensors with overlapping regions of influence and multiple sensing modalities pose new problems in data fusion. Complex relationships between the sensor observations, including reflections and nonlinear effects, make it difficult to determine such quantities as number, location, and characteristics of sources, and even the sensor array configuration. This is related to such problems as ICA (independent component analysis), sensor fusion, and more standard array processing problems like finding direction of arrival. Our approach uses nonparametric estimates of mutual information (see Masters work) to attempt to determine relationships between sensors, and frame the extraction of the original sources as an ICA-like problem. This research is part of the SensorWeb project.

    Image Segmentation and Deblurring Using Curve Evolution, Junmo Kim

    Image segmentation has been an important problem in image processing and computer vision. One of the problems we are working on is to perform segmentation and deblurring of a given image, which is obtained by blurring an unknown original image with a known blurring operation and by adding white Gaussian noise to the blurred image. The segmentation and deblurring is performed simultaneously by minimizing the Mumford-Shah functional, which is designed to get a piecewise smooth deblurred image and its edges. Minimizing the Mumford-Shah functional corresponds to evolving a curve to the boundaries of piecewise smooth regions and the curve evolution is implemented using Level Set method, which automatically handles topological changes of the image boundaries.

    Other relevant problems include development of information theoretic approach to image segmentation using nonparametric statistics, segmentation of textured images, and development of a mathematically sound shape prior.


    Modeling and Estimation of Gaussian Processes on Graphs with Cycles, Erik Sudderth

    Statistical models of two-dimensional fields play an important role in a variety of application areas, from oceanography to image processing. Markov random fields, perhaps the most common means of representing a two-dimensional random process, have an intuitively appealing structure, but they generally lead to computationally intensive estimation algorithms. The multiscale tree models previously introduced by the Stochastic Systems Group provide highly efficient estimation procedures. The fundamental source of the efficiency of tree-based algorithms is that there is a single unique path between any two points in the tree - in other words, there are no loops. Unfortunately, the tree structure also tends to lead to blocky artifacts in the final estimation results.

    My research involves the investigation of model structures that lie in between densely connected Markov random fields and singly connected multiscale trees. We have developed a novel estimation algorithm which computes the exact means and error covariances for Gaussian estimation problems on arbitrary cyclic graphs. It works by exploiting the presence of tree-like structures in more densely connected graphs. Current work focuses on obtaining a deeper understanding of this algorithm's dynamics, and on determining efficient procedures for constructing models on graphs with cycles.

    Krylov Subspace Estimation, M. Schneider

    Computing the linear least-squares estimate of a high-dimensional random quantity given noisy data requires solving a large system of linear equations. In many situations, one can solve this system efficiently using the conjugate gradient (CG) algorithm. Computing the estimation error variances is a more intricate task. It is difficult because the error variances are the diagonal elements of a complicated matrix. This research is focused on developing a method for using the conjugate search directions generated by the CG algorithm to obtain a converging approximation to the estimation error variances. The algorithm for computing the error variances falls out naturally from a novel estimation-theoretic interpretation of the CG algorithm. Preliminary results indicate that the algorithm is effective for many problems requiring the estimation of processes evolving in space or time.

    Statistical Methods and Curve Evolution Theory for Image Segmentation, A. Tsai

    Image segmentation--the process of grouping image data into meaningful regions--is a fundamental and challenging problem in early vision with important applications to medical diagnosis, remote sensing, product quality inspection, motion analysis and tracking, autonomous vehicle navigation, and so forth. Generally, image segmentation is the first and most difficult task of any automated image understanding process. During image segmentation, each meaningful region formed can be set apart from the rest based on some defining features that are unique to that particular region. The defining features of each region manifest themselves in a variety of ways including, but not limited to, intensity, color, surface luminance, and texture. In recent years, segmentation algorithms based on either curve evolution techniques or statistical methods have received considerable attention. Curve evolution techniques for image segmentation involve the evolution of curves according to prescribed partial differential equations (PDEs) whereas statistical methods for image segmentation entail stochastic models and estimation-theoretic techniques. The statistical methods we focus on include multiscale models and estimators, the EM algorithm, and approximation schemes derived from mean field theory. The broad objective is to develop novel image segmentation algorithms for a variety of different applications (e.g. prostate segmentation for MRI-guided prostate brachytherapy or laser radar range profiling, anomaly suppression, and target detection) based on statistical methods and curve evolution techniques.

    Target Model Generation from Synthetic Aperture Radar Imagery, J. A. Richards

    Automatic target recognition (ATR) systems are often designed to be used in conjunction with synthetic aperture radar (SAR) imaging systems to detect and classify targets of interest. A prerequisite for the operation of a model-based ATR system is the existence of a database containing models of targets that might be encountered in SAR imagery. Unfortunately, the generation of models to populate the ATR database is typically a tedious and difficult task, often requiring detailed descriptions of targets in the form of blueprints or CAD models. Recently, efforts to generate models from a single 1-D radar range profile or a single 2-D SAR image have met with some success. However, the models generated from these data sets are of limited use to most ATR systems because they are not three-dimensional. The goal of my research is twofold: to develop a method for generating or updating 3-D target models directly from multiple SAR images, and more generally, to understand and to characterize the context in which this model generation takes place, in terms of the observability and robustness of the elemental components that form the target models.

    Estimation of Anisotropic Phenomena For SAR ATR, A. J. Kim


    An Estimation-Theoretic Technique for Motion-Compensated Synthetic-Aperture Array Imaging, C. L. Logan

    Synthetic-Aperture Radar (SAR), as an imaging technique, achieves high azimuth resolution by exploiting the relative motion between the airborne/spaceborne radar antenna and the target field. This is carried out through coherent processing of the returned radar signals, effectively synthesizing the effect of a larger aperture array. However, any imprecision on the motions of either the antenna or the target field will cause current SAR processing techniques to exhibit undesirable blurring and object-displacement artifacts. Here, we present an estimation-theoretic approach, in which we view the motion-compensated SAR problem as that of transmitting an image over a dispersive channel, where the actual target field is the transmitted data, and the final SAR image is the received data. The dispersion for each scatterer pixel is directly dependent upon the scatterer velocity.

    We also present a new SAR processing technique for alleviating motion effects. Our proposed approach may be viewed as a multi-dimensional matched-filter, whose parameters are determined by the relative motion between the SAR antenna and the target. In the fore-described framework, this technique is equivalent to developing a model for the motion-dependent dispersion, and incorporating it into the receiver. In contrast to similar multi-dimensional matched-filter methods, we propose a fast and easily implementable solution.

    A Realization Theory for Multiscale Autoregressive Stochastic Models, A. Frakt

    In a wide range of applications there is a need for fast and accurate processing of one- and two-dimensional data. These applications may pose challenges due to a number of factors: (1) the data sets may be large; (2) the data may be non-stationary, sparse, or non-local; (3) the underlying process to be estimated may have correlations at multiple scales; (4) there is often a desire to fuse data representing measurements at multiple resolutions. A recently introduced class of multiscale autoregressive models indexed by trees addresses the above challenges and admits an efficient estimator which provides estimation error statistics for free. These multiscale models are direct generalizations of standard autoregressive state-space models and the efficient estimator is a generalization of the Kalman filter and the Rauch-Tung-Striebel smoother.

    To reap these benefits of the multiscale framework one must first design an appropriate model. Specifically, one must translate a conventional prior to a multiscale prior. This is the multiscale stochastic realization problem and it is a generalization of the standard autoregressive state-space stochastic realization problem. Finding efficient ways to build exact and reduced order multiscale models from conventional second-order characterizations of signals images is the focus of my research.

    Nonlinear Scale Space Analysis in Image Processing, I. Pollak

    Image filtering with nonlinear partial differential equations (PDEs) is a relatively young but quickly growing field. I am interested in its applications to segmentation, noise removal, and de-blurring. The general premise here is to pretend that the image to be processed is the initial condition of a PDE evolving in time. Then the output is the solution to the PDE at some positive time instant. Various equations have been proposed that smooth out noise while preserving the edges. In my thesis, a new family of evolution equations is proposed. They erode edges until, ultimately, every edge disappears, but no blurring happens in the process. Thus, the evolution automatically generates a multiscale family of segmentations. The algorithm can be generalized to vector-valued (e.g., color) images. It can be shown that, in 1-D, the algorithm finds the maximum likelihood solutions to certain change detection problems. A slightly more detailed summary of my research, as well as some thoughts on future research directions, can be found at http://ssg.mit.edu/group/ilya/research.ps. My papers are at http://ssg.mit.edu/group/ilya/ilya.shtml.

    Multiscale Estimation of Large-Scale Dynamic Systems, T. Ho

    The estimation of large-scale dynamic systems finds numerous important scientific and engineering applications, e.g., remote sensing data assimilation and image processing. Conventional linear least-squares methods, such as the Kalman filter, are impractical due to their high computational complexity and data storage requirements. A computationally efficient multiscale estimation framework developed at SSG has been successfully applied to a variety of large-scale static estimation problems. The main objective of my thesis is the extension of this multiscale methodology to dynamic systems.

    In a manner analogous to the propagation of the error covariances in the discrete-time Kalman filter, our proposed iterative estimation algorithm implicitly propagates a multiscale model of the estimation errors through the successive prediction and update steps. For certain dynamic systems, such as 1-D diffusion which has simple dynamics and whose estimation error process can be succinctly, albeit approximately, modeled on multiscale trees, our algorithm can achieve a computational complexity of O(N logN). The adaptation of this algorithm to 2-D systems, and its application to optimal flow and ocean data assimilation problems are currently under investigation.


    Multiscale Autoregressive Models and Wavelets, K. Daoudi

    The multiscale autoregressive (MAR) framework was introduced to support the development of optimal multiscale statistical signal processing. Its power resides in the fast and flexible algorithms to which it leads and to its ability to simultaneously address several complications which arise in a variety of signal processing applications. For instance, the data sets can be large, the processes to be estimated can be non-stationary, the measurements may be irregularly spaced, non-local, and corrupted by non-stationary noise. While the MAR framework was originally motivated by wavelets, the link between these two worlds has been previously established only in the simple case of the Haar wavelet.

    In a recent work we provided, in the 1D case, a unification of the MAR framework and all compactly supported wavelets (orthogonal and biorthogonal) through the notion of "internality" (an internal MAR process is a MAR process for which each state is a linear functional of the finest scale process). We also provided a new view of the multiscale stochastic realization problem which is to design coarse-scale states to match some given fine-scale statistics. This new view consists in restricting the class of linear functionals that define the states of an internal MAR process to the small but rich class of wavelet bases. Our approach is not only computationally fast, but it provides a systematic way to build MAR states that have meaningful and useful structure and are not tied directly to the intricate details of the process being modeled (as previous approaches do). The idea of selecting the linear functionals from a library is an extremely important one in many applications such as data fusion problems in which data are available at several resolutions. We are currently extending this work to the two-dimensional case.


    Multiresolution Statistical Modeling with Application to Modeling Groundwater Flow, Mike Daniel

    The development of accurate mathematical models describing the flow of groundwater is an important problem due to the prevalence of contaminants in or near groundwater supplies. An important parameter of these models is hydraulic conductivity, which describes the ability of the subsurface geology to conduct water flow. Because hydraulic conductivity is a function of the earth's subsurface, direct measurements can be made only at a relatively small number of locations. Instead, one must rely on indirect measurement sources, which supply observations of conductivity at different locations and resolutions. An important problem is to estimate the hydraulic conductivity function from all available data, and to characterize the remaining uncertainty. The class of multiscale processes introduced in [Chou et al., 1994] appears to be well-suited to this problem, since these processes can be estimated efficiently at every scale at which they are modeled; the multiscale estimator also provides an uncertainty measure for the estimates. However, this multiscale framework has some limitations that must be overcome before it can be applied to general data fusion problems. First, because all of the previous applications have focused on the measurement and estimation of the finest-scale process, arbitrary nonlocal properties of interest (e.g., coarse-resolution measurements of hydraulic conductivity) have not been represented within the multiscale framework. Second, the class of stochastic processes that is well modeled by low-order tree models has not been fully characterized. To address the first limitation, this thesis (1) extends multiscale realization theory so that coarse-scale variables can represent particular nonlocal properties to be measured or estimated and (2) applies these realization algorithms to the estimation of hydraulic conductivity from sparse measurements made at different resolutions. To partially address the second limitation, the multiscale processes are shown to provide natural approximations of fractional Brownian motion. These approximations are based on the observation that the multiscale realization problem can be considerably simplified when modeling random processes that are statistically self-similar and/or have stationary increments.

    Feature Extraction Using High Resolution Pursuit, Seema Jaggi

    Feature extraction from one and two-dimensional signals is an important step in model-based object recognition. Model-based object recognition is currently the focus of much work in computer vision. One reason for this is that object recognition has applications in many varied fields including military, medical, and industrial. Model-based object recognition is performed by comparing a given data image to a set of model images and determining which model image the data image most closely resembles. While a pixel-by-pixel comparison of the object and model is possible, it is generally unreliable since the pixelated model provides only one specific instance of the model. Small errors in the sensor geometry or small changes in the object can result in misclassification. Instead, significant features are extracted from both the object and the model, and recognition is performed by comparing these object and model features.

    Low complexity optimal joint detection for over-saturated multiple access communications, Rachel Learned

    Optimal joint detection for interfering (non-orthogonal) users in a multiple access communication system has, in general, a computational complexity which is exponential in the number of users. For this reason, optimal joint detection has been thought impractical for large numbers of users. A number of sub-optimal low complexity joint detectors have been proposed for direct sequence spread spectrum user waveforms which have properties suitable for mobile cellular and other systems. There are, however, other systems, such as satellite systems, for which other waveforms may be considered. This thesis shows that there are user signature set selections which enable optimal joint detection that is extremely low in complexity. When a hierarchical cross-correlation structure is imposed on the user waveforms, optimal detection can be achieved with a tree-structured receiver having complexity that is, in typical cases, a low-order-polynomial in the number of users. This is a huge savings over the exponential complexity needed for the optimal detection of general signals.

    Work in recent literature has shown that a hierarchically structured signal set can achieve over-saturation (more users than dimensions) with no growth in required signal-to-noise ratio. The proposed tree detector achieves low complexity optimal joint detection even in this over-saturated case.

    In this thesis the optimal one-shot tree joint detector is derived for the rare scenario of all user signatures (including phases) exactly known at the receiver and its behavior in non-ideal conditions is examined via simulation. For the more realistic case of having an unknown or a partially known phase at the receiver the optimal one-shot tree joint weight/phase estimator is derived and its performance capabilities are studied through simulations. Three procedures that take advantage of having a sequence of symbol frames are proposed: the optimal joint weight/phase sequence estimator, the multi-frame phase estimate average, and the multi-frame recursive phase estimate.

    Hierarchical Stochastic Modeling for Multiscale Segmentation and Compression of SAR Imagery, A. Kim

    There has recently been a growing interest in Synthetic Aperture Radar (SAR) imaging on account of its importance in a variety of applications. One reason for its gain in popularity is its ability to image terrain at extraordinary rates. Acquiring data at such rates, however, has drawbacks in the form of exorbitant costs in data storage and transmission over relatively slow channels. To alleviate these and related costs, we are developing a segmentation driven compression technique using hierarchical stochastic modeling within a multiscale framework. Our approach to SAR image compression is unique in that we exploit the multiscale stochastic structure inherent in SAR imagery. This structure is well captured by a set of scale auto-regressive (AR) models that accurately characterize the evolution in scale of homogeneous regions for different classes of terrain. We thus associate with each major classification of terrain, a predetermined AR model reflecting the terrain's evolution in scale. A segmentation of SAR imagery is then generated by using a statistical test to compare the local scale evolution behavior within an image to the predefined AR models. The segmentation is subsequently used in tandem with the corresponding models in a pyramid encoder to provide a robust spatially adaptive compression technique that hierarchically encodes both the segmentation and the image.

    Wavelet Denoising Techniques with Applications to High-Resolution Radar, D. Tucker

    The classical estimation problem, that of estimating an unknown signal in additive noise, has recently been revisited by researchers. Wavelets and wavelet packets can be attributed to the resurgence of interest in this area. One of the most significant properties of wavelets, which we exploit, is their ability to represent signals in a given smoothness signal class with very few large magnitude coefficients. In this research, we find an ``optimal'' representation of a given signal in a wavelet packet tree, such that removing noisy coefficients at a given threshold improves the signal quality and minimizes the error in reconstructing the signal. To apply these denoising techniques, we seek a methodology that will extract significant features from high-resolution radar (HRR) returns for the purpose of Automatic Target Recognition (ATR). HRR profiles are one-dimensional radar returns that provide a ``fingerprint'' of a target. Using returns from a particular target, we create a database that contains signals representative of the target at different azimuth and elevation angles, and the database is extended to include many possible targets. The ATR problem then reduces to a database search procedure in order to determine a target's identity and spatial orientation.

    Anomaly Detection and Localization from Tomographic Data, A. Frakt

    The primary focus of my work in this domain is on an efficient multiscale approach to the problems of anomaly detection and localization from noisy tomographic data. These are characteristic of a class of problems which cannot be optimally solved because they involve hypothesis testing over hypothesis spaces with extremely large cardinality. For my Master's Thesis work, I have applied what I call a multiscale hypothesis testing approach to the anomaly detection and localization problems.

    A multiscale hypothesis test is a hierarchical sequence of composite hypothesis tests which discards large portions of the hypothesis space with minimal computational burden and zooms in on the likely true hypothesis. For the anomaly detection and localization problems, hypothesis zooming corresponds to spatial zooming---anomalies are successively localized to finer and finer spatial scales. The key challenges include how to hierarchically divide a large hypothesis space and how to process the data at each stage of the hierarchy to decide which parts of the hypothesis space deserve more attention. The former has been addressed by others. For the latter, a non-linear optimization problem is posed and solved for a decision statistic which maximally disambiguates composite hypotheses. With no more computational complexity, this optimized statistic shows substantial improvement over conventional approaches.

    Multiscale Methods for the Segmentation of Images, M. Schneider

    Segmenting an image based on gradient information is a difficult problem that has been attacked from several angles. One common method of approaching segmentation is to introduce a cost functional which one minimizes over an edge map and a piecewise smooth approximating surface. Finding the minimum provides one with a segmented image. This minimum is typically found by simulating a differential equation. Alternatively, recursive estimation algorithms can be used to compute the minima of many types of cost functionals. Such algorithms not only compute minima quickly, they also calculate error statistics in the process. This research investigates the use of multiscale estimation algorithms to compute segmentations of images.

    Nonparametric Estimation for Dynamical Systems, Alex Ihler

    Often, real world problems have dependancies which are not easily captured by canonical models. Nonlinear systems, or nongaussian uncertainty properties, often give rise to such systems. Nonparametric estimates (eg Parzen density estimation) are capable of capturing a wealth of complex relations, but their high computational cost makes them impractical at high dimensions. Dynamical systems can have long past dependence (and thus require high dimensional observations) yet be highly structured (having a low intrinsic dimension). We would like to capture the power of a nonparametric estimate while being able to constrain the computational cost. By nonparametrically estimating the joint pdf of a function of the past (eg neural net) and the system's future samples, while training the function based on its estimated entropy, we can find maximally informative statistics and characterize not only their relation to the future but an estimate of our uncertainty (noise dynamics, state changes, etc). At the same time, by controlling the output dimension of the function and doing all estimates in the output space, we can control our computational cost.

    Spatio-Temporal fMRI Signal Analysis Using Information Theory, Junmo Kim

    Functional MRI is a fast brain imaging technique which measures the spatio-temporal neuronal activity. The development of automatic statistical analysis techniques which calculate brain activation maps from fMRI data has been a challenging problem due to the limitation of current understanding of human brain physiology. In previous work a novel information-theoretic approach was introduced for calculating the activation map for fMRI analysis [Tsai et al, 1999]. In that work the use of mutual information as a measure of activation resulted in a nonparametric calculation of the activation map. Nonparametric approaches are attractive as the implicit assumptions are milder than the strong assumptions of popular approaches based on the general linear model popularized by Friston et al [1994]. Here we show that, in addition to the intuitive information-theoretic appeal, such an application of mutual information is equivalent to a hypothesis test when the underlying densities are unknown. Furthermore we incorporate local spatial priors using the well-known Ising model thereby dropping the implicit assumption that neighboring voxel time-series are independent. As a consequence of the hypothesis testing equivalence, calculation of the activation map with local spatial priors can be formulated as mincut/maxflow graph-cutting problem. Such problems can be solved in polynomial time by the Ford and Fulkerson method. Empirical results are presented on three fMRI datasets measuring motor, auditory, and visual cortex activation. Comparisons are made illustrating the differences between the proposed technique and one based on the general linear model.



    Problems with this site should be emailed to jonesb@mit.edu