Restricted isometry and information-based numerical analysis

Abstract

This thesis aims to advance numerical analysis towards practical scenarios in which the available information for numerical algorithms is partial, contaminated, and priced. These scenarios represent information-based situations crucial in practical applications, particularly when the available information is predetermined or obtaining sufficient information can be difficult and costly. The resulting paradigm is referred to as information-based numerical analysis, and the main motivation is to develop numerical algorithms that achieve a reasonable level of accuracy with limited and possibly predetermined information. The thesis explores this new paradigm with concrete numerical algorithms in three numerical analysis topics.

The first part of the thesis focuses on numerical approximation, specifically on hyperinterpolation. Hyperinterpolation is a quadrature-based discretization of the orthogonal projection, and constructing a hyperinterpolant of degree $n$ requires a positive-weight quadrature rule with exactness degree $2n$. Using the Marcinkiewicz--Zygmund (MZ) system of quadrature rules, which can be regarded as a restricted isometry of the quadrature rules in the numerical integration of polynomials of certain degrees, the thesis shows that hyperinterpolation can be constructed with a reasonable error bound in the presence of the quadrature exactness assumption, suggesting that it is reliable in regard of the information-based situation. The thesis also proposes a variant of this scheme in approximating singular and oscillatory functions, leveraging the product-integration method and attaining the desired accuracy with fewer quadrature points than the original hyperinterpolation.

The second part of the thesis proposes and analyzes a quadrature-based spectral method for solving the Allen--Cahn equation on spheres based on the approximation results in the previous part. This method employs hyperinterpolation and the MZ system of quadrature rules, achieving the theoretical benefits of the Galerkin method at a computational cost comparable to the collocation method. This method does not necessarily rely on the quadrature exactness assumption, which confronts more practical simulations situations and distinguishes it from previous quadrature-based methods. Moreover, this method also possesses an effective maximum principle, which allows the numerical solutions to deviate from the sharp bound by a controllable discretization error.

The third part of the thesis focuses on compressed sensing and imaging, investigating models that reconstruct unknown signals and images from their incomplete and inaccurate measurements. These models can be formulated as solving an underdetermined linear system. The thesis introduces the springback penalty and the enhanced total variation (TV) regularization and establishes the exact and stable reconstruction theory for these models under the restricted isometry property (RIP) framework. The thesis shows that the springback and enhanced TV models have tighter reconstruction error bounds than various convex and non-convex models for scenarios where the amount of measurements is limited and the level of noise is significant.

Overall, this thesis contributes to the development of numerical algorithms that require less information while achieving the desired level of accuracy. The proposed algorithms in this thesis demonstrate their effectiveness and theoretical superiority over existing algorithms in various numerical analysis topics regarding information-based situations. The investigation in this thesis may enlighten the development of numerical algorithms for other problems that involve information-based situations.