Reduced basis decomposition: a certified and fast lossy data compression algorithm

DOI10.1016/J.CAMWA.2015.09.023MaRDI QIDQ2006533zbMATH OpenOpenAlexFDO

Authors Yanlai Chen

Publication date 11 October 2020

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.05947

zbMATH Keywords

data mininggreedy algorithmlossy compressionreduced basis methodsingular value decomposition

Mathematics Subject Classification ID

Numerical linear algebra (65F99) Computing methodologies for image processing (68U10)

Abstract: Dimension reduction is often needed in the area of data mining. The goal of these methods is to map the given high-dimensional data into a low-dimensional space preserving certain properties of the initial data. There are two kinds of techniques for this purpose. The first, projective methods, builds an explicit linear projection from the high-dimensional space to the low-dimensional one. On the other hand, the nonlinear methods utilizes nonlinear and implicit mapping between the two spaces. In both cases, the methods considered in literature have usually relied on computationally very intensive matrix factorizations, frequently the Singular Value Decomposition (SVD). The computational burden of SVD quickly renders these dimension reduction methods infeasible thanks to the ever-increasing sizes of the practical datasets. In this paper, we present a new decomposition strategy, Reduced Basis Decomposition (RBD), which is inspired by the Reduced Basis Method (RBM). Given $X$ the high-dimensional data, the method approximates it by $Y,T(approxX)$ with $Y$ being the low-dimensional surrogate and $T$ the transformation matrix. $Y$ is obtained through a greedy algorithm thus extremely efficient. In fact, it is significantly faster than SVD with comparable accuracy. $T$ can be computed on the fly. Moreover, unlike many compression algorithms, it easily finds the mapping for an arbitrary ``out-of-sample vector and it comes with an ``error indicator certifying the accuracy of the compression. Numerical results are shown validating these claims.

Recommendations

• A randomized generalized low rank approximations of matrices algorithm for high dimensionality reduction and image compression.
• Linear low-rank approximation and nonlinear dimensionality reduction
• A numerical study of efficient sampling strategies for randomized singular value decomposition
• Fast approximate truncated SVD.
• Randomized Dynamic Mode Decomposition

Cites work

• ``Natural norm a posteriori error estimators for reduced basis approximations
• A priori convergence theory for reduced-basis approximations of single-parameter elliptic partial differential equations
• An `empirical interpolation' method: Application to efficient reduced-basis discretization of partial differential equations
• Certified reduced basis method for electromagnetic scattering and radar cross section estimation
• Certified reduced basis methods and output bounds for the harmonic Maxwell's equations
• Convergence rates for greedy algorithms in reduced basis methods
• Efficient reduced-basis treatment of nonaffine and nonlinear partial differential equations
• Estimation of the Error in the Reduced Basis Method Solution of Nonlinear Equations
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• scientific article; zbMATH DE number 1824045 (Why is no real title available?)
• On the Error Behavior of the Reduced Basis Technique for Nonlinear Finite Element Approximations
• Output bounds for reduced-basis approximations of symmetric positive definite eigenvalue problems
• Reduced basis approximation and a posteriori error estimation for affinely parametrized elliptic coercive partial differential equations. Application to transport and continuum mechanics.
• Reduced basis method for the rapid and reliable solution of partial differential equations
• Reduced collocation methods: Reduced basis methods in the collocation framework
• Trace optimization and eigenproblems in dimension reduction methods.

Cited in

(4)

• Hybrid projection methods with recycling for inverse problems
• Hybrid Projection Methods with Recycling for Inverse Problems
• Multilevel techniques for compression and reduction of scientific data -- the multivariate case
• A provably convergent MM-GKS variant for large-scale inverse problems

This page was built for publication: Reduced basis decomposition: a certified and fast lossy data compression algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2006533)