Error analysis for denoising smooth modulo signals on a graph

Introduction

This was the motivation behind the recent work of Cucuringu and Tyagi that focused primarily on the first (modulo denoising) stage, which is an interesting question by itself. Before discussing their result, it will be convenient to fix the notation used throughout the paper.

1 Denoising smooth modulo signals

which is the product manifold of unit radius circles, i.e., $\mathcal{C}_{n}=\mathcal{C}_{1}\times\cdots\times\mathcal{C}_{1}.$ Hence, by constructing a proximity graph $G=([n],E)$ on the sampling points $(x_{i})_{i=1}^{n}$ – where there is an edge between $i$ and $j$ if $x_{i}$ is within a specified distance of $x_{j}$ – they proposed solving a quadratically constrained quadratic program (QCQP)

where $L$ is the Laplacian of $G$, and $\gamma>0$ is a regularization parameter. While the objective function is convex, this is a non-convex problem due to the constraint set $\mathcal{C}_{n}$. It is not clear whether the global solution of (QCQP) can be obtained in polynomial time. Hence they proposed relaxing $\mathcal{C}_{n}$ to a sphere leading to the trust region subproblem (TRS)

On the other hand, one can show that $\left\|{z-h}\right\|_{2}^{2}\asymp\sigma^{2}n$ with high probability if $\sigma\lesssim 1$, hence we cannot conclude

This motivates the present paper which seeks to identify conditions under which (1.4) holds. In fact, we will consider a more abstract problem setting where $G$ is any connected graph, and $h\in\mathcal{C}_{n}$ is smooth w.r.t $G$. This is formally described below, followed by a summary of our main results.

2 Problem setup

Let $h=[h_{1},\dots,h_{n}]^{T}\in\mathcal{C}_{n}$ be an unknown ground truth signal which is assumed to be smooth w.r.t $G$ in the sense that

Given access to the noisy samples $z\in\mathcal{C}_{n}$, and the graph $G$, we aim to answer the following two questions.

This is a convex program, also referred to as Tikhonov regularization in the literature (e.g., ), and its solution is given in closed form by $\widehat{g}=(I+\gamma L)^{-1}z$. Under what conditions can we ensure that $\widehat{g}$ satisfies (1.4)?

Under what conditions can we ensure that the solution $\widehat{g}$ of (TRS) satisfies (1.4)?

As we will see in Section 4, the solution of (TRS) is closely related to that of (UCQP) but requires a more careful analysis.

It is worth mentioning that the quadratic penalty term $\gamma g^{*}Lg$ in (UCQP) and (TRS) aims to promote solutions $\widehat{g}$ which are smooth w.r.t $G$. This is natural given that the ground truth signal $h\in\mathcal{C}_{n}$ is assumed to be smooth w.r.t. $G$, as stated in (1.5). Moreover, the choice of the regularization parameter $\gamma$ is important since larger values of $\gamma$ increase the smoothness of the estimate (larger bias), while smaller values increase the variance of the estimate. For e.g., if we set $\gamma=0$, which is equivalent to removing the regularization term, then we obtain $\widehat{g}=z$. The main point of the ensuing analysis is to find a suitable “intermediate” choice of $\gamma$ which ensures that $\widehat{g}$ satisfies (1.4).

where $\eta_{i}$ are i.i.d. Then denoting $z_{i}=\exp(\iota 2\pi y_{i})$ and $h_{i}=\exp(\iota 2\pi f(x_{i}))$, we will consider $G=([n],E)$ to be the path graph ($P_{n}$), where

3 Main results

Before stating our results, let us define for any $\lambda\in[\lambda_{\min},\lambda_{1}]$, the set

consisting of indices corresponding to the “low frequency” part of the spectrum of $L$. Moreover, while all our results are non-asymptotic, we suppress constants in this section for clarity. The reader is referred to Appendix A for a tabular summary of the main notation used in the paper.

We begin by outlining our main results for the estimator (UCQP). Theorem 1 below identifies conditions on $\sigma$ under which (UCQP) provably denoises the samples in expectation. The statement is a simplified version of Theorem 4.

The parameter $\overline{\lambda}$ depends on the spectrum of the Laplacian and can be thought of as the “cut-off frequency”. As can be seen from Theorem 1, we would ideally like $\overline{\lambda}$ to be “large” and $\left|{\mathcal{L}_{\overline{\lambda}}}\right|$ to be “small”; in particular, $\left|{\mathcal{L}_{\overline{\lambda}}}\right|=o(n)$. For e.g., when $G$ is the complete graph Recall that in the complete graph, there is an edge $\left\{{i,j}\right\}$ for each $i\neq j$. ($K_{n}$), then $\lambda_{n}=0$ and $\lambda_{i}=n$ for $i=1,\dots,n-1$. Hence, the choice $\overline{\lambda}=n$ is ideal as it leads to $\left|{\mathcal{L}_{\overline{\lambda}}}\right|=0$. Furthermore, the noise regime in the Theorem involves a lower bound on $\sigma$ which might seem unnatural. We believe this is likely an artefact of the analysis involving the estimation error. Specifically, the error bound we obtain is of the form (see Lemma 3.1)

The problematic term is the first term which depends linearly on $\sigma$. Indeed, since $\left\|{z-h}\right\|_{2}^{2}\asymp\sigma^{2}n$ w.h.p, we end up with the lower bound requirement when $\sigma\ll 1$ for ensuring the denoising guarantee. Nevertheless, if $\frac{1}{\varepsilon\overline{\lambda}}\sqrt{\frac{{\triangle B_{n}}}{n}}=o(1)$ as $n$ increases, the requirement on $\sigma$ is of the form $o(1)\leq\sigma\lesssim 1$ which becomes progressively mild as $n$ increases.

