Say we have the following (wavelet) series representation at some location and scale in a signal:

$$ f = \sum_{k=1}^{K} c_k \psi_k$$

where $c_k$ is the coefficient, in order of magnitude ($|c_k| > |c_{k+1}|$) and $\psi_k$ is the wavelet, although it could be any $L_2$ function I guess.

Is there a principled way of truncating the series? E.g. could AIC be applied to say choose the first $N < K$ wavelets? If so how?

  • $\begingroup$ Possibly $|c_k|\ge|c_{k+1}|$? $\endgroup$ – Laurent Duval Mar 20 '16 at 15:38

We are in the realm of non-linear data approximation. Among the standard litterature, there are Nonlinear approximation, 1998 (R. de Vore), or the more visual On Fourier and Wavelets: Representation, Approximation and Compression, 2006, Vetterli.

Best $N$-term approximation, with respect to some norm $\|f-f_N \|_p$, is quite involved (generically, NP-hard). A basic (suboptimal) approach keeps the $N$ biggest terms (esp. with an orthogonal basis)), which (since $|c_k|\ge|c_{k+1}|$) amounts to finding a proper threshold $\gamma$, and perfom hard-thresholding, up to $|c_N|\ge \gamma >|c_{N+1}|$. There are many strategies to pick an optimal threshold, with additional assumptions on the data, on the noise.

Since you are interested in the Akaike Information Criterion (AIC), you can check A Crossvalidatory AIC for Hard Wavelet Thresholding in Spatially Adaptive Function Estimation, 1998, that compares with other standard wavelet shrinkages.

In general, you have to balance a number of terms (on even bits) with the accuracy. The $\ell_0$ constraint can be converted into other norm penalty. If you want to compress, denoise, you can use other sparsity measures like entropy-based method. Further, you have all sort of matching techniques. You can have a quick overview, for images, in Chapter 4: Redundancy and adaptivity.

| improve this answer | |
  • $\begingroup$ Thanks Laurent. I relation to the question, I was more thinking of the coefficients at a single, specific location independent of the rest of the image, so $K$ will be small, say only 5 or 6 terms. But I guess the principle is the same. Specifically, each wavelet represents a particular feature component, such as a line segment or an edge, that add together to make a complex feature, such as 'T' junction. So number of wavelets (components) determines the feature class. Currently I just use an arbitrary threshold, but I will try adding an $\ell_0$ penalty term like in 4.2.2 of your paper. $\endgroup$ – geometrikal Mar 20 '16 at 21:46
  • $\begingroup$ @geometrikal Let me think about it in more details, if you let us know of some other details. With very few terms, I suspect that a lot of methods won't work how they are supposed to. As several coeffcients group around features, maybe a block-thresholding scheme could be appropriate $\endgroup$ – Laurent Duval Mar 20 '16 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.