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>