We also derive conditions under which denoising occurs with high probabilityprobability approaching $1$ as $n\rightarrow\infty$. (w.h.p). Theorem 2 below is a simplified version of Theorem 6.

For any given $\varepsilon\in(0,1)$ and $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$, suppose that

If $\gamma\asymp(\frac{\sigma^{2}n}{\triangle B_{n}\overline{\lambda}^{2}})^{1/4}$, then w.h.p, the solution $\widehat{g}$ of (UCQP) satisfies $\left\|{\frac{\widehat{g}}{\left|{\widehat{g}}\right|}-h}\right\|_{2}^{2}\leq\varepsilon\left\|{z-h}\right\|_{2}^{2}$.

The conditions in Theorem 2 are slightly more stringent compared to those in Theorem 1 due to the appearance of extra $\log$ factors. These arise due to the concentration inequalities used in the analysis for bounding the estimation error, see Theorem 5.

In Section 3, we interpret our results for special graphs The choice of the graphs $K_{n},P_{n}$ and $S_{n}$ is only for convenience, one could consider other connected graphs as well. such as $K_{n},P_{n}$ and the star graph Recall that a star graph is a tree with one vertex having degree $n-1$, and the remaining $n-1$ vertices having degree $1$. ($S_{n}$); see Corollaries 2, 3. In particular, the statement for $P_{n}$ therein can be applied to the example from Section 1.2, readily yielding conditions that ensure denoising; see Corollary 4. It states that if $\frac{\log n}{\sqrt{n}}\lesssim\sigma\lesssim 1$ and $n\gtrsim 1$, then for $\gamma\asymp\left(\frac{\sigma^{2}n^{10/3}}{M^{2}}\right)^{1/4}$ the solution $\widehat{g}$ of (UCQP) satisfies (w.h.p)

Hence for any $\varepsilon\in(0,1)$, in the noise regime $\max\left\{{\frac{M}{\varepsilon n^{1/3}},\frac{\log n}{\sqrt{\varepsilon n}}}\right\}\lesssim\sigma\lesssim 1$, if $n\gtrsim(1/\varepsilon)^{3}$, then (UCQP) denoises $z$ w.h.p.

Results for (TRS).

We now describe conditions under which the estimator (TRS) provably denoises $z\in\mathcal{C}_{n}$ w.h.p. Theorem 3 below is a simplified version of Theorem 8.

For any $\varepsilon\in(0,1)$, given $k\in[n-1]$ s.t $\lambda_{n-k+1}<\lambda_{n-k}$ and $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$ with the choice $\gamma\asymp(\frac{\sigma^{2}n}{\triangle B_{n}\overline{\lambda}^{2}})^{1/4}$, suppose that the following conditions are satisfied.

$B_{n}\lesssim\min\left\{{n\lambda_{n-k},n\overline{\lambda}}\right\}$, and $1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|+\sqrt{(1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|)\log n}\lesssim\varepsilon n$.

$\sigma\lesssim\min\left\{{\sqrt{\varepsilon},\frac{\overline{\lambda}}{\lambda_{n-k+1}^{2}}\sqrt{\frac{\triangle B_{n}}{n}}}\right\}$ and

The above statement is admittedly more convoluted than that for $\eqref{prog:ucqp}$ which is primarily due to the more intricate nature of the estimation error analysis. An interesting aspect of the above result is that we can consider the “best” choice of $k$ (satisfying $\lambda_{n-k+1}<\lambda_{n-k}$) which leads to the mildest constraints on $\sigma$ and $B_{n}$. Note that since $G$ is connected (by assumption), $k=1$ always satisfies this condition ($0=\lambda_{n}<\lambda_{n-1}$). This leads to the following useful Corollary which is a simplified version of Corollary 6.

For any $\varepsilon\in(0,1)$ and $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$ with the choice $\gamma\asymp(\frac{\sigma^{2}n}{\triangle B_{n}\overline{\lambda}^{2}})^{1/4}$, suppose that the following conditions are satisfied.

$B_{n}\lesssim n\lambda_{\min}$ and $1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|+\sqrt{(1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|)\log n}\lesssim\varepsilon n$.

$\max\left\{{\left(\frac{\log n}{\sqrt{n}}\right)^{1/2},\frac{B_{n}}{n\lambda_{\min}\sqrt{\varepsilon}},\sqrt{\frac{\log n}{n}},\frac{1}{\varepsilon\overline{\lambda}}\sqrt{\frac{\triangle B_{n}}{n}}}\right\}\lesssim\sigma\lesssim\sqrt{\varepsilon}.$

It is natural to ask whether Corollary 1 is – for all practical purposes – sufficient, compared to Theorem 3. For the complete graph $K_{n}$, observe that the only valid choice is $k=1$, hence we need Corollary 1. However, as we will see in Section 4, it turns out that for the path graph $P_{n}$, Corollary 1 leads to unreasonably strict conditions on $\sigma$ and $B_{n}$ (see Remark 5). In fact for the path graph, $\lambda_{n-k+1}<\lambda_{n-k}$ holds for each $k\in[n-1]$, hence a careful choice of $k$ in Theorem 3 is key to obtaining satisfactory conditions, see Corollary 8.

In the setting of the example from Section 1.2, Corollary 8 roughly states that for any $\varepsilon\in(0,1)$, in the noise regime $(\frac{\log n}{\sqrt{n}})^{1/2}\lesssim\sigma\lesssim\sqrt{\varepsilon}$ with $n$ large enough and a suitably chosen $\gamma$, (TRS) denoises $z$ w.h.p. This condition on $\sigma$ is visibly stricter than that for (UCQP); we believe that this is likely an artefact of the analysis. Nevertheless, for this example, we see for $\varepsilon$ fixed and $n\rightarrow\infty$ that both (TRS) and (UCQP) provably denoise $z$ w.h.p in the noise regime $o(1)\leq\sigma\lesssim 1$.

