High-resolution signal recovery via generalized sampling and functional principal component analysis

Abstract

In this paper, we introduce a computational framework for recovering a high-resolution approximation of an unknown function from its low-resolution indirect measurements as well as high-resolution training observations by merging the frameworks of generalized sampling and functional principal component analysis. In particular, we increase the signal resolution via a data-driven approach, which models the function of interest as a realization of a random field and leverages a training set of observations generated via the same underlying random process. We study the performance of the resulting estimation procedure and show that high-resolution recovery is indeed possible provided appropriate low rank and angle conditions hold and provided the training set is sufficiently large relative to the desired resolution. Moreover, we show that the size of the training set can be reduced by leveraging sparse representations of the functional principal components. Furthermore, the effectiveness of the proposed reconstruction procedure is illustrated by various numerical examples.

Appendix. Proofs of theoretical results

Proof of Lemma 1

Observe that $\sin \limits \angle (\mathcal {E}_{m},\hat {\mathcal {E}}^{p}_{m})\leq \sin \limits \angle (\mathcal {E}_{m},\mathcal {E}^{p}_{m}) + \sin \limits \angle (\mathcal {E}^{p}_{m},\hat {\mathcal {E}}^{p}_{m}),$ where $\mathcal {E}^{p}_{m}:=\text {span}\{{\phi _{1}^{p}},\ldots ,{\phi _{m}^{p}}\}$ and $\{({\phi _{j}^{p}},{\lambda _{j}^{p}})\}_{j=1}^{p}$ are the eigenfunction-eigenvalue pairs of the covariance operator K_p associated to the random variable $Q_{\mathcal {G}_{p}}F$. Recall that ${e^{p}_{j}}:=(\langle {\phi _{j}^{p}} ,\varphi _{1} \rangle ,\ldots , \langle {\phi _{j}^{p}} ,\varphi _{p} \rangle )^{\top }$ is an eigenvector of Σ_X with eigenvalue ${\lambda _{j}^{p}}$. To upper-bound $\sin \limits \angle (\mathcal {E}_{m},\mathcal {E}^{p}_{m})$, first note that for any k,j = 1,…,p, we have

$$ \begin{array}{@{}rcl@{}} {\lambda_{j}^{p}} \langle {\phi_{j}^{p}} ,\varphi_{k} \rangle &= {\sum}_{\ell=1}^{p} {\Sigma}_{X}^{(k\ell)}\langle {\phi_{j}^{p}},\varphi_{\ell} \rangle = {\int}_{D}{\int}_{D} K(u,v) \overline{\varphi_{k}(u)} {\phi_{j}^{p}}(v) \mathrm{d} u \mathrm{d} v, \end{array} $$

where we used ${\lambda ^{p}_{j}} {e^{p}_{j}}={\Sigma }_{X} {e^{p}_{j}}$ and ${\Sigma }_{X}^{(k,\ell )}=\mathbb {E} [ \langle F-\mu , \varphi _{k} \rangle \overline { \langle F-\mu , \varphi _{\ell }} \rangle ] = {\sum }_{j\in \mathbb {N}}\lambda _{j} \langle \phi _{j}, \varphi _{k} \rangle \overline {\langle \phi _{j}, \varphi _{\ell } \rangle } = {\int \limits }_{D}{\int \limits }_{D} K(u,v) \overline {\varphi _{k}(u)}\varphi _{\ell }(v) \mathrm {d} u \mathrm {d} v$, k,ℓ = 1,…,p, as well as the fact that ${\phi _{j}^{p}}={\sum }_{\ell =1}^{p}\langle {\phi _{j}^{p}},\varphi _{\ell } \rangle \varphi _{\ell }$, respectively. Therefore

$$ \begin{array}{@{}rcl@{}} {\lambda^{p}_{j}} {\int}_{D} {\phi^{p}_{j}}(v) \overline{g(v)} \mathrm{d} v = {\int}_{D}{\int}_{D} K(u,v) {\phi^{p}_{j}}(u) \overline{g(v)} \mathrm{d} u \mathrm{d} v, \quad \forall g\in\mathcal{G}_{p}. \end{array} $$

