For objects belonging to a known model set and observed through a prescribed linear process, we aim at determining methods to recover linear quantities of these objects that are optimal from a worst-case perspective. Working in a Hilbert setting, we show that, if the model set is the intersection of two hyperellipsoids centered at the origin, then there is an optimal recovery method which is linear. It is specifically given by a constrained regularization procedure whose parameters, short of being explicit, can be precomputed by solving a semidefinite program. This general framework can be swiftly applied to several scenarios: the two-space problem, the problem of recovery from $\ell_2$-inaccurate data, and the problem of recovery from a mixture of accurate and $\ell_2$-inaccurate data. With more effort, it can also be applied to the problem of recovery from $\ell_1$-inaccurate data. For the latter, we reach the conclusion of existence of an optimal recovery method which is linear, again given by constrained regularization, under a computationally verifiable sufficient condition. Experimentally, this condition seems to hold whenever the level of $\ell_1$-inaccuracy is small enough. We also point out that, independently of the inaccuracy level, the minimal worst-case error of a linear recovery method can be found by semidefinite programming.

Nonlinear dynamical systems are ubiquitous in various scientific areas. The Koopman operator theory provides a way to analyze nonlinear dynamical systems with a linear operator, whose spectra contain rich information in understanding the behaviors of dynamical systems. In this paper, we aim to use a data-driven method to construct the principal eigenfunctions of the Koopman operator. Our approach relies on the decomposition of the Koopman eigenfunction where the linear part associates with the left eigenvectors of the linearization of the system at the equilibrium, and the nonlinear part satisfies a linear PDE. Then, we solve the linear PDE using a random features model, which is a data-driven machine learning technique for large-scale kernel approximation. In addition, the random features model can be viewed as a randomized shallow neural network where only the linear readout needs to be trained, which significantly reduces the computational complexity. We provide a computational framework for the approximation of Koopman eigenfunctions and an error analysis for our proposed method. Finally, we present simulation results for learning the principal eigenfunctions and constructing the Lyapunov function using learned principal eigenfunctions. Numerical experiments indicate that our method is fast and accurate. As such, it can serve as a benchmark for approximating Koopman eigenfunctions.

Optimal recovery is a mathematical framework for learning functions from observational data by adopting a worst-case perspective tied to model assumptions on the functions to be learned. Working in a finite-dimensional Hilbert space, we consider model assumptions based on approximability and observation inaccuracies modeled as additive errors bounded in $\ell_2$. We focus on the local recovery problem, which amounts to the determination of Chebyshev centers. Earlier work by Beck and Eldar presented a semidefinite recipe for the determination of Chebyshev centers. The result was valid in the complex setting only, but not necessarily in the real setting, since it relied on the S-procedure with two quadratic constraints, which offers a tight relaxation only in the complex setting. Our contribution consists in proving that this semidefinite recipe is exact in the real setting, too, at least in the particular instance where the quadratic constraints involve orthogonal projectors. Our argument exploits a previous work of ours, where exact Chebyshev centers were obtained in a different way. We conclude by stating some open questions and by commenting on other recent results in optimal recovery.