Frame approximation with bounded coefficients

Ben Adcock, Mohsen Seifi

TL;DR

Function approximation using "frames" (redundant systems) offers great flexibility but often suffers from "exploding" coefficients due to numerical ill-conditioning. This paper introduces two adaptive SVD-based methods that maintain small, stable coefficients without sacrificing approximation accuracy, effectively solving a major practical hurdle in numerical frame theory.

What Problem Does This Paper Address?

In scientific computing, we often need to approximate a complex function using a set of simpler "building block" functions. While orthonormal bases (like Fourier series) are the gold standard, they can be incredibly difficult to construct for irregular domains or specialized problems.

Frames provide a flexible alternative. Unlike bases, frames are "overcomplete"—they have more elements than strictly necessary to span the space. This redundancy is a double-edged sword: it makes frames easy to build, but it leads to ill-conditioned linear systems.

When you try to solve for the coefficients of a frame approximation using standard tools (like Matlab’s backslash or even standard Truncated SVD), the coefficients often "explode," becoming massive in magnitude. This is computationally inefficient and physically nonsensical, especially since the redundancy of the frame implies that many different sets of coefficients could represent the same function. The authors seek a way to find the "good" coefficients—those that are both accurate and small.

Methods

The authors propose moving beyond static thresholding. Standard Truncated SVD (TSVD) simply discards all singular values below a fixed tolerance $\epsilon$. The authors introduce two "Adaptive SVD" (ASVD) schemes:

  1. ASVD1 (Adaptive SVD 1): Instead of a flat cutoff, this method discards a singular value $\sigma_n$ if it is either below $\epsilon$ OR if its contribution to the coefficient norm is disproportionately large compared to the data. Specifically, it checks if $| \langle y, v_n \rangle | / \sigma_n > c \|y\|$, where $c$ is a user-defined parameter.
  2. ASVD2 (Adaptive SVD 2): This is a stricter version that imposes a global bound. It sorts singular values and picks the largest possible set such that the total norm of the resulting coefficients remains below a fixed threshold ($c \|y\|$).

These methods are "adaptive" because the decision to keep or discard a singular value depends on the specific function being approximated, not just the properties of the frame itself.

Datasets

As a theoretical numerical analysis paper, the "datasets" consist of specific mathematical functions and frame constructions used for benchmarking:

  • Functions: The authors test smooth functions (like a Runge-type function $1/(1+75t^2)$) and functions with logarithmic singularities.
  • Frames:
    • Legendre Polynomial Frames: Created by restricting orthonormal Legendre polynomials from a large interval to a smaller sub-interval.
  • Augmented Frames: An orthonormal basis (Legendre) augmented with a finite set of singular "feature functions" (like $\log(t) \cdot \phi_j(t)$) to better capture singularities.

Key Insights and Ideas

  • The "Bizarre" Peak: Standard methods exhibit a strange phenomenon where coefficients spike to massive levels when the number of terms ($N$) is medium-sized (the "pre-asymptotic" regime), only to settle down once $N$ becomes very large. The authors realized this spike is unnecessary for accuracy.
  • Cost-Benefit Analysis for Singular Values: Not all singular values are created equal. Some contribute a tiny bit to accuracy but cause a massive jump in coefficient size. By adaptively pruning these "expensive" singular values, we can maintain stability.
  • Redundancy as a Safety Net: Because frames are redundant, there are many ways to represent a function. If one representation requires huge coefficients, the ASVD methods effectively search for a "cheaper" alternative that is nearly as accurate.
  • Thresholding is Vital: The paper proves that even with adaptive logic, a baseline threshold $\epsilon > 0$ is necessary to ensure fast convergence; without it, the error can jump or stagnate.

Key Results

  • Stability: ASVD2 guarantees that coefficients are uniformly bounded by $c \|y\|$ regardless of how many terms ($N$) are used. ASVD1 keeps them growing at most by $O(\sqrt{N})$, which is much better than the $O(1/\sqrt{\epsilon})$ explosion seen in TSVD.
  • Accuracy: Mathematically, the authors prove that ASVD1 and ASVD2 achieve the same $O(\sqrt{\epsilon})$ limiting accuracy as standard TSVD.
  • Numerical Performance: In tests, the ASVD methods completely eliminated the "coefficient spike" seen in Matlab's backslash and TSVD, while the approximation error curves remained almost identical to the standard (but unstable) approaches.

Limitations and Future Work

  • Parameter Selection: The methods rely on a constant $c$. If $c$ is chosen too small, the approximation error can be significantly worse than TSVD, or convergence can become very slow.
  • Frame Requirement: The theoretical guarantees rely on the system being a "frame." For general redundant systems that don't satisfy the frame condition (like simple monomials $t^n$), these methods might not perform as well because a small-norm representation might not exist.
  • Extension to Least-Squares: The current analysis focuses on "square" systems (finite sections). The authors suggest that extending this logic to "uneven" systems (where you have more samples than functions) is a promising next step.

Summary updated

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.
BibTeX
@inproceedings{adcock2021frame,
  author = {Ben Adcock and Mohsen Seifi},
  title = {{Frame approximation with bounded coefficients}},
  booktitle = {Adv. Comput. Math},
  year = {2021},
  url = {https://openreview.net/forum?id=QKixTjiFkva},
}

Loading related content...

Figure