Since also $\lambda _{j} {\int \limits }_{D} \phi _{j}(v) \overline {f(v)} \mathrm {d} v = {\int \limits }_{D}{\int \limits }_{D} K(u,v) \phi _{j}(u) \overline {f(v)} \mathrm {d} u \mathrm {d} v$, $\forall f\in {\mathscr{L}}_{2}(D;\mathbb {C})$, by the approximation properties of the Galerkin method [10], we have ${\lambda _{j}^{p}}\leq \lambda _{j}$, and moreover, there exist C (independent of p) and p₀ such that for any p ≥ p₀ and j = 1,…,m, we have

$$ \begin{array}{@{}rcl@{}} \lambda_{j} -{\lambda_{j}^{p}} &\leq C {\lambda_{j}^{2}} {\epsilon_{p}^{2}}, \end{array} $$

(25)

$$ \begin{array}{@{}rcl@{}} \|\phi_{j} - {\phi_{j}^{p}}\| &\leq C \epsilon_{p}. \end{array} $$

(26)

Now, let e_j := (〈ϕ_j,φ₁〉,〈ϕ_j,φ₂〉,…)^⊤, $E_{m} := (e_{1}, \ldots , e_{m}) \in \mathbb {C}^{\infty \times m}$ and ${E_{m}^{p}} := ({e_{1}^{p}}, \ldots , {e_{m}^{p}}) \in \mathbb {C}^{p\times m}$. Let $Q_{p}\in \mathbb {C}^{p\times \infty }$ denote the projection operator with identity I_p constituting the first p columns and the rest equal to zero, and let ${\Theta }({E_{m}^{p}},Q_{p}E_{m})$ denote the m × m diagonal matrix whose j th diagonal entry is $\arccos$ of the j th singular value of $({E_{m}^{p}})^{\top } Q_{p} E_{m}$. Observe that $\langle \phi _{j},{\phi _{k}^{p}} \rangle ={\sum }_{\ell =1}^{p} \langle \phi _{j},\varphi _{\ell } \rangle \langle {\phi _{k}^{p}},\varphi _{\ell } \rangle = ({e_{k}^{p}})^{\top } Q_{p} e_{j}$. Therefore, we have

$$ \begin{array}{@{}rcl@{}} \sin\angle(\mathcal{E}_{m},{\mathcal{E}}^{p}_{m}) &=& \|\sin {\Theta}({E_{m}^{p}},Q_{p} E_{m})\|_{\text{op}} \leq \frac{1}{\sqrt{2}} \| {E_{m}^{p}} - Q_{p} E_{m} \|_{\mathrm{F}} \\ &\leq& \sqrt{\frac{m}{2}} \max_{j=1,\ldots,m} \| {e_{j}^{p}} - Q_{p} e_{j} \|_{2} \!\leq\! \sqrt{\frac{m}{2}} \max_{j=1,\ldots,m} \| {\phi^{p}_{j}} - \phi_{j} \| \!\leq\! C \sqrt{\frac{m}{2}} \epsilon_{p}, \end{array} $$

