Sampling, denoising and compression of matrices by coherent matrix organization

The need to organize and analyze real-valued matrices arises in various settings - notably, 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-Holder 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 compression 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 specified mixed-Holder 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. (C) 2012 Elsevier Inc. All rights reserved.