B-term Approximation Using Tree-Structured Haar Transforms

摘要

We present a heuristic solution for B-term approximation of 1-D discrete signals using Tree-Structured Haar (TSH) transforms. Our solution consists of two main stages: best basis selection and greedy approximation. In addition, when approximating the same signal with different B constraints or error metrics, our solution also provides the flexibility of reducing overall computation time of approximation by increasing overall storage space. We adopt a lattice structure to index basis vectors, so that one index value can fully specify a basis vector. Based on the concept of fast computation of TSH transform by butterfly network, we also develop an algorithm for directly deriving butterfly parameters and incorporate it into our solution. Results show that, when the error metric is either normalized l_1-norm or normalized l_2-norm, our solution has comparable (sometimes better) approximation quality with prior data synopsis algorithms.