where in the last inequality we used (26). To conclude part (a) of the proof, it remains to upper-bound $\sin \limits \angle (\mathcal {E}^{p}_{m},\hat {\mathcal {E}}^{p}_{m})$. Similarly as above, let $\hat {E}_{m}^{p} := (\hat {e}_{1}^{p}, \ldots , \hat {e}_{m}^{p}) \in \mathbb {C}^{p\times m}$, and let ${\Theta }(\hat {E}_{m}^{p},{E_{m}^{p}})$ denote the m × m diagonal matrix whose j th diagonal entry is $\arccos$ of the j th singular value of $(\hat {E}_{m}^{p})^{\top } {E_{m}^{p}}$. Since ${\langle \phi ^{p}_{j}},{\hat \phi ^{p}_{k}}\rangle = (\hat {e}^{p}_{k})^{\top }{e^{p}_{j}}$, we have $\sin \limits \angle ({\mathcal {E}}^{p}_{m},\hat {\mathcal {E}}^{p}_{m}) = \|{\sin \limits } {\Theta }(\hat {E}_{m}^{p},{E_{m}^{p}})\|_{\text {op}}$, and since ${\Sigma }_{X} {e^{p}_{j}}={\lambda ^{p}_{j}} {e^{p}_{j}}$, we have ${\Sigma }_{Y}{e_{j}^{p}}=({\lambda _{j}^{p}}+\tilde \sigma ^{2}){e_{j}^{p}}$. Thus, due to Davis–Kahan Theorem [20] and Weyl’s inequality [46], provided $\| \hat {\Sigma }_{Y} - {\Sigma }_{Y} \|_{\text {op}}<({\lambda _{m}^{p}}-\lambda _{m+1}^{p})/2$ holds, we have

$$ \sin\angle({\mathcal{E}}^{p}_{m},\hat{\mathcal{E}}^{p}_{m}) \leq \frac{\sqrt{m}}{|{\lambda_{m}^{p}}+\tilde\sigma^{2}-\lambda_{m+1}(\hat{\Sigma}_{Y})|} \| \hat{\Sigma}_{Y} - {\Sigma}_{Y} \|_{\text{op}} \leq \frac{2\sqrt{m}}{{\lambda_{m}^{p}}-\lambda_{m+1}^{p}} \| \hat{\Sigma}_{Y} - {\Sigma}_{Y} \|_{\text{op}}. $$

Due to result by [33], there exists $\tilde C$ so that for any $\delta \geq \exp (-n)$, the inequality

$$ \| \hat{\Sigma}_{Y} - {\Sigma}_{Y} \|_{\text{op}} \leq \tilde{C} ({\lambda_{1}^{p}}+\tilde\sigma^{2})(\sqrt{p/n}+\sqrt{\log(1/\delta)/n}) $$

holds with probability at least 1 − δ, and thus, if $2\tilde {C} ({\lambda _{1}^{p}}+\tilde \sigma ^{2})(\sqrt {p/n}+\sqrt {\log (1/\delta )/n}) <{\lambda _{m}^{p}}-\lambda _{m+1}^{p}$, then

$$ \begin{array}{@{}rcl@{}} \sin\angle({\mathcal{E}}^{p}_{m},\hat{\mathcal{E}}^{p}_{m}) \leq 2 \tilde{C}\sqrt{m}({\lambda_{m}^{p}}-\lambda_{m+1}^{p})^{-1} ({\lambda_{1}^{p}}+\tilde\sigma^{2})(\sqrt{p/n}+\sqrt{\log(1/\delta)/n}) \end{array} $$

holds with probability at least 1 − 2δ. Moreover, due to (25) and the fact that ${\lambda ^{p}_{j}}\leq \lambda _{j}$, we have ${\lambda _{m}^{p}}-\lambda _{m+1}^{p} \geq \lambda _{m}-\lambda _{m+1} - C {\lambda _{m}^{2}} {\epsilon _{p}^{2}}$ and ${\lambda ^{p}_{1}}+\tilde \sigma ^{2} \leq \lambda _{1}+\tilde \sigma ^{2}$, so the result (a) follows. For part (b), since $\mu _{p}=Q_{\mathcal {G}_{p}}\mu = (\varphi _{1},\ldots ,\varphi _{p}) \mu _{X}= (\varphi _{1},\ldots ,\varphi _{p})\mu _{Y}$, we have