Outline of the paper.

The rest of the paper is organized as follows. Section 2 introduces some preliminaries involving certain intermediate facts and technical results that will be needed in our analysis. Section 3 contains the analysis for (UCQP) while Section 4 analyzes (TRS). Section 5 contains some simulation results on synthetic examples for (UCQP) and (TRS). We conclude with Section 6 which contains a discussion with related work from the literature, and directions for future work.

Preliminaries

This section summarizes some useful technical tools that will be employed at multiple points in our analysis. We begin by deriving some simple consequences of the smoothness assumption in (1.5).

Similar to (1.8), for $\lambda\in[\lambda_{\min},\lambda_{1}]$, let us define the set

consisting of indices corresponding to the “high frequency” part of the spectrum of $L$. Then using (1.5) and the fact $\left\|{h}\right\|_{2}^{2}=n$, it is not difficult to establish that

Hence the smaller $B_{n}$ is, the more correlated $h$ is with the eigenvectors corresponding to $\left\{{n}\right\}\cup\mathcal{L}_{\lambda}$. It is also useful to note that since

hence $\left\|{Lh}\right\|_{2}^{2}\leq 2\triangle h^{*}Lh\leq 2\triangle B_{n}$ which is equivalent to

Finally, recall the setup in Section 1.2 where we obtain noisy modulo samples of a smooth function $f$ on a uniform grid (with $G=P_{n}$). In this setting, we can relate $B_{n}$ to the quadratic variation of $f$ on the grid. Indeed, using the fact $\left|{h_{i}-h_{i+1}}\right|\leq 2\pi\left|{f(x_{i})-f(x_{i+1})}\right|$ (see proof of [11, Lemma 8]), it follows that

Noise model.

Next, we collect some useful results related to the random noise model in (1.6). The following Proposition is easy to verify, its proof is provided in the appendix for completeness.

In particular, if $\sigma\leq\frac{1}{\pi\sqrt{2}}$ then the expected distance of $z$ from $h$ can be bounded as

We will also require several concentration bounds in order to derive high probability error bounds later on in our analysis.

With probability at least $1-\frac{4}{n^{2}}$,

With probability at least $1-\frac{2}{n^{2}}$,

With probability at least $1-\frac{2}{n^{2}}$,

With probability at least $1-\frac{2}{n^{2}}$,

In all the above inequalities, the event obtained by reversing both the inequality and the sign of the RHS term also holds with the stated probability of success.

Lastly, we will make extensive use of the following useful result from [21, Proposition 3.3] concerning the projection operator in (1.2).

It is especially important to note that for any number $t>0$, we have $\frac{w}{\left|{w}\right|}=\frac{tw}{\left|{tw}\right|}$. Hence from the above Proposition, it follows that $\left\|{\frac{w}{\left|{w}\right|}-g}\right\|_{q}\leq 2\left\|{tw-g}\right\|_{q}$ for any $t>0$. While it might be difficult to choose the optimal scale $t>0$ that minimizes the above bound, one could still choose a good surrogate that leads to an improvement over the bound obtained when $t=1$.

Error bounds for (UCQP)

We now analyse the quality of the solution $\widehat{g}=(I+\gamma L)^{-1}z$ of (UCQP). To begin with, we have the following Lemma that bounds the error between $\frac{\widehat{g}}{\left|{\widehat{g}}\right|}$ and $h$ for any $z\in\mathcal{C}_{n}$.

For any $z\in\mathcal{C}_{n}$ and $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$, it holds that

From the definition in (1.2), observe that $\frac{\widehat{g}}{\left|{\widehat{g}}\right|}=\frac{e^{{{2}\pi^{2}\sigma^{2}}}\widehat{g}}{\left|{e^{{{2}\pi^{2}\sigma^{2}}}\widehat{g}}\right|}$ where we recall $\widehat{g}=(I+\gamma L)^{-1}z$. We can write

which implies $\left\|{e^{{{2}\pi^{2}\sigma^{2}}}\widehat{g}-h}\right\|_{2}^{2}\leq 2(\left\|{e_{1}}\right\|_{2}^{2}+\left\|{e_{2}}\right\|_{2}^{2})$. Using Proposition 3, we then obtain

Using $h=\sum_{j=1}^{n}\langle q_{j},h\rangle q_{j}$, we can write $e_{2}$ as

This leads to the bound (using orthonormality of $q_{j}$’s)

where in the penultimate step, we used the identity

∎ The quantity $\overline{\lambda}$ depends on the graph $G$, and as we will see shortly, we will like to choose $\overline{\lambda}$ such that (a) $\left|{\mathcal{L}_{\overline{\lambda}}}\right|$ is small and, (b) $\sum_{j\in\mathcal{L}_{\overline{\lambda}}\cup\left\{{n}\right\}}\left|{\langle h,q_{j}\rangle}\right|^{2}\approx\left\|{h}\right\|_{2}^{2}=n$.

1 Error bounds in expectation

Let $z\in\mathcal{C}_{n}$ be generated as in (1.6) and assume $\sigma\leq\frac{1}{2\pi}$. Then for any given $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$, it holds that

In particular, if $\gamma=(\frac{4\pi^{2}\sigma^{2}n}{\triangle B_{n}\overline{\lambda}^{2}})^{1/4}$, we obtain the simplified bound

By taking the expectation of both sides of the inequality in Lemma 1, and using Proposition 1, we obtain

The bound in (3.1) now follows from the standard fact $e^{x}\leq 1+2x$ for any $x\leq 1$.

To obtain the bound in (3.2), we first use $1+\gamma\lambda_{\min}\geq 1$ and $1+\gamma\overline{\lambda}\geq\gamma\overline{\lambda}$ in (3.1) and observe that the resulting bound is a convex function of $\gamma$ minimized for the stated value of $\gamma$. Plugging this choice of $\gamma$ in (3.1) then yields (3.2). ∎

