Deterministic wavelet thresholding for general-error metrics
View Patent ↗Novel, computationally efficient schemes for deterministic wavelet thresholding with the objective of optimizing maximum-error metrics are provided. An optimal low polynomial-time algorithm for one-dimensional wavelet thresholding based on a new dynamic-programming (DP) formulation is provided that can be employed to minimize the maximum relative or absolute error in the data reconstruction. Directly extending a one-dimensional DP algorithm to multi-dimensional wavelets results in a super-exponential increase in time complexity with the data dimensionality. Thus, novel, polynomial-time approximation schemes (with tunable approximation guarantees for the target maximum-error metric) for deterministic wavelet thresholding in multiple dimensions are also provided.
1. A method for deterministic wavelet thresholding for optimizing general-error metrics, comprising using a processor to perform the steps of:
building a deterministic wavelet synopsis that minimizes maximum error in a data-value approximation; and
providing a minimum maximum error for all data values in an error subtree of an error tree associated with the deterministic wavelet synopsis, wherein a minimum maximum error value for the error subtree is conditioned on a root node of the error subtree, an amount of storage allotted for the deterministic wavelet synopsis, and an error that enters the error subtree through coefficient selections made on a path from a root node of the error tree toward the root node of the error subtree.
2. The method of claim 1 , wherein the minimum maximum error is a maximum relative error.
3. The method of claim 1 , wherein the minimum maximum error is a maximum absolute error.
4. The method of claim 1 , wherein the deterministic wavelet synopsis is built over a one-dimensional data array.
5. The method of claim 1 , wherein the deterministic wavelet synopsis is built over a multi-dimensional data array.
6. A method for deterministic wavelet thresholding for optimizing general-error metrics, comprising using a processor to perform the steps of:
building a deterministic wavelet synopsis that minimizes maximum error in a data-value approximation, wherein the deterministic wavelet synopsis comprises a plurality of coefficients, wherein each coefficient of the deterministic wavelet synopsis is retained deterministically; and
providing a minimum maximum error for all data values in a subtree for the deterministic wavelet synopsis.