$$ \begin{array}{@{}rcl@{}} \|\mu -\hat\mu_{p} \| &\leq& \|\mu - \mu_{p} \| + \|\mu_{p} - \hat\mu_{p} \| = \|Q_{\mathcal{G}_{p}^{\perp}}\mu \| + \|\hat{\mu}_{Y}-\mu_{Y}\|_{2} \\ &\leq& \|Q_{\mathcal{G}_{p}^{\perp}}\mu \| + \sqrt{n^{-1}\text{Tr}({\Sigma}_{X}+\tilde\sigma^{2} I_{p})} + \sqrt{2n^{-1}({\lambda_{1}^{p}}+\tilde\sigma^{2})\log(1/\delta^{\prime}) }, \end{array} $$

with probability at least $1-\delta ^{\prime }$, where in the last inequality we used the result by [32]. The final result then follows by using that ${\lambda ^{p}_{1}}\leq \lambda _{1}$. □

Proof of Theorem 2

First observe that for any $f\in {\mathscr{L}}_{2}(D;\mathbb {C})$ we have

$$ \begin{array}{@{}rcl@{}} \|Q_{\mathcal{F}_{q}^{\perp}} f\| &\leq& \|Q_{\mathcal{F}_{q}^{\perp}} Q_{\mathcal{E}_{m}} f \| + \|Q_{\mathcal{F}_{q}^{\perp}} (f- Q_{\mathcal{E}_{m}} f ) \| \\&\leq& \|f\| \sup_{\substack{\{g\in\mathcal{E}_{m}: \|g\|=1\}}} \| Q_{\mathcal{F}_{q}^{\perp}} g \| + \|Q_{\mathcal{E}_{m}^{\perp}} f \|. \end{array} $$

Since $\cos \limits \angle (\hat {\mathcal {E}}^{p}_{m},\mathcal {F}_{q})\geq 1 - \sup _{\substack {\{f\in \hat {\mathcal {E}}^{p}_{m}: \|f\|=1\}}} \|Q_{\mathcal {F}_{q}^{\perp }} f\|$, by using the above inequality we get

$$ \begin{array}{@{}rcl@{}} \cos\angle(\hat{\mathcal{E}}^{p}_{m},\mathcal{F}_{q}) &\geq 1 - \!\sup_{\substack{\{f\in\mathcal{E}_{m}: \|f\|=1\}}}\! \|Q_{\mathcal{F}_{q}^{\perp}} f\| - \!\sup_{\substack{\{f\in\hat{\mathcal{E}}^{p}_{m}: \|f\|=1\}}}\! \|Q_{\mathcal{E}_{m}^{\perp}} f\| \\ &= 1 - \sin\angle(\mathcal{E}_{m},\mathcal{F}_{q}) - \sin\angle(\mathcal{E}_{m},\hat{\mathcal{E}}_{m}^{p}). \end{array} $$

(27)

Define the event ${\Omega }:=\{\sin \limits \angle (\mathcal {E}_{m},\hat {\mathcal {E}}_{m}^{p})\leq \tilde \epsilon _{mpn\delta }\}$, which due to Lemma 1(a) is the event of probability at least 1 − δ. Due to 27 and since $\sin \limits \angle (\mathcal {E}_{m},\mathcal {F}_{q})<1-\tilde \epsilon _{mpn\delta }$, on Ω we have $\cos \limits \angle (\hat {\mathcal {E}}^{p}_{m},\mathcal {F}_{q}) > 0.$ Now define $\tilde {F}_{0}= {\sum }_{j=1}^{m} \tilde \alpha _{j} \hat {\phi _{j}^{p}}$ such that

$$ \{\tilde\alpha_{j}\}_{j=1}^{m} := \text{argmin}_{\{\alpha_{j}\}_{j=1}^{m}\in\mathbb{C}^{m}} \sum\limits_{k=1}^{q} \bigl| \langle F-\hat\mu_{p},\psi_{k} \rangle - \sum\limits_{j=1}^{m} \alpha_{j} {\langle\hat\phi^{p}_{j}},\psi_{k}\rangle \bigr|^{2}. $$

(28)

On Ω, by the GS result (5) and bound (27), we have