As can be seen from (3.2), there is a trade-off in the choice of $\overline{\lambda}$. We are now ready to state our first main theorem which establishes conditions under which (UCQP) provably denoises the input $z\in\mathcal{C}_{n}$. It follows easily from Lemma 2 and Proposition 1(v).

Let $z\in\mathcal{C}_{n}$ be generated as in (1.6), and $\varepsilon\in(0,1)$. For any given $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$ satisfying $1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|\leq\frac{\varepsilon n}{64}$, suppose that the noise level $\sigma$ satisfies

Then for the choice $\gamma=(\frac{4\pi^{2}\sigma^{2}n}{\triangle B_{n}\overline{\lambda}^{2}})^{1/4}$, the solution $\widehat{g}$ of (UCQP) satisfies

Finally, (3.4) is clearly ensured provided $1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|\leq\frac{\varepsilon n}{64}$ and

The condition $1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|\lesssim\varepsilon n$ in Theorem 4 implies that we require $\left|{\mathcal{L}_{\overline{\lambda}}}\right|=o(n)$ as $n$ increases, for fixed $\varepsilon$. In other words, $\overline{\lambda}$ should not be chosen to be too large.

The Theorem requires that the noise level lies in the regime $\frac{1}{\varepsilon\overline{\lambda}}\sqrt{\frac{{\triangle B_{n}}}{n}}\lesssim\sigma\lesssim 1$ for denoising. The lower bound therein is likely due to an artefact of the analysis, and arises from the first error term in (3.2) which scales as $\frac{\sigma}{\overline{\lambda}}\sqrt{\triangle B_{n}n}$. Nevertheless, if

then the condition on $\sigma$ weakens considerably as $n$ increases.

It is interesting to translate the conditions of Theorem 4 for special choices of $G$, namely $K_{n}$ (complete graph), $S_{n}$ (star graph) and $P_{n}$ (path graph). This leads to the following Corollary.

Let $z\in\mathcal{C}_{n}$ be generated as in (1.6), and $\varepsilon\in(0,1)$.

($G=K_{n}$) Suppose $n\gtrsim\frac{1}{\varepsilon}$ and $\frac{1}{n\varepsilon}\sqrt{B_{n}}\lesssim\sigma\lesssim 1$. If $\gamma\asymp(\frac{\sigma^{2}}{n^{2}B_{n}})^{1/4}$, then the solution $\widehat{g}$ of (UCQP) satisfies (3.3).

($G=S_{n}$) Suppose $n\gtrsim\frac{1}{\varepsilon}$ and $\frac{1}{\varepsilon}\sqrt{B_{n}}\lesssim\sigma\lesssim 1$. If $\gamma\asymp(\frac{\sigma^{2}}{B_{n}})^{1/4}$, then the solution $\widehat{g}$ of (UCQP) satisfies (3.3).

($G=P_{n}$) For a given $\theta\in[0,1)$, suppose $n\gtrsim(\frac{1}{\varepsilon})^{\frac{1}{1-\theta}}$ and $\frac{n^{\frac{3}{2}-2\theta}}{\varepsilon}\sqrt{B_{n}}\lesssim\sigma\lesssim 1$. If $\gamma\asymp(\frac{\sigma^{2}n^{5-4\theta}}{B_{n}})^{1/4}$, then the solution $\widehat{g}$ of (UCQP) satisfies (3.3).

The spectra of $L$ for $K_{n}$, $S_{n}$ and $P_{n}$ are well known, see for e.g. [8, Chapter 1].

Here, $\triangle=n-1$ and $\lambda_{n-1}=\cdots=\lambda_{1}=n$. Choose $\overline{\lambda}=n$ so that $\mathcal{L}_{\overline{\lambda}}=\emptyset$.

Here, $\triangle=n-1$ while $\lambda_{n-1}=\cdots=\lambda_{2}=1$ and $\lambda_{1}=n$. Choose $\overline{\lambda}=1$ so that $\mathcal{L}_{\overline{\lambda}}=\emptyset$.

Here, $\lambda_{j}=4(\sin^{2}[\frac{\pi}{2n}(n-j)])$ for $j=1,\dots,n$; hence

Choosing $\overline{\lambda}\asymp\frac{1}{n^{2(1-\theta)}}$ for $\theta\in[0,1)$, it is not difficult to see that $\left|{\mathcal{L}_{\overline{\lambda}}}\right|\lesssim n^{\theta}$, and so, $1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|\lesssim\varepsilon n$ provided $n\gtrsim(\frac{1}{\varepsilon})^{\frac{1}{1-\theta}}$. The conditions on $\sigma$ and $\gamma$ follow easily using $\triangle=2$.

For the graphs in Corollary 2, we can deduce conditions on the smoothness term $B_{n}$ which lead to a non-vacuous regime for $\sigma$, of the form $o(1)\leq\sigma\lesssim 1$. These are detailed below when $n\rightarrow\infty$.

($G=K_{n}$) If $\varepsilon$ is fixed, then $B_{n}=o(n^{2})$ suffices. On the other hand, if $\varepsilon=\varepsilon_{n}\rightarrow 0$ (as $n\rightarrow\infty$) and $\varepsilon_{n}=\omega(\frac{1}{n})$, then $B_{n}=o(\varepsilon_{n}^{2}n^{2})$ is sufficient.

($G=S_{n}$) For $\varepsilon$ fixed, it suffices that $B_{n}=o(1)$, while if $\varepsilon_{n}\rightarrow 0$ and $\varepsilon_{n}=\omega(\frac{1}{n})$, then $B_{n}=o(\varepsilon_{n}^{2})$ is sufficient.

