 |
|
Stochastic
Systems Group |
|
|
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
- Post-Doctoral Research
- Doctoral Students
- Research Summary, Venkat Chandrasekaran
- Research Summary, Lei Chen
- A Multipole-motivated Hierarchical Model for Inference in Large-scale GMRFs, Myung Jin Choi
- Research Summary, Ayres Fan
- Research Summary, Emily Fox
- Tractable Methods for Inference and Learning in Graphical Models, Jason K. Johnson
- Network-constrained decision problems, Patrick Kreidl
- Research Summary, Dmitry Malioutov
- Research Summary, Vincent Tan
- Anisotropy Characterization in Wide-Angle SAR Imaging Using Sparse Signal Approximation, Kush Varshney
- Masters Students
Recent/Past Student/Staff Research Summaries
Research Summary, Jason Williams (completed Ph.D, 1/2007)
- Learning Multiscale Models from Data, Dewey Tucker, Ph.D. Thesis
- Estimation and modeling of stochastic processes defined by graphs, Martin Wainwright, Ph.D. Thesis
- Surface Reflectance Estimation and Real-World Illumination Statistics, Ron Dror, Ph.D. Thesis
- Sensor Arrays and Information Theoretic Fusion, Alex Ihler, Ph.D. Thesis
- Image Segmentation and Deblurring Using Curve Evolution , Junmo Kim, Ph.D. Thesis
- Modeling and Estimation of Gaussian Processes on Graphs with Cycles, Erik Sudderth, Master's Thesis
- Krylov Subspace
Estimation,
Mike Schneider
-
Statistical Methods and Curve Evolution Theory
for Image Segmentation,
Andy Tsai
- Target Model
Generation from Synthetic Aperture Radar Imagery,
John Richards
-
Estimation of Anisotropic Phenomena For
SAR ATR,
Andrew Kim
- An
Estimation-Theoretic Technique for Motion-Compensated
Synthetic-Aperture Array Imaging,
Cedric Logan, Ph.D. Thesis
- A Realization
Theory for Multiscale Autoregressive Stochastic Models
Austin Frakt, Ph.D. Thesis
- Nonlinear Scale
Space Analysis in Image Processing,
Ilya Pollak, Ph.D. Thesis
- Multiscale Estimation
of Large Scale Dynamic Systems,
Terrance Ho, Ph.D. Thesis
-
Multiscale Autoregressive Models and Wavelets,
Khalid Daoudi
- Multiresolution
Statistical Modeling with Application to Modeling Groundwater Flow,
Mike Daniel, Ph.D. Thesis
- Feature Extraction
Using High Resolution Pursuit, Seema Jaggi, Ph.D. Thesis
- Low complexity
optimal joint detection for over-saturated multiple access
communications, Rachel Learned, Ph.D. Thesis
-
Hierarchical Stochastic Modeling for Multiscale Segmentation
and Compression of SAR Imagery,
Andrew Kim, Master's Thesis
- Wavelet Denoising
Techniques with Applications to High-Resolution Radar,
Dewey Tucker, Master's Thesis
- Anomaly Detection
and Localization from Tomographic Data,
Austin Frakt, Master's Thesis
- Multiscale Methods
for the Segmentation of Images, Michael Schneider, Master's Thesis
-
Nonparametric Estimation for Dynamical Systems,
Alex Ihler, Master's Thesis
-
Spatio-Temporal fMRI Signal Analysis Using Information Theory,
Junmo Kim, Master's Thesis
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 Text
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 Text
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 Text
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 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