Tel Aviv University
 School of Mathematical Sciences
   Applied Mathematics Seminar
 
Date:          Tuesday June 19, 2012, 15:10
Place:           Schreiber Bldg, Room 309
 
Speaker: Matan Gavish
        Stanford University
 
Title: Sampling, Denoising and Compression of Matrices by Coherent Matrix
Organization.
 
Abstract:
 
The need to organize and analyze real-valued matrices arises in data
analysis (where matrices are multivariate data sets) and in numerical
analysis (where matrices represent linear operators). We provide a formal
framework for matrix organization and subsequent analysis. A matrix is
organized by providing two metrics, one on the column set and one on the row
set. An organization is "coherent" if matrix entries can be predicted from
close-by entries, or formally, if the matrix is Mixed Holder in the two
metrics. Coherent matrix organization becomes computationally feasible and
theoretically tractable by focusing on special metrics, induced by
hierarchical partition trees on the row and column sets. Finding an
organization then reduces to performing simultaneous row-column hierarchical
metric vector quantization of the matrix. Building on an orthogonal "Haar"
transform for matrix space induced by a partition tree pair, we characterize
the Mixed-H older matrix class in terms of tensor product wavelet
coefficient decay and calculate its n-width.
 
We also provide procedures for constructing coherent organizations and show
how to quantitatively compare candidate organizations for a given matrix. We
use the Haar transform to provide optimal sampling, approximation and com-
pression algorithms for coherently organized matrices, proving that they can
be substantially subsampled. When a matrix is noisy and cannot be organized
so as to achieve a specifed Mixed-H older smoothness, we show that under an
easy to check condition of Besov-space type, it can be decomposed as a sum
of a coherent matrix, with the specified Mixed-Holder smoothness, and a
noisy or incoherent matrix with few nonzero entries.
 
Joint work with Ronald Coifman (Yale) and Boaz Nadler (Weizmann).
 
Reading:
 
- Sampling, denoising and compression of matrices by coherent matrix
organization, to appear in ACHA
 
- Harmonic Analysis of Digital Data Bases in: Wavelets and Multiscale
Analysis, Birkhauser 2011
 
- Multiscale Wavelets on Trees, Graphs and High Dimensional Data, ICML 2010
All available at  <http://gavish.web.stanford.edu>
 
______________________________________________________________________
 
Dr. Adi Ditkowski                                                     |
Department of Applied Mathematics                                     |
School of Mathematical Sciences          phone:  972-3-640-5987       |
Tel Aviv University,                     fax  :  972-3-640-9357       |
Tel Aviv, 69978 Israel                   email:   <adid@post.tau.ac.il>  |
______________________________________________________________________
 
---------------------------------------------------------
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Adi Ditkowski   <adid@post.tau.ac.il>