($G=P_{n}$) For fixed $\varepsilon$, it is sufficient that $B_{n}=o(n^{4\theta-3})$, while the condition $B_{n}=o(\varepsilon_{n}^{2}n^{4\theta-3})$ suffices if $\varepsilon_{n}\rightarrow 0$ and $\varepsilon_{n}=\omega(\frac{1}{n^{1-\theta}})$.

2 High probability error bounds

We now proceed to derive high probability bounds on the estimation error when $z\in\mathcal{C}_{n}$ is generated randomly as in (1.6). We begin with a simplification of some of the bounds stated in Proposition 2 that we will need in our analysis.

If $\sigma\leq\frac{1}{2\sqrt{2}\pi}$, then

Recall that for $x\in$, we have $x/2\leq 1-e^{-x}\leq x$. Therefore if $8\pi^{2}\sigma^{2}\leq 1$, then

Using (3.5) in Proposition 2 (ii) with $k=1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|$ readily yields the statement.

Proof of (ii).

Using (3.5) in Proposition 2 (iv), we obtain w.p at least $1-\frac{2}{n^{2}}$ the bound

We now simplify the RHS of (3.6) by noting that if $\sigma\geq\frac{1}{6\pi\sqrt{n}}$ and $n\geq 2$, then

provided $\sigma\geq\frac{72\log n}{\pi\sqrt{n}}$.

Proof of (iii).

Using (3.5) in Proposition 2 (iii), we obtain w.p at least $1-\frac{2}{n^{2}}$ the bound

provided $\sigma\geq\frac{1}{6\pi\sqrt{n}}$ and $n\geq 2$ (using (3.7)). The condition $\sigma\geq\frac{72\log n}{\pi\sqrt{n}}$ then implies $\left\|{z-h}\right\|_{2}^{2}\geq\pi^{2}\sigma^{2}n$. ∎ We will now use Lemma 3 and Lemma 1 to obtain a high probability error bound on $\left\|{\frac{\widehat{g}}{\left|{\widehat{g}}\right|}-h}\right\|_{2}$.

We first simplify the bound in Lemma 1 with $1+\gamma\lambda_{\min}\geq 1$, $1+\gamma\overline{\lambda}\geq\gamma\overline{\lambda}$. Denoting $\overline{z}=e^{{-{2}\pi^{2}\sigma^{2}}}h$, this yields

Applying the bounds in (i),(ii) of Lemma 3 in (3.9), and observing that $e^{{{4}\pi^{2}\sigma^{2}}}\leq 1+8\pi^{2}\sigma^{2}\leq 2$ when $\sigma\leq\frac{1}{2\sqrt{2}\pi}$, we obtain with probability at least $1-\frac{4}{n^{2}}$ that

Plugging the stated choice of $\gamma$ in (3.10) leads to (3.8). ∎

By combining Lemma 3(iii) with Theorem 5, we obtain our main result that establishes conditions under which (UCQP) provably denoises $z$ with high probability.

Let $z\in\mathcal{C}_{n}$ be generated as in (1.6), and $\varepsilon\in(0,1)$. For any given $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$ suppose that

If $\gamma=(\frac{4\pi^{2}\sigma^{2}n}{\triangle B_{n}\overline{\lambda}^{2}})^{1/4}$, then with probability at least $1-\frac{6}{n^{2}}$, the solution $\widehat{g}$ of (UCQP) satisfies

Recall from Lemma 3(iii), that if $\frac{72\log n}{\pi\sqrt{n}}\leq\sigma\leq\frac{1}{2\sqrt{2}\pi}$ then $\left\|{z-h}\right\|_{2}^{2}\geq\pi^{2}\sigma^{2}n$ holds with high probability. Using (3.8) from Theorem 5, we hence note that (3.11) is ensured if

which in turn is ensured provided each LHS term of (3.12) is less than or equal to $\frac{\varepsilon\pi^{2}\sigma^{2}n}{3}$. Combining the resulting three conditions with the requirement $\frac{72\log n}{\pi\sqrt{n}}\leq\sigma\leq\frac{1}{2\sqrt{2}\pi}$, one can check that the stated conditions in the Theorem suffice. ∎

As in Corollary 2, we can translate the conditions of Theorem 6 for the special cases $G=K_{n},S_{n}$ or $P_{n}$. The proof is similar to that of Corollary 2 and hence omitted.

Let $z\in\mathcal{C}_{n}$ be generated as in (1.6), and $\varepsilon\in(0,1)$.

($G=K_{n}$) Suppose $\frac{n}{\sqrt{\log n}}\gtrsim\frac{1}{\varepsilon}$ and $\max\left\{{\frac{1}{n\varepsilon}\sqrt{B_{n}},\frac{\log n}{\sqrt{\varepsilon n}}}\right\}\lesssim\sigma\lesssim 1$. If $\gamma\asymp(\frac{\sigma^{2}}{n^{2}B_{n}})^{1/4}$, then the solution $\widehat{g}$ of (UCQP) satisfies (3.11) w.h.p.

($G=S_{n}$) Suppose $\frac{n}{\sqrt{\log n}}\gtrsim\frac{1}{\varepsilon}$ and $\max\left\{{\frac{1}{\varepsilon}\sqrt{B_{n}},\frac{\log n}{\sqrt{\varepsilon n}}}\right\}\lesssim\sigma\lesssim 1$. If $\gamma\asymp(\frac{\sigma^{2}}{B_{n}})^{1/4}$, then the solution $\widehat{g}$ of (UCQP) satisfies (3.11) w.h.p.

($G=P_{n}$) For a given $\theta\in[0,1)$, suppose $n^{\theta}+\sqrt{n^{\theta}\log n}\lesssim\varepsilon n$ and $\max\left\{{\frac{n^{\frac{3-4\theta}{2}}}{\varepsilon}\sqrt{B_{n}},\frac{\log n}{\sqrt{\varepsilon n}}}\right\}\lesssim\sigma\lesssim 1$. If $\gamma\asymp(\frac{\sigma^{2}n^{5-4\theta}}{B_{n}})^{1/4}$, then the solution $\widehat{g}$ of (UCQP) satisfies (3.11) w.h.p.

