The operator-norm Nyström perturbation bound

Given: The Nyström operators in the Statement, a bounded inverse $A^{-1}$, and $q=\mathrm{\parallel }{A}^{-1}\mathrm{\parallel }\mathrm{\parallel }{K}_Q-K\mathrm{\parallel }<1$.

Nyström quadrature operators and their reconstructed equations: $K_Q$ is the finite-sum map $u\mapsto {\sum }_j{w}_{j}k(\cdot ,y_j)u(y_j)$, with continuous coefficient functions $x\mapsto w_{j}k(x,y_j)$.

Finite-node Nyström equations are equivalent to their reconstructed equations: the finite system is nonsingular exactly when the reconstructed operator $I-K_Q$ is bijective.

Neumann series and small perturbations of bounded inverses: if $\mathrm{\parallel }R\mathrm{\parallel }<1$, then $I-R$ is invertible with inverse norm at most $(1-\mathrm{\parallel }R\mathrm{\parallel }{)}^{-1}$; if $A$ and $E$ are bounded and $A^{-1}$ is bounded with $\mathrm{\parallel }{A}^{-1}E\mathrm{\parallel }<1$, then $A+E=A(I+A^{-1}E)$ is invertible.

The operator norm as the least bound and as the unit-sphere or unit-ball supremum: $\mathrm{\parallel }T\mathrm{\parallel }$ is defined for a bounded linear operator by its supremum on the unit ball.

Composition satisfies |ST|\le|S|,|T|: for bounded linear operators $S,T$, $\mathrm{\parallel }ST\mathrm{\parallel }\le \mathrm{\parallel }S\mathrm{\parallel }\mathrm{\parallel }T\mathrm{\parallel }$.

A bounded linear operator between normed spaces: a linear map is bounded when one constant bounds its output norm by that constant times the input norm.

The square $[0,1{]}^2$ is compact (Heine-Borel in ${\mathbb{R}}^n$: with the Euclidean metric a subset of ${\mathbb{R}}^n$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line), so $k$ is bounded by $C(K,\mathbb{R})$ is complete in the supremum metric for every nonempty compact metric space $K$. If $M:={\sup }_{(x,y)\in [0,1{]}^2}\mathrm{\mid }k(x,y)\mathrm{\mid }$, the integral formula and Uniformly close integrable functions have integrals differing by at most the interval length times their uniform error give $\mathrm{\parallel }Ku{\mathrm{\parallel }}_{\mathrm{\infty }}\le M\mathrm{\parallel }u{\mathrm{\parallel }}_{\mathrm{\infty }}$, and Integrable functions on $[a,b]$ form a set closed under sums and scalar multiples, and ${\int }_a^b(\lambda f+\mu g)=\lambda {\int }_a^{b}f+\mu {\int }_a^{b}g$ makes $K$ linear. The finite-sum formula and Triangle inequality for finite sums, Finite sums and finite products, by recursion, Laws of finite sums and finite products give $\mathrm{\parallel }{K}_{Q}u{\mathrm{\parallel }}_{\mathrm{\infty }}\le M\mathrm{\parallel }u{\mathrm{\parallel }}_{\mathrm{\infty }}{\sum }_j\mathrm{\mid }{w}_j\mathrm{\mid }$ and make $K_Q$ linear. Hence $\mathrm{\parallel }(K_Q-K)u{\mathrm{\parallel }}_{\mathrm{\infty }}\le M(1+{\sum }_j\mathrm{\mid }{w}_j\mathrm{\mid })\mathrm{\parallel }u{\mathrm{\parallel }}_{\mathrm{\infty }}$ and $\mathrm{\parallel }(I-K)u{\mathrm{\parallel }}_{\mathrm{\infty }}\le (1+M)\mathrm{\parallel }u{\mathrm{\parallel }}_{\mathrm{\infty }}$; thus $K$, $K_Q$, $K_Q-K$, and $A=I-K$ are bounded linear maps in the sense of [F6].