PDF
\(\newcommand{\footnotename}{footnote}\) \(\def \LWRfootnote {1}\) \(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\) \(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\) \(\let \LWRorighspace \hspace \) \(\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }\) \(\newcommand {\mathnormal }[1]{{#1}}\) \(\newcommand \ensuremath [1]{#1}\) \(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \) \(\newcommand {\setlength }[2]{}\) \(\newcommand {\addtolength }[2]{}\) \(\newcommand {\setcounter }[2]{}\) \(\newcommand {\addtocounter }[2]{}\) \(\newcommand {\arabic }[1]{}\) \(\newcommand {\number }[1]{}\) \(\newcommand {\noalign }[1]{\text {#1}\notag \\}\) \(\newcommand {\cline }[1]{}\) \(\newcommand {\directlua }[1]{\text {(directlua)}}\) \(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\) \(\newcommand {\protect }{}\) \(\def \LWRabsorbnumber #1 {}\) \(\def \LWRabsorbquotenumber "#1 {}\) \(\newcommand {\LWRabsorboption }[1][]{}\) \(\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }\) \(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\) \(\def \mathcode #1={\mathchar }\) \(\let \delcode \mathcode \) \(\let \delimiter \mathchar \) \(\def \oe {\unicode {x0153}}\) \(\def \OE {\unicode {x0152}}\) \(\def \ae {\unicode {x00E6}}\) \(\def \AE {\unicode {x00C6}}\) \(\def \aa {\unicode {x00E5}}\) \(\def \AA {\unicode {x00C5}}\) \(\def \o {\unicode {x00F8}}\) \(\def \O {\unicode {x00D8}}\) \(\def \l {\unicode {x0142}}\) \(\def \L {\unicode {x0141}}\) \(\def \ss {\unicode {x00DF}}\) \(\def \SS {\unicode {x1E9E}}\) \(\def \dag {\unicode {x2020}}\) \(\def \ddag {\unicode {x2021}}\) \(\def \P {\unicode {x00B6}}\) \(\def \copyright {\unicode {x00A9}}\) \(\def \pounds {\unicode {x00A3}}\) \(\let \LWRref \ref \) \(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\) \( \newcommand {\multicolumn }[3]{#3}\) \(\require {textcomp}\) \(\newcommand {\intertext }[1]{\text {#1}\notag \\}\) \(\let \Hat \hat \) \(\let \Check \check \) \(\let \Tilde \tilde \) \(\let \Acute \acute \) \(\let \Grave \grave \) \(\let \Dot \dot \) \(\let \Ddot \ddot \) \(\let \Breve \breve \) \(\let \Bar \bar \) \(\let \Vec \vec \)

On the Convergence of the Singular Value Expansion of 2D functions

Sungwoo Jeong, Alex Townsend

Abstract

In this work we study the convergence of the singular value expansion (SVE) of 2D functions (kernels). Consider a square-integrable kernel \(K:[a, b]\times [c, d]\to \mathbb {R}\), where \([a, b], [c, d]\subset \mathbb {R}\). We define (i) Right singular functions denoted by \(u_1,u_2,\ldots \), which are orthonormal with respect to \(L^2([a,b])\) and (ii) Left singular functions denoted by \(v_1,v_2,\ldots \), which are orthonormal with respect to \(L^2([c,d])\). These singular functions are defined to satisfy the relationships

\begin{equation} \sigma _n u_n(x) = \int _c^d K(x, y)v_n(y) dy, \hspace {1cm} \sigma _n v_n(y) = \int _a^b K(x, y) u_n(x) dx. \end{equation}

The values \(\sigma _1\geq \sigma _2\geq \cdots >0\) are called the (positive) singular values of \(K\). The SVE of \(K\) is then defined as

\begin{equation} \label {eq:sve} K(x, y) = \sum _{n=1}^\infty \sigma _n u_n(x) v_n(y). \end{equation}

Recall that the singular vectors of a matrix \(A\) is defined with relationships \(Av_n = \sigma _n u_n\), \(u_n^*A = \sigma _n v_n^*\) and the singular value decomposition (SVD) can be defined as \(A = \sum _n \sigma _n u_n v_n^*\). Thus, the SVE can be thought of as a continuous analogue of the SVD [1].

Before the SVD of a matrix, several pioneers of modern functional analysis in the early 20th century figured out the existence and properties of the SVE for a general square-integrable kernel. Within these developments, Mercer [2], in 1909, showed that any continuous, symmetric positive definite kernel \(K:[a,b]\times [a,b]\rightarrow \mathbb {R}\) has a uniformly and absolutely converging SVE,

\begin{equation} K(x,y) = \sum _{n=1}^\infty \lambda _n u_n(x) u_n(y), \quad (x,y)\in [a,b]\times [a,b], \end{equation}

which is also equivalent to its eigenfunction expansion. This is often called Mercer’s theorem. For general kernels without positive definiteness or symmetricity, the convergence property (pointwise, uniform, and absolute) of the SVE is an open problem.

In this work, we first prove that the conclusion of Mercer’s theorem does not hold for general symmetric and asymmetric kernels, whenever the positive-definiteness condition is dropped. We provide novel examples which lead to the following result.

  • Theorem 1. For any \([a, b]\subset \mathbb {R}\) there are continuous symmetric indefinite kernels on \([a,b]\times [a,b]\) such that the SVE, equation (2), (i) does not converge pointwise, (ii) converges pointwise but not uniformly, or (iii) converges pointwise but not absolutely.

We hope this theorem will clarify some confusion in the literature regarding the convergence of the SVE whenever a symmetric kernel is not positive definite. In practice, a symmetric indefinite kernel often possesses a pointwise converging SVE but we prove that such convergence is not always guaranteed. Our work provides a rigorous underpinning for kernel methods using indefinite and asymmetric kernels.

We then prove our second main result, which is the convergence result of the SVE when a kernel is equipped with a mild regularity condition. We say a kernel \(K:[a, b]\times [c, d]\to \mathbb {R}\) is of uniform bounded variation if

\begin{equation} \int _a^b \frac {\partial }{\partial x}K(x,y)dx <V, \qquad \int _c^d \frac {\partial }{\partial y}K(x,y)dy <V, \label {eq:bv} \end{equation}

holds for any fixed \(x, y\) and a uniform constant \(V>0\). We remark that this is a larger class of general continuous kernels which includes, for instance, Lipschitz continuous kernels. For a continuous kernel of uniform bounded variation, we prove the following result using the singular value decay and a generalization of the Rademacher-Menchov theorem. (In fact, we prove that the same conclusion holds for any continuous kernel that has a singular value decay \(\sigma _n = \mathcal {O}(n^{-\alpha })\) with \(\alpha >\frac {1}{2}\).)

  • Theorem 2. For any \([a, b], [c, d]\subset \mathbb {R}\), let \(K:[a,b]\times [c,d]\to \mathbb {R}\) be a continuous kernel of uniform bounded variation (see equation (4)). Then, the SVE of \(K\), equation (2), converges pointwise almost everywhere, unconditionally almost everywhere, and almost uniformly.

To prove the second theorem, we also provide a new bound on the decay of singular values, which is state in the following proposition. We use a recent result [3] on the decay of the error of truncated Legendre series approximation to prove the decay bound.

  • Proposition 1. For any \([a, b], [c, d]\subset \mathbb {R}\), a continuous kernel \(K:[a,b]\times [c,d]\rightarrow \mathbb {R}\) of uniform bounded variation has \(\sigma _n = \mathcal {O}(n^{-1})\) as \(n\rightarrow \infty \).

Furthermore, we provide an efficient numerical algorithm for computing the SVE of a given function. The algorithm is divided into two steps. In the first step, we compute a pseudo-skeleton approximation using Gaussian elimination with complete pivoting (GECP), which is an iterative procedure to approximate the kernel \(K(x,y)\) as a sum of rank-1 functions [4]. After we have computed a rank \(\leq R\) pseudo-skeleton approximation, \(K_R(x, y)\), in the first step, we improve it by performing a low-rank SVD. The SVD decomposes \(K_R(x, y)\) into a sum of outer products of orthonormal functions with singular values and gives us an accurate truncated singular value expansion of \(K\).

References