$$ \|\tilde{F}_{0} - (F-\hat\mu_{p}) \| \leq \frac{\|Q_{\hat{\mathcal{E}}_{m}^{p}}(F -\hat\mu_{p}) - (F-\hat\mu_{p})\|}{1 - \sin\angle(\mathcal{E}_{m},\mathcal{F}_{q}) - \tilde\epsilon_{mpn\delta}} . $$

(29)

Observe that

$$ \begin{array}{@{}rcl@{}} \|Q_{\hat{\mathcal{E}}_{m}^{p\perp}}(F -\hat\mu_{p}) \| &\leq& \|Q_{\hat{\mathcal{E}}_{m}^{p\perp}}(F -\mu) \| + \|Q_{\hat{\mathcal{E}}_{m}^{p\perp}}(\mu -\hat\mu_{p}) \| \\ &\leq& \|Q_{\hat{\mathcal{E}}_{m}^{p\perp}}Q_{\mathcal{E}_{m}} (F -\mu)\| + \| Q_{\hat{\mathcal{E}}_{m}^{p\perp}} Q_{\mathcal{E}_{m}^{\perp}} (F -\mu) \| + \|\mu - \hat\mu_{p} \| \\ &\leq& \sin\angle(\mathcal{E}_{m},\hat{\mathcal{E}}_{m}^{p})\|F-\mu\| + \| Q_{\mathcal{E}_{m}^{\perp}} (F-\mu) \| + \|\mu - \hat\mu_{p} \|. \end{array} $$

(30)

Define the event ${\Omega }^{\prime }=\{\|\mu -\hat \mu _{p}\|_{2}\leq \bar \epsilon _{np\delta ^{\prime }} \}$, which due to Lemma 1(b) happens with probability $1-\delta ^{\prime }$. Then, due to 29 and 30, on ${\Omega }\cap {\Omega }^{\prime }$ we have

$$ \|\tilde{F}_{0} - (F-\hat\mu_{p}) \| \leq \frac{ \tilde\epsilon_{mpn\delta}\|F-\mu\| + \| Q_{\mathcal{E}_{m}^{\perp}} (F-\mu) \| +\bar\epsilon_{np\delta^{\prime}} }{1 - \sin\angle(\mathcal{E}_{m},\mathcal{F}_{q}) - \tilde\epsilon_{mpn\delta}}. $$

(31)

Finally, define ${\Omega }^{\prime \prime }:=\bigl \{ \|\hat \alpha - \tilde \alpha \|_{2} \leq \sec \angle (\hat {\mathcal {E}}^{p}_{m},\mathcal {F}_{q}) \sigma \sqrt {(2m+2\log (1/\delta ^{\prime \prime })) /(qr_{1})} \bigr \}$, where vector $\tilde \alpha =(\tilde \alpha _{1},\ldots ,\tilde \alpha _{m})^{\top }$ is defined as in (26) and $\hat \alpha =(\hat \alpha _{1},\ldots ,\hat \alpha _{m})^{\top }$ is as in (19). On ${\Omega }\cap {\Omega }^{\prime }$, the probability of ${\Omega }^{\prime \prime }$ conditional on F₁,…,F_n,Z₁,…,Z_n (so that we are in the setting of a fixed design matrix) is at least $1 - \delta ^{\prime \prime }$, due to the result from [30]. Also, since 31 and

$$ \begin{array}{@{}rcl@{}} \|\hat{F}-F\| \leq \|\hat \alpha - \tilde\alpha\|_{2} + \|\tilde{F}_{0} - (F - \hat\mu_{p}) \|, \end{array} $$

the required bound holds on ${\Omega }\cap {\Omega }^{\prime }\cap {\Omega }^{\prime \prime }$, which has the probability at least $1 - \delta - \delta ^{\prime } - \delta ^{\prime \prime }$ because $\mathbb {P}({\Omega } \cap {\Omega }^{\prime } \cap {\Omega }^{\prime \prime }) \geq 1- \mathbb {P}(({\Omega } \cap {\Omega }^{\prime })^{\mathrm {c}}) -$. □