Optimal linear subdivision rules for noisy data

Sergio López-Ureña, Dionisio F. Yáñez · 2024

Read Optimal linear subdivision rules for noisy data by Sergio López-Ureña, Dionisio F. Yáñez (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01287.txt.

Introduction

Sergio López-Ureña and Dionisio Yáñez build better rules for smoothing noisy data, in a 2024 preprint whose head title reads Linear minimum-variance approximants for noisy data. Smoothing rules rebuild a curve from samples, but noise in the samples leaks into the result. The pair weight each sample so the spread of the output noise drops as low as it can go. Their weights draw on two classic ideas from statistics for fitting lines to messy data.

With the help of operators that wipe out smooth trends, they derive formulas that work for tangled, uneven noise. Older rules turn out to be the best choice only when the noise at each point stands alone. Tests on sample data back the claim: when noise links across points, the new rules beat the ones in use today. The result gives curve builders a sharper tool for real-world signals.

Catalog record

CREATORSergio López-Ureña, Dionisio F. Yáñez
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-01287

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimal linear subdivision rules for noisy data Sergio López-Ureña, Dionisio F. Yáñez Abstract Subdivision schemes are iterative processes that recursively refine data by applying subdivision rules. This paper introduces linear subdivision rules tailored to handle noisy data. A key innovation lies in determining the rule coefficients by solving an optimization problem aimed at minimizing the noise variance. The study addresses the general case, allowing for noise correlation among data with a non-uniform distribution. In fact, we show that the subdivision rules, proposed in [S. López-Ureña and D. F. Yáñez, J. Sci. Comput. , 100(1) (2024)], are optimal for uncorrelated noise with non-uniform variance. Numerical experiments are provided to demonstrate the effectiveness of these optimal rules compared to other subdivision rules designed for noisy data. 1 Introduction Subdivision schemes are widely recognized as a powerful tool for designing functions, including curves and surfaces, due to their simplicity and computational efficiency (see, e.g., [ 4 ] ). These methods have found applications in various fields, such as computer graphics, image processing, and others (see, e.g., [ 1 , 7 ] ). The process involves iteratively refining an initial dataset by applying a predefined set of subdivision rules, generating a sequence that may converge to a continuous—or even smooth—function. Subdivision theory focuses on analyzing the properties of the limit function derived from the given subdivision rules [ 2 ] . In certain applications, noisy data are managed, requiring the use of specialized subdivision schemes. To address this, Dyn et al. [ 3 ] proposed a novel scheme based on solving least squares problems. While this approach effectively reduces noise, it exhibits limited capability in approximating smooth functions. To mitigate this limitation, the authors of [ 6 ] introduced a weight function within the least squares formulation, achieving a more balanced trade-off between noise reduction and approximation performance. The goal of this paper is to derive rules that maximize noise reduction while preserving a specified approximation order. Let \bm{f}=(f_{i})_{i=1}^{N} represent a dataset associated with the grid \bm{x}=(x_{i})_{i=1}^{N}\in\mathds{R}^{N} , x_{i}<x_{i+1} where h=\max\{x_{i+1}-x_{i}\ :\ i=1,\ldots,N-1\} . We assume the data is composed of two components: noise and samples of a smooth function g:\mathds{R}\longrightarrow\mathds{R} . Specifically, \bm{f}=g|_{\bm{x}}+\bm{e}\in\mathds{R}^{N} , where g|_{\bm{x}}:=(g(x_{i}))_{i=1}^{N} and the noise \bm{e}\sim\bm{E}, being \bm{E} a vector of probability distributions with zero mean, \mathbb{E}\left(\bm{E}\right)=0. Our objective is to determine coefficients \bm{a}\in\mathds{R}^{N} for a linear rule, \Psi(\bm{f}):=\sum_{i=1}^{N}a_{i}f_{i} , such that \Psi(\bm{f})\approx g(t_{0}) for a given t_{0}\in[x_{1},x_{N}] , achieving a specified accuracy while minimizing the influence of \bm{e} . We begin by presenting the solution to the proposed problem and establishing its connection to prior research. Then some experiments are performed to demonstrate the effectiveness of the proposed rules in comparison to other subdivision rules for noisy data. 2 Designing linear rules to minimize noise under prescribed approximation capability Since \Psi is linear, \Psi(g|_{\bm{x}}+\bm{e})=\Psi(g|_{\bm{x}})+\Psi(\bm{e}) . We propose to split the problem into two parts. One takes care of approximating the smooth function and the other one tries to reduce the noise as much as possible. On the one hand, we may solve the smooth problem \Psi(g|_{\bm{x}})=g(t_{0})+O(h^{d}) that is achieved by imposing to \Psi the reproduction of polynomials up to d-1 degree, \Pi_{d-1} , as well known in subdivision theory. For this, we introduce the following definitions. Definition 1 . A rule \Psi:\mathds{R}^{N}\longrightarrow\mathds{R} reproduces \Pi_{d} with the setting (\bm{x},t_{0}) if \Psi(g|_{\bm{x}})=g(t_{0}),\,\,\forall g\in\Pi_{d}. Definition 2 . A rule \Psi:\mathds{R}^{N}\longrightarrow\mathds{R} has approximation order d with the setting (\bm{x},t_{0}) with h=\max\{x_{i+1}-x_{i}\ :\ i=1,\ldots,N-1\} if \Psi(g|_{\bm{x}})=g(t_{0})+O(h^{d}) is fulfilled for any function g\in\mathcal{C}^{d} . That is, if for each g\in\mathcal{C}^{d} there exists C_{g},h_{g}>0 such that |\Psi(g|_{\bm{x}})-g(t_{0})|\leq C_{g}h^{d} for all h\in(0,h_{g}) . We will omit (\bm{x},t_{0}) if it is clear by the context. These concepts are related with the next result. Lemma 3 . If \Psi reproduces \Pi_{d-1} , then it has approximation order d . On the other hand, for the noisy problem , that consists in minimizing the noisy contribution \Psi(\bm{e}) , we can carry out an easy statistical treatment. Lemma 4 . The expectancy and variance of \Psi(\bm{E}) are \mathbb{E}\left(\Psi(\bm{E})\right)=0,\qquad\mathbb{V}\left(\Psi(\bm{E})\right)=\|\Omega\bm{a}\|_{2}^{2}, (1) where \Omega is some upper triangular matrix. Proof. The probability distribution of \Psi(\bm{e}) is \Psi(\bm{E})=\sum_{i=1}^{N}a_{i}E_{i}=\bm{a}^{T}\bm{E} , denoting vectors as column matrices. The expectancy and variance are \mathbb{E}\left(\Psi(\bm{E})\right)=\bm{a}^{T}\mathbb{E}\left(\bm{E}\right)=0,\qquad\mathbb{V}\left(\Psi(\bm{E})\right)=\bm{a}^{T}\hat{\Omega}\bm{a}, where \hat{\Omega} is the covariance N\times N matrix of the random distributions \bm{E} , \hat{\Omega}_{i_{1},i_{2}}=\text{Cov}(E_{i_{1}},E_{i_{2}}),\qquad i_{1},i_{2}=1,\ldots,N. Since \hat{\Omega} is a symmetric and positive semidefinite matrix, it admits a Cholesky-like decomposition, say \hat{\Omega}=\Omega^{T}\Omega , being \Omega an upper triangular matrix which is regular, provided that the covariance matrix \hat{\Omega} is positive definite. Now we can write \mathbb{V}\left(\Psi(\bm{E})\right)=\bm{a}^{T}\hat{\Omega}\bm{a}=(\Omega\bm{a})^{T}(\Omega\bm{a})=\|\Omega\bm{a}\|_{2}^{2}. ∎ Our aim is to make the noise as small as possible, we propose to reduce the variance of \Psi(\bm{e}) , or equivalently, to minimize \|\Omega\bm{a}\|_{2}^{2} . Remark 5 . From now, we assume that \Omega is regular. That is, the covariance matrix of the noise is positive-definite. Further simplifications can be made, which we do not consider. For instance, if all the variables \bm{E} are uncorrelated , then \Omega is just a diagonal matrix. In addition, if all the variables \bm{E} have equal variance, then \Omega is a constant diagonal matrix and it could be assumed without loss of generality that it is the identity matrix. These assumptions are very common in practice, as in the numerical experiments of [ 1 , 3 , 6 ] . Now it is revealed that we may solve the next optimization problem to address both the smooth and noisy problems: \begin{cases}\min\|\Omega\bm{a}\|_{2}^{2}\\ \text{s.t. $\bm{a}\in\mathds{R}^{N}$ such that $\Psi(\bm{f})=\bm{a}^{T}\bm{f}$ reproduces $\Pi_{d-1}$ with the setting $(\bm{x},t_{0})$.}\end{cases} (2) Definition 6 . We say that a linear rule \Psi is optimal for a set of random variables \bm{E} and for the choice of t_{0},\bm{x},d if its \bm{a} is a solution of the optimization problem ( 2 ). In the following, we compute the optimal rules for any arbitrary choice of t_{0},d,\bm{x} and \bm{E} , but supposing that the covariance matrix is positive definite, because it guarantees the unicity of the solution of ( 2 ). Lemma 7 . \Psi reproduces \Pi_{d-1} if, and only if, \bm{a} is a solution of the d\times N linear system \sum_{i=1}^{N}a_{i}x_{i}^{s}=t_{0}^{s},\qquad s=0,1,\ldots,d-1. (3) The system can be solved if N\geq d , and the solution is unique if N=d . As a consequence, the set of rules able to reproduce \Pi_{d-1} is an affine space of dimension N-d . Proof. Equation ( 3 ) is obtained from \Psi(P|_{\bm{x}})=P(t_{0}) for P\in\{1,x,\ldots,x^{d-1}\} , which is a basis of \Pi_{d-1} . Since the matrix of the system is a Vandermonde matrix, the system is compatible with N-d degrees of freedom. Clearly, the solutions of a linear system form an affine space. ∎ Now we see that this affine space can be easily parameterized. Let us denote \Pi_{d}|_{\bm{x}}=\{P|_{\bm{x}}\ :\ P\in\Pi_{d}\} which is a linear subspace of \mathds{R}^{N} of dimension d+1 . Then, we can consider a full-rank linear operator \nabla_{d}:\mathds{R}^{N}\longrightarrow\mathds{R}^{N-d} projecting any vector in \mathds{R}^{N} to the orthogonal complement of \Pi_{d-1}|_{\bm{x}} , which is isomorph to \mathds{R}^{N-d} . By definition, \nabla_{d} is such that \Pi_{d-1}|_{\bm{x}}=\ker(\nabla_{d}). (4) According to [ 5 , 7 ] , \nabla_{d} is an annihilation operator of \Pi_{d-1} . We denote it by \nabla_{d} because, for equal-spaced grids \bm{x} , the finite difference operator of order d can be taken. In that

Read the complete text