0.4 Approximation  (Page 3/3)

Supposing that $f$ is piecewise smooth, however, with a finite number of discontinuities, then (as discussed in Sparse (Nonlinear) Models from Low-Dimensional Signal Models ) $f$ will have a limited number of significant wavelet coefficients at fine scales. Because of theconcentration of these significant coefficients within each scale, the nonlinear approximation rate will remain ${\sigma }_K{\left(f\right)}_2\lesssim K^{-H}$ as if there were no discontinuities present [link] .

Unfortunately, this resilience of wavelets to discontinuities does not extend to higher dimensions. Suppose, for example, that $f$ is a ${\mathcal{C}}^H$ smooth 2-D signal. Assuming the proper number of vanishing moments, a wavelet representation will achievethe optimal nonlinear approximation rate ${\sigma }_K{\left(f\right)}_2\lesssim K^{-H/2}$ [link] , [link] . As in the 1-D case, this approximation rate is maintained when a finite number of point discontinuities are introduced into $f$ . However, when $f$ contains 1-D discontinuities (edges separating the smooth regions), the approximation rate will fall to ${\sigma }_K{\left(f\right)}_2\lesssim K^{-1/2}$ [link] . The problem actually arises due to the isotropic, dyadic supports of the wavelets; instead of $O\left(1\right)$ significant wavelets at each scale, there are now $O\left(2^j\right)$ wavelets overlapping the discontinuity. We revisit this important issue in Compression .

Despite the limited approximation capabilities for images with edges, nonlinear approximation in the wavelet domain typically offers a superior approximation to an image compared to linear approximation in the wavelet domain. As an example, [link] (b) shows the nonlinear approximation of the Cameraman test image obtained by keeping the largest scaling and wavelet coefficients. In this case, a number of high-frequency coefficients are selected, which gives an improved ability to represent features such as edges. Better concise transforms, which capture the image information in even fewer coefficients, would offer further improvements in terms of nonlinear approximation quality.

Finding approximations

As mentioned above, in the case where $\Psi$ is an orthonormal basis and $p=2$ , the solution to [link] is easily obtained by thresholding: one simply computes the coefficients $\alpha$ and keeps the $K$ largest (setting the remaining coefficients to zero). Thresholding can also be shown to be optimal for arbitrary ${\ell }_p$ norms in the special case where $\Psi$ is the canonical basis. While the optimality of thresholding does notgeneralize to arbitrary norms and bases, thresholding can be shown to be a near-optimal approximation strategy for wavelet bases witharbitrary $L_p$ norms [link] .

In the case where $\Psi$ is a redundant dictionary, however, the expansion coefficients $\alpha$ are not unique, and the optimization problem [link] can be much more difficult to solve. Indeed, supposing even that an exact $K$ -term representation exists for $f$ in the dictionary $\Psi$ , finding that $K$ -term approximation is NP-hard in general, requiring a combinatorial enumeration of the $\left(\genfrac{}{}{0pt}{}{Z}{K}\right)$ possible sparse subspaces [link] . This search can be recast as the optimization problem

Manifold approximation

We also consider the problem of finding the best manifold-based approximation to a signal (see [link] (c)). Suppose that $\mathcal{F}=\{f_{\theta }:\theta \in \Theta \}$ is a parametrized $K$ -dimension manifold and that we are given a signal $I$ that is believed to approximate $f_{\theta }$ for an unknown $\theta \in \Theta$ . From $I$ we wish to recover an estimate of $\theta$ . Again, we may formulate this parameter estimation problem as an optimization, writing the objectivefunction (here we concentrate solely on the $L_2$ or ${\ell }_2$ case)

Standard nonlinear parameter estimation  [link] tells us that, if $D$ is differentiable, we can use Newton's method to iteratively refine a sequence of guesses ${\theta }^{\left(0\right)},{\theta }^{\left(1\right)},{\theta }^{\left(2\right)},\cdots$ to ${\theta }^{*}$ and rapidly convergence to the true value. Supposing that $\mathcal{F}$ is a differentiable manifold, we would let

Again, the above discussion assumes the manifold to be differentiable. Many interesting parametric signal manifolds are in fact nowheredifferentiable — the tangent spaces demanded by Newton's method do not exist. However, in [link] we have identified a type of multiscale tangent structure to the manifold that permits a coarse-to-fine technique for parameter estimation.