As in Remark 2, we can deduce conditions on the smoothness term $B_{n}$ which lead to a non-vacuous regime for $\sigma$ of the form $o(1)\leq\sigma\lesssim 1$. These are detailed below when $n\rightarrow\infty$.

($G=K_{n}$) If $\varepsilon$ is fixed then $B_{n}=o(n^{2})$ suffices while if $\varepsilon=\varepsilon_{n}\rightarrow 0$ and $\varepsilon_{n}=\omega(\frac{\log n}{\sqrt{n}})$, then $B_{n}=o(\varepsilon_{n}^{2}n^{2})$ is sufficient.

($G=S_{n}$) If $\varepsilon$ is fixed then $B_{n}=o(1)$ suffices while if $\varepsilon_{n}\rightarrow 0$ and $\varepsilon_{n}=\omega(\frac{\log n}{\sqrt{n}})$, then $B_{n}=o(\varepsilon_{n}^{2})$ is sufficient.

($G=P_{n}$) For fixed $\varepsilon$, it is sufficient that $B_{n}=o(n^{4\theta-3})$. On the other hand, if $\varepsilon_{n}\rightarrow 0$ and $\varepsilon_{n}=\omega(\max\{\frac{\log n}{\sqrt{n}},\frac{n^{\theta}+\sqrt{n^{\theta}\log n}}{n}\})$ then the condition $B_{n}=o(\varepsilon_{n}^{2}n^{4\theta-3})$ suffices.

Denoising modulo samples of a function.

If $\frac{\log n}{\sqrt{n}}\lesssim\sigma\lesssim 1$ and $n\gtrsim 1$ then w.h.p,

For $\varepsilon\in(0,1)$, if $n\gtrsim(1/\varepsilon)^{3}$ and $\max\left\{{\frac{M}{\varepsilon n^{1/3}},\frac{\log n}{\sqrt{\varepsilon n}}}\right\}\lesssim\sigma\lesssim 1$, then $\widehat{g}$ satisfies (3.11) w.h.p.

where the penultimate inequality uses the Lipschitz continuity of $f$, and the last inequality uses $n-1\geq n/2$.

For the first part, recall from Corollary 2 (iii) that $\overline{\lambda}\asymp\frac{1}{n^{2(1-\theta)}}$ for $\theta\in[0,1)$, which implies $\left|{\mathcal{L}_{\overline{\lambda}}}\right|\lesssim n^{\theta}$. Applying this along with (3.13) to Theorem 5, we obtain the bound

Notice that we need $1/2<\theta<1$ to get a non-trivial bound. The choice $\theta=2/3$ “balances” the exponents of $n$, and if moreover $n\gtrsim 1$, then we obtain the statement of the first part.

The second part follows easily by plugging (3.13) along with $\theta=2/3$ in Corollary 3(iii). ∎

Error bounds for (TRS)

where $\otimes$ denotes the Kronecker product. Then it is easy to check that (TRS) is equivalent to

Note that the above Lemma’s do not require any sphere constraint on $\overline{z},z$. We now use Lemma 5 to derive the following crucial Lemma which states upper and lower bounds on $\mu^{\star}$. The notation $\mathcal{N}(L)$ is used to denote the null space of $L$, which is the span of $q_{n}$ since $G$ is connected by assumption.

For any $z\in\mathcal{C}_{n}$ satisfying $z\not\perp$ $\mathcal{N}(L)$, we have that $\widehat{g}=2(2\gamma L+\mu^{\star}I)^{-1}z$ is the unique solution of (TRS) with $\mu^{\star}\in(0,2]$. Additionally, if $\widetilde{\lambda}$ is an eigenvalue of $L$ satisfying

If $z\not\perp$ $\mathcal{N}(L)$ then is a pole of $\phi$. Hence there exists a unique $\mu^{\star}\in(0,\infty)$ such that $\widehat{g}=2(2\gamma L+\mu^{\star}I)^{-1}z$ is a (unique) solution of (TRS) as it satisfies the conditions in Lemma 5. Since $n=\left\|{\widehat{g}}\right\|_{2}^{2}\leq\frac{4n}{(\mu^{\star})^{2}}$, we obtain $\mu^{\star}\leq 2$. To obtain the lower bound on $\mu^{\star}$, note that (4.1) implies

which leads to the stated lower bound on $\mu^{\star}$. ∎

Next, we bound the the error between $\frac{\widehat{g}}{\left|{\widehat{g}}\right|}$ and $h$ for any $z\in\mathcal{C}_{n}$ such that $z\not\perp\mathcal{N}(L)$.

For any $z\in\mathcal{C}_{n}$ such that $z\not\perp$ $\mathcal{N}(L)$, and $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$, the (unique) solution $\widehat{g}=2(2\gamma L+\mu^{\star}I)^{-1}z$ of (TRS) satisfies the bound

with $E_{1},E_{2}$ as defined in Lemma 1, and $\mu^{\star}\in(0,2]$.

The proof is along the lines of Lemma 1 with only few technical differences. Firstly, we can write

which in conjunction with Proposition 3 leads to the bound

Proceeding identically to the proof of Lemma 1, it is easy to verify that $\left\|{e_{1}}\right\|_{2}^{2}\leq\frac{4}{(\mu^{\star})^{2}}E_{1}$. In order to bound $\left\|{e_{2}}\right\|_{2}^{2}$, we begin by expanding $e_{2}$ as

Then using the orthonormality of $q_{j}$’s, we can bound $\left\|{e_{2}}\right\|_{2}^{2}$ as follows.

