Uniform Chebyshev approximations of functions satisfying a variation-type condition: reconstruction of time-varying signals on graphs

1. Introduction

• For large graphs, Chebyshev approximation avoids the need to calculate the entire Laplacian spectrum when approximating the kernels.The paper extends this motivation from time-independent kernels to kernels defined on a two-variable rectangle.Source: §1 · pp. 1–2
• A continuous function on the square satisfying a variation-type condition has a uniformly convergent Chebyshev expansion in the first variable.The paper uses this theorem to approximate the time-varying scaling and wavelet functions.Source: §1 · p. 2
• The approximants use time-varying coefficients whose polynomial degree does not depend on time.The coefficients characterize the approximants at each time and may be computed directly once the scaling and wavelet functions are given.Source: §1 · p. 3
• The reconstruction framework targets time-varying graph signals and scaling and wavelet kernels that depend on a continuous time variable.The kernels are defined over two variables, motivating an extension of the approximation procedure to two variables.Source: §1 · pp. 1–3
• The paper adapts an existing graph-signal reconstruction scheme to continuous-time signals and studies uniform approximation error bounds.The introduction notes that any C1 function satisfies the stated variation-type condition and that additional differentiability in x yields an error bound.Source: §1 · p. 3

2.1. Weighted Graphs and Laplacian.

• The setting uses finite, connected, undirected weighted graphs; their Laplacians are real symmetric with nonnegative eigenvalues.The graph has positive edge weights, and its Laplacian admits an orthogonal spectral decomposition.Source: §2.1 · p. 4

2.2. Graph Fourier Transform of a time-varying signal.

• The Graph Fourier Transform is applied to the signal separately at each fixed time, using the Laplacian eigenbasis.The inverse transform is defined on spectral data.Source: §2.2 · p. 5

2.3. Overall Graph Wavelet Transform of a time-varying signal.

• The overall Graph Wavelet Transform combines scaling and wavelet operators whose kernels can vary with time.For fixed time, the wavelet operator is defined through the graph spectrum and is self-adjoint.Source: §2.3 · pp. 6–7
• Under joint continuity and positivity assumptions, the transform has frame bounds independent of time on the specified compact time interval.The bounds obtained from minima and maxima over the spectral interval are valid but need not be optimal.Source: §2.3 · p. 8
• Because exact Laplacian eigenvalues can be difficult to obtain for large graphs, the reconstruction scheme uses Chebyshev kernel approximations and a pseudoinverse.The paper states that the signal can then be recovered up to computational errors.Source: §2.3 · pp. 8–9

3.1. Chebyshev polynomials in R.

• In one variable, continuous functions of bounded variation or satisfying a Dini–Lipschitz condition have uniformly convergent Chebyshev series, and product identities allow coefficients of polynomial squares to be computed from the original coefficients.Source: §3.1 · p. 10

3.2. Chebyshev polynomials in R2.

• A time-varying-coefficient Chebyshev expansion mirrors the reconstruction scheme in and reduces the computations complicated by nine cases in the direct two-variable approach.Source: §3.3 · p. 11, §3.2 · p. 11

3.3. Main results.

• A continuous f satisfying a variation-type condition on the square has a uniformly convergent Chebyshev expansion, without assumptions on derivative behavior.The proof establishes uniform equicontinuity of the partial sums and uses their pointwise convergence to obtain uniform convergence.Source: §3.3 · pp. 13–14
• If the partial sums also converge to f in the sense of bounded variation through condition (ii), f has a uniformly convergent double Chebyshev series.The result also holds with the two variables interchanged.Source: §3.3 · p. 15
• Every C2 function has a uniform double Chebyshev series expansion; more generally, the corollary assumes a variation-type condition on f and on one continuous partial derivative.Source: §3.3 · p. 16
• The double-series approach has more challenging formulas but gives uniform convergence of canonical rectangular partial sums for sufficiently regular functions; the alternative has easier time-varying coefficient formulas.The alternative yields the exact form of the approximate transform composition for all time points, while the double-series approach has constant expansion coefficients.Source: §3.3 · p. 17
• For any continuous g, TK(g) is well defined without a variation-type condition and gives a near-best uniform approximation up to a logarithmically growing factor.Source: §3.3 · p. 18
• For g that is (m+1)-times continuously differentiable in x, Theorem 3.13 gives a uniform error bound for TK(g) with a constant independent of K.Source: §3.3 · pp. 18–19

