Abstract
Due to their flexibility, frames of Hilbert spaces are attractive alternatives to bases in approximation schemes for problems where identifying a basis is not straightforward or even feasible. Computing a best approximation using frames, however, can be challenging since it requires solving an ill-conditioned linear system. One consequence of this ill-conditioning is that the coefficients of such a frame approximation can grow large. In this paper we resolve this issue by introducing two methods for frame approximation that possess bounded coefficients. As we show, these methods typically lead to little or no deterioration in the approximation accuracy, but successfully avoid the large coefficients inherent to previous approaches, thus making them attractive in situations where large coefficients are undesirable. We also present theoretical analysis to support these conclusions.
Introduction
In scientific computing, approximating complex functions often requires building blocks beyond standard orthonormal bases. Frames offer a flexible, redundant alternative, particularly useful for irregular domains. However, this redundancy is a double-edged sword: while it simplifies frame construction, it introduces numerical ill-conditioning. When solving for coefficients using standard tools like Matlab’s backslash or Truncated SVD (TSVD), the resulting coefficients often "explode" in magnitude during the pre-asymptotic regime. This paper introduces adaptive methods to ensure coefficient stability without compromising accuracy.
Adaptive SVD Methods
The core innovation lies in moving away from static thresholding of singular values. Standard TSVD discards all singular values below a fixed tolerance $\epsilon$. In contrast, the authors propose two Adaptive SVD (ASVD) schemes that consider the specific function being approximated:
- ASVD1: Discards a singular value $\sigma_n$ if it falls below a baseline tolerance $\epsilon$ or if its contribution to the coefficient norm is disproportionately large relative to the data (i.e., $| \langle y, v_n \rangle | / \sigma_n > c \|y\|$).
- ASVD2: Imposes a global bound, selecting the largest set of singular values such that the total coefficient norm remains below a user-defined threshold $c \|y\|$.
These methods treat redundancy as a safety net; if one representation requires massive coefficients, the ASVD methods search for a "cheaper" alternative that is nearly as accurate.
Stability and Accuracy Analysis
Numerical experiments using Legendre polynomial frames and Runge-type functions demonstrate the effectiveness of these adaptive schemes. A key observation is the "bizarre peak" in coefficient norms seen in standard TSVD during the pre-asymptotic phase, where $N$ is medium-sized.
As shown in Figure 2, while the error curves for ASVD remain nearly identical to TSVD, the coefficient norms are significantly suppressed. ASVD2 guarantees a uniform bound, while ASVD1 limits growth to $O(\sqrt{N})$, a vast improvement over the $O(1/\sqrt{\epsilon})$ explosion typical of standard approaches.
Comparison with Standard Solvers
The practical utility of ASVD1 is further highlighted when compared against common numerical tools like QR decomposition, Tikhonov regularization, and Matlab's backslash operator.
Figure 4 illustrates that standard solvers fail to control coefficient growth in the pre-asymptotic regime, often resulting in spikes that are physically nonsensical and computationally inefficient. ASVD1 maintains stability throughout the approximation process while matching the $O(\sqrt{\epsilon})$ limiting accuracy of TSVD.
Conclusion
By adaptively pruning singular values based on a cost-benefit analysis of their contribution to the coefficient norm, ASVD methods provide a robust solution to the problem of exploding coefficients in frame approximations. These methods ensure that the flexibility of redundant systems can be leveraged without the numerical instability traditionally associated with ill-conditioned frame operators.
Summary updated