daanhb
commented
8 years ago Sorry for my slow reply @kuanxu. This is a very good point, and as you mention the adaptive construction of a frame approximation is not straightforward. It is a topic of its own that we did not address yet. Feel free to experiment and suggest possible solutions :-)
For completeness, let me outline some considerations:
- The underlying problem is that, as you know, after you have computed an approximation with N coefficients there is no clear indication how many coefficients M <= N would have been sufficient. It is not the case that the coefficients decay to machine precision and stay there.
- There is indeed usually some decay of the Fourier extension coefficients. However, that decay is not related to the smoothness of the function as is usually the case in approximation schemes, and it is fairly unpredictable. There is no guarantee. Truncating the expansion based on this decay would be far from optimal.
- We can compute a smoothed Fourier extension in O(N log N) operations with an adaptation of the fast algorithm. This has not yet appeared in literature, but it is included in the implementation. With this algorithm, the coefficients do decay at a certain rate and they can simply be truncated. However, with our algorithm you have to guess a priori the smoothness of the function, since you essentially enforce decay at a certain rate. You can truncate, but it would still not be optimal unless you adaptively find the maximal decay rate.
- Since we solve a least squares approximation problem Ax=B with rectangular matrix A, you can assess the approximation error by calculating the residual Ax-B. The maximum of the residual is a reliable estimate of the maximum pointwise error of the approximation. Based on this, one could imagine a bisection iteration to find the optimal number of degrees of freedom to reach a certain precision. Constructing larger and larger approximations until the function is resolved, as you suggest, should be possible. Being ambitious, though, you would still want to optimally truncate the final approximation.
- Our fast algorithm currently employs a lot of matrix-vector products with random vectors, and a full SVD of a small but dense matrix. Ideally, in an adaptive algorithm, the results of these computations are reused when the number of degrees of freedom changes. It is not clear how to do this.
kuanxu
Is it possible to have an automatic
framefunconstructor which is able to construct aframefunwith a reasonably optimal lengthnfor a given function handle? I mean something similar to thechebfunconstructor which keeps increasing the length of the approximation until the function is "fully resolved".I had a vague impression that @daanhb mentioned that the Fourier extension coefficients are not necessarily decaying, which prevents an automatic construction. But I checked with a few examples and found that the Fourier extension coefficients are indeed getting smaller and smaller as the frequency goes higher and higher. Any comments?
It'll be nice if we can have such an auto-ctor. But, of course, even if it is possible to have such a thing, I'm not suggesting this should be something default at the user level.