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 non-transitory computer readable medium storing computer instructions, when processed by a computer, adapt the operation of the computer to perform a method for deterministic wavelet thresholding for optimizing general-error metrics, the method comprising:
conditioning a minimum error value for an error subtree not only on a root node of the error subtree and the amount of synopsis storage allotted, but also on an error that enters the subtree through coefficient selections made on a path from the root node to a particular node, excluding that particular node itself; and
tabulating all possible coefficient selections in polynomial time.
2. The method of claim 1 , further comprising:
minimizing error in a data approximation;
wherein the minimum error value is maximum relative error.
3. The method of claim 1 , further comprising:
minimizing error in a data approximation;
wherein the minimum error value is maximum absolute error.
4. A non-transitory computer readable medium storing computer instructions, when processed by a computer, adapt the operation of the computer to perform a method for deterministic wavelet thresholding for optimizing general-error metrics, the method comprising:
approximately covering a range of all possible error contributions for paths up to a root node of an error subtree using a plurality of approximate error values;
tabulating the approximate error values by capturing approximate error in a plurality of error subtrees, each error subtree being rooted at a particular node; and
tabulating a rounded additive error contribution due to ancestors of the particular node being discarded from a synopsis.
5. The method of claim 4 , wherein the error values are relative.
6. The method of claim 4 , wherein the error values are absolute.
7. A non-transitory computer readable medium storing computer instructions, when processed by a computer, adapt the operation of the computer to perform a method for deterministic wavelet thresholding for optimizing general-error metrics, the method comprising:
determining error value vectors for each of a plurality of coefficient subsets;
scaling-down the error value vectors using a threshold value;
using dynamic programming over the scaled error value vectors, cycling only through coefficient subsets whose error value vector entries are above the threshold value to determine an optimal solution for a scaled problem instance;
trying an appropriate collection of additional threshold values and returning the synopsis with the smallest error.