where in the last inequality, we used (2.1),(2.2). ∎

When $z\in\mathcal{C}_{n}$ is generated as in (1.6), the following Lemma presents a (high probability) lower bound on $\mu^{\star}$ provided $\sigma$ is small and $h$ is sufficiently smooth.

Let $z\in\mathcal{C}_{n}$ be generated as in (1.6), then the solution of $\eqref{prog:trs}$ is unique. Moreover, suppose that for any given $k\in[n-1]$ s.t $\lambda_{n-k+1}<\lambda_{n-k}$, the following holds.

Then with probability at least $1-\frac{4}{n^{2}}$, we have that

We will lower bound the lower bound estimate of $\mu^{\star}$ from Lemma 6 using Proposition 2(i). Note that $z\in\mathcal{C}_{n}$ satisfies $z\not\perp\mathcal{N}(L)$ a.s. Set $\widetilde{\lambda}=\lambda_{n-k+1}$ in Lemma 6, and let $U$ denote the $n\times k$ matrix consisting of $q_{j}$’s for $n-k+1\leq j\leq n$.

Let us first simplify the statement of Proposition 2(i) when $\sigma^{2}\leq\frac{1}{8\pi^{2}}$. Recall from the proof of Lemma 3 that this implies $1-e^{{-{8}\pi^{2}\sigma^{2}}}\in[4\pi^{2}\sigma^{2},8\pi^{2}\sigma^{2}]$. Then the (magnitude of the) RHS of the bound in Proposition 2(i) can be upper bounded as

where the last inequality uses $\sigma^{2}\leq\sigma$ and $k\leq n$.

Plugging (4.3) in Proposition 2 (i), we conclude that with probability at least $1-\frac{4}{n^{2}}$,

Using (4.2), we have $\frac{B_{n}}{n\lambda_{n-k}}+4\pi^{2}\sigma^{2}+\frac{24760\log n}{\sqrt{n}}\leq\frac{1}{4}$. This leads to the bound

which in conjunction with Lemma 6 leads to the stated bound on $\mu^{\star}$. In particular, the conditions in (4.2) ensure $\mu^{\star}\geq 1$. ∎

Using Lemmas 7 and 8, we arrive at the following (high probability) bound on the error $\left\|{\frac{\widehat{g}}{\left|{\widehat{g}}\right|}-h}\right\|_{2}^{2}$ for the solution $\widehat{g}$ of $\eqref{prog:trs}$.

Let $z\in\mathcal{C}_{n}$ be generated as in (1.6), then the solution $\widehat{g}$ of (TRS) is unique. For any given $k\in[n-1]$ s.t $\lambda_{n-k+1}<\lambda_{n-k}$, and any $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$ with the choice $\gamma=(\frac{4\pi^{2}\sigma^{2}n}{\triangle B_{n}\overline{\lambda}^{2}})^{1/4}$, suppose that the following conditions are satisfied.

$B_{n}\leq\min\left\{{\frac{n\lambda_{n-k}}{12},\frac{n\overline{\lambda}}{2}}\right\}$, and

$286\left(\frac{\log n}{\sqrt{n}}\right)^{1/2}\leq\sigma\leq\min\left\{{\frac{1}{4\sqrt{3}\pi},\frac{\overline{\lambda}}{16\lambda_{n-k+1}^{2}}\sqrt{\frac{\triangle B_{n}}{4\pi^{2}n}}}\right\}$.

where $C_{1}=288\pi$, $C_{2}=396160$, $C_{3}=230400$, $C_{4}=262144$, $C_{5}=144$.

We simply combine Lemmas 7 and 8. To this end, recall that the error bound in Theorem 5 is a bound on the term $8(E_{1}+E_{2})$. This means that if $\frac{72\log n}{\pi\sqrt{n}}\leq\sigma\leq\frac{1}{2\sqrt{2}\pi}$, then for the stated choice of $\gamma$, we have with probability at least $1-\frac{4}{n^{2}}$,

The conditions in Lemma 8 imply in particular that $\mu^{\star}\geq 1$, hence (4.5) is a bound on $\frac{32(E_{1}+E_{2})}{\mu^{\star}}$. This takes care of the first error term in the bound in Lemma 7.

In order to bound the second term therein, observe that if $B_{n}\leq\frac{n\overline{\lambda}}{2}$, then

Also, condition (ii) for $\sigma$ implies $24760\frac{\log n}{\sqrt{n}}\leq\frac{3\sigma^{2}}{\pi^{2}}(\leq\frac{1}{12})$. Note that the requirement $\sigma\geq 286(\frac{\log n}{\sqrt{n}})^{1/2}$ is stricter than $\sigma\geq\frac{72\log n}{\pi\sqrt{n}}$. Given these observations, we can bound the second term in the bound of Lemma 7 as follows.

Plugging (4.5) and (4.6) in Lemma 7 then readily yields the stated bound in the Theorem. ∎

The following Corollary provides a simplification of Theorem 7 and is directly obtained by considering $k=1$ since $\lambda_{n}<\lambda_{n-1}=\lambda_{\min}$.

Let $z\in\mathcal{C}_{n}$ be generated as in (1.6), then the solution $\widehat{g}$ of (TRS) is unique. For given $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$ with the choice $\gamma=(\frac{4\pi^{2}\sigma^{2}n}{\triangle B_{n}\overline{\lambda}^{2}})^{1/4}$, suppose that

where the constants $C_{1},\dots,C_{5}$ are as in Theorem 7.

We are now in a position to derive conditions under which (TRS) provably denoises $z$ with high probability. We begin with the following Theorem which provides these conditions in their full generality.

