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.