Samplets: A new paradigm for data compression
In this article, we introduce the concept of samplets by transferring the construction of Tausch-White wavelets to the realm of data. This way we obtain a multilevel representation of discrete data which directly enables data compression, detection of singularities and adaptivity. Applying samplets to represent kernel matrices, as they arise in kernel based learning or Gaussian process regression, we end up with quasi-sparse matrices. By thresholding small entries, these matrices are compressible to O(N log N) relevant entries, where N is the number of data points. This feature allows for the use of fill-in reducing reorderings to obtain a sparse factorization of the compressed matrices. Besides the comprehensive introduction to samplets and their properties, we present extensive numerical studies to benchmark the approach. Our results demonstrate that samplets mark a considerable step in the direction of making large data sets accessible for analysis.
Code (0)
등록된 구현이 없습니다.
Tasks
Data CompressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Construction of generalized samplets in Banach spaces
Recently, samplets have been introduced as localized discrete signed measures which are tailored to an underlying data set. Samplets exhibit vanishing moments, i.e., their measure integrals vanish for all polynomials up …
Data CompressionSamplet basis pursuit: Multiresolution scattered data approximation with sparsity constraints
We consider scattered data approximation in samplet coordinates with $\ell_1$-regularization. The application of an $\ell_1$-regularization term enforces sparsity of the coefficients with respect to the samplet basis. Sa…
Data CompressionSurface ReconstructionBespoke multiresolution analysis of graph signals
We present a novel framework for discrete multiresolution analysis of graph signals. The main analytical tool is the samplet transform, originally defined in the Euclidean framework as a discrete wavelet-like constructio…
Multiresolution kernel matrix algebra
We propose a sparse algebra for samplet compressed kernel matrices, to enable efficient scattered data analysis. We show the compression of kernel matrices by means of samplets produces optimally sparse matrices in a cer…
Constructing Gaussian Processes via Samplets
Gaussian Processes face two primary challenges: constructing models for large datasets and selecting the optimal model. This master's thesis tackles these challenges in the low-dimensional case. We examine recent converg…
Gaussian Processesregression