June
8, 2004
PI Name, Institution: Andrew Knyazev, U of Colorado Denver
Award # 0345173
Technical/Research Summary The proposed innovative basic research
contributes to
national security by providing breakthroughs in technology in data
mining, in
particular, in image segmentation and registration, using the spectral
clustering, a technique of locating clusters in the data using
eigenvalues and
eigenvectors of corresponding correlation matrices, which is related to
the
principal component analysis. The advantage of spectral clustering
compared to
other, more traditional, methods of data mining is its ability to
handle more
efficiently large amounts of data. The main step of spectral clustering is a
construction of an
eigenvalue problem for the corresponding data and the analysis goals
that
determines the accuracy and numerical efficiency of the spectral
clustering practical
implementation. A model for spectral clustering has been developed,
based on a
concept of gravitational vibrations: the data points are associated
with masses
and the correlation between the data points is treated as a gravitation
force.
Low frequency vibrations of the whole system reveal the clusters in the
data
since the data points with higher correlation are associated with
tightly
connected masses that have the tendency to move together, while
uncorrelated
data points correspond to loosely connected masses that tend to move
into the
opposite directions within the low frequency vibration modes. A
negative
correlation can be represented by an antigravitaion force and also
included
into the model. The model naturally leads to a fuzzy clustering which
is
important in applications such as segmentation of images without edges.
Automated image registration is an important
topic of
research with applications, e.g., in geological intelligence. We
propose to
perform the image registration on preconditioned, rather than the
original,
images. For preconditioning, we suggest projecting the original image
on the
fist few eigenfunctions of the matrix that is used in the spectral
image
segmentation, hoping that such a projection removes the noise and image
details
not essential for image registration. Registration of preconditioned
images is
expected to improve stability of registration methods. The final part of the project is to analyze
and test for
spectral clustering the eigenvalue solvers developed by the PI. A
typical
eigenvalue problem in spectral clustering is to compute a few extreme
eigenvalues and corresponding eigenvectors of symmetric matrices of
very large
size. An efficient parallel code for such problems is being developed
as a part
of the LLNL Hypre library. Many parts of the project are work in
progress. The final
results will be available at the PI Web page http://math.ucdenver.edu/~aknyazev/