Let $z\in\mathcal{C}_{n}$ be generated as in (1.6), then the solution $\widehat{g}$ of (TRS) is unique. With constants $C_{1},\dots,C_{5}$ as in Theorem 7, for any $\varepsilon\in(0,1)$, given $k\in[n-1]$ s.t $\lambda_{n-k+1}<\lambda_{n-k}$ and $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$ with the choice $\gamma=(\frac{4\pi^{2}\sigma^{2}n}{\triangle B_{n}\overline{\lambda}^{2}})^{1/4}$, suppose that the following conditions are satisfied.

$B_{n}\leq\min\left\{{\frac{n\lambda_{n-k}}{12},\frac{n\overline{\lambda}}{2}}\right\}$, and $1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|+\sqrt{(1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|)\log n}\leq\frac{\pi^{2}}{5C_{2}}\varepsilon n$.

$\sigma\leq\min\left\{{\frac{\pi\sqrt{\varepsilon}}{\sqrt{5C_{3}}},\frac{\overline{\lambda}}{16\lambda_{n-k+1}^{2}}\sqrt{\frac{\triangle B_{n}}{4\pi^{2}n}}}\right\}$ and

Recall from Lemma 3 (iii), that $\left\|{z-h}\right\|_{2}^{2}\geq\pi^{2}\sigma^{2}n$ w.p at least $1-\frac{2}{n^{2}}$. Conditioning on the intersection of this event and the event in Theorem 7, it suffices to ensure that the bound in (4.4) is less than or equal to $\pi^{2}\sigma^{2}n\varepsilon$. This in turn is ensured provided each term in the RHS of (4.4) is less than or equal to $\varepsilon\frac{\pi^{2}\sigma^{2}n}{5}$. Combining the resulting conditions with those in Theorem 7 yields the statement of the Theorem. ∎

The following simplification of Theorem 8 is obtained for $k=1$, as was done in Corollary 5.

Let $z\in\mathcal{C}_{n}$ be generated as in (1.6), then the solution $\widehat{g}$ of (TRS) is unique. With constants $C_{1},\dots,C_{5}$ as in Theorem 7, for any $\varepsilon\in(0,1)$ and $\overline{\lambda}\in[\lambda_{\min},\lambda_{1}]$ with the choice $\gamma=(\frac{4\pi^{2}\sigma^{2}n}{\triangle B_{n}\overline{\lambda}^{2}})^{1/4}$, suppose that the following conditions are satisfied.

$B_{n}\leq\frac{n\lambda_{\min}}{12}$ and $1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|+\sqrt{(1+\left|{\mathcal{L}_{\overline{\lambda}}}\right|)\log n}\leq\frac{\pi^{2}}{5C_{2}}\varepsilon n$.

Finally, as done previously for (UCQP), it will be instructive to translate Theorem 8 for the special cases $G=K_{n}$, $S_{n}$ or $P_{n}$. This is stated below using the simplified version in Corollary 6.

Let $z\in\mathcal{C}_{n}$ be generated as in (1.6) and $\varepsilon\in(0,1)$.

($G=K_{n}$) Suppose $\frac{n}{\sqrt{\log n}}\gtrsim\frac{1}{\varepsilon}$, $B_{n}\lesssim n^{2}$ and $\max\left\{{\frac{\sqrt{B_{n}}}{n\varepsilon},\frac{B_{n}}{n^{2}\sqrt{\varepsilon}},(\frac{\log n}{\sqrt{n}})^{1/2},(\frac{\log n}{\varepsilon n})^{1/2}}\right\}\lesssim\sigma\lesssim\sqrt{\varepsilon}$. If $\gamma\asymp(\frac{\sigma^{2}}{n^{2}B_{n}})^{1/4}$, then the (unique) solution $\widehat{g}$ of (TRS) satisfies (4.7) w.h.p.

($G=S_{n}$) Suppose $\frac{n}{\sqrt{\log n}}\gtrsim\frac{1}{\varepsilon}$, $B_{n}\lesssim n$ and $\max\left\{{\frac{\sqrt{B_{n}}}{\varepsilon},\frac{B_{n}}{n\sqrt{\varepsilon}},(\frac{\log n}{\sqrt{n}})^{1/2},(\frac{\log n}{\varepsilon n})^{1/2}}\right\}\lesssim\sigma\lesssim\sqrt{\varepsilon}$. If $\gamma\asymp(\frac{\sigma^{2}}{B_{n}})^{1/4}$, then the (unique) solution $\widehat{g}$ of (TRS) satisfies (4.7) w.h.p.

($G=P_{n}$) For a given $\theta\in[0,1)$, suppose $n^{\theta}+\sqrt{n^{\theta}\log n}\lesssim\varepsilon n$, $B_{n}\lesssim\frac{1}{n}$ and

If $\gamma\asymp(\frac{\sigma^{2}n^{5-4\theta}}{B_{n}})^{1/4}$, then the (unique) solution $\widehat{g}$ of (TRS) satisfies (4.7) w.h.p.

Use Corollary 6 with $\lambda_{\min},\overline{\lambda}$ as in Corollary 2. ∎

For $K_{n}$, note that only $k=1$ meets the requirement of Theorem 8 since $\lambda_{n-1}=\cdots=\lambda_{1}$. For $S_{n}$, the only other possibility (apart from $k=1$) is to choose $k=n-1$, since $\lambda_{2}=1<\lambda_{1}=n$. But this choice of $k$ leads to a vacuous noise regime due to the appearance of the term $\sqrt{B_{n}}+\frac{1}{\sqrt{B_{n}}}$ as a lower bound on $\sigma$.

Similarly to Remark 3 for (UCQP), we can deduce conditions on the smoothness term $B_{n}$ which – when $n\rightarrow\infty$ – lead to a non-vacuous regime for $\sigma$ of the form $o(1)\leq\sigma\lesssim\sqrt{\varepsilon}$. Here, we will only treat the case where $\varepsilon$ is fixed.