Composition formula

• The approximate transform composed with its adjoint has explicit time-varying coefficient formulas, following the time-independent construction.Its polynomial degree bound does not depend on time, and each coefficient is a finite sum of products of integrals.Source: §4 · pp. 19–21

Uniform kernel approximations

• Uniformly convergent Chebyshev expansions approximate the time-varying kernels with degrees chosen independently of time.The expansion coefficients depend on time, and the partial sums converge uniformly on the spectral and time domain.Source: §4 · pp. 19–20

Stable reconstruction

• The approximate transform's pseudoinverse gives stable reconstruction when the uniform kernel errors are sufficiently small.Uniform convergence lets the approximation errors decrease as the polynomial degrees increase, satisfying the stated small-error condition under the frame assumptions.Source: §4 · pp. 21–22

5.1. Graph, time-varying signal, and noise model.

• The test uses a 500-vertex sensor graph and compares reconstructions over 101 equally spaced times and 100 independent noise perturbations.The graph, noise-free signal, and noise realizations are held fixed across comparisons.Source: §5.1 · pp. 22–23, Figure 5.1 · p. 23

5.2. Kernels, uniform approximation, and stability.

• On the sampled [0, 1] × [5, 800] domain, the combined kernel error decreases from 6.38 × 10^-2 at K = 8 to 6.34 × 10^-6 at K = 40, while the minimum observed s_K is 0.95.The reported inequalities hold at every tested degree, and the reconstruction systems are described as well conditioned.Source: §5.2 · p. 25, Figure 5.2 · p. 25

5.3. Soft thresholding of the graph wavelet coefficients.

• SURE selects parameters from noisy data alone; the proposed method uses one threshold factor over the full interval and allows the transform parameter to vary with time.The comparison uses one parameter pair across all sampled times, and both methods share the same reconstruction map.Source: §5.3 · p. 26

5.4. Chebyshev denoising and convergence.

• The time-varying method has lower mean squared error than the time-independent method at every tested degree; with the exact transform, it reduces overall mean squared error by 4.23%.Table 5.2 holds the parameters selected in Subsection 5.3 fixed across degrees.Source: Table 5.2 · p. 28, §5.4 · p. 28
• The time-varying reconstruction error E_K falls from 2.11 × 10^-3 at K = 8 to 2.14 × 10^-7 at K = 40.Conjugate gradient requires at most 8 iterations at K = 8 and at most 2 at K = 40.Source: §5.4 · pp. 28–29, Table 5.2 · p. 28

• For continuous functions satisfying a variation-type condition, the paper proves uniform Chebyshev approximation on the square and a double-series version with uniform error bounds.The scaling and wavelet kernels admit time-varying coefficient expansions with degrees independent of time; the approximate transform composition retains the time-independent explicit coefficient formulas, and reconstruction is stable with bounds in terms of uniform kernel errors.Source: §6 · p. 29
• The time-varying method consistently attains smaller mean squared error than the time-independent method in sensor-network denoising.The method soft-thresholds graph wavelet coefficients and reconstructs by solving the associated normal equations.Source: §6 · p. 29
• On the sensor network, sampled uniform errors decay rapidly with degree, and stability inequalities hold on the validation grid at all tested degrees.Source: §6 · p. 29

• T_m,n(x, y) is written as a six-term sum pairing u_m, v_m, and w_m with u_-n, v_-n, and w_-n.Source: Appendix A · p. 29
• Straightforward calculations yield the six expansions used in the proof.Source: Appendix A · pp. 29–30
• Summing the six expansions and comparing them with the expansion of T_m,n(x, y)T_k,ℓ(x, y) yields the assertion.Source: Appendix A · p. 30