On the convergence of the integral identification method
Abstract Generated abstract
The paper analyzes convergence and statistical properties of an iterative integral identification method for estimating the coefficients of a linear form from observations affected by additive zero mean noise. The authors reformulate the recurrence in matrix form, derive conditions under which the iteration converges in expectation to the true coefficient vector, and express the limiting estimator through a convergent matrix series. They further obtain covariance formulas for the estimated coefficients, including the intercept term, and show that the variance order is comparable to that of linear orthogonal experimental design. Finally, under assumptions on the distribution of observations, they derive probabilistic estimates for the matrix norm condition and propose a transcendental equation for determining the number of observations needed to achieve a specified convergence probability.
Full Text
On the Convergence of the Integral Identification Method
V. V. Zakharov, V. I. Naplekov, V. T. Presler
(Presented by the scientific seminar of the Laboratory of Computer Technology and Automation of the Research Institute of Nuclear Physics and Automation at TPI)
In [1], on the basis of integral smoothing, the following iterative scheme was obtained for identifying the linear form \(F(\vec{x}) = b_0+\sum_{i=1}^{n} b_i x_i\).
\[ b_k^m=b_k^0+b_k^{m-1} -\frac{1}{\tau_k}\left( \frac{1}{N_{2k}}\sum_{s_k}Y_{s_k}^{m-1} -\frac{1}{N_{1k}}\sum_{r_k}Y_{r_k}^{m-1} \right), \tag{1} \]
\[ Y_j^{m-1}=\sum_{i=1}^{n} b_i^{m-1}x_i^j+b_0^{m-1}, \qquad m=1,2,\ldots \]
\[ b_0^m=\frac{1}{N}\sum_{j=1}^{N}\left(F_j-\sum_{i=1}^{n} b_i^m x_i^j\right), \tag{2} \]
\[ b_k^0=\frac{1}{\tau_k}\left( \frac{1}{N_{2k}}\sum_{s_k}F_{s_k} -\frac{1}{N_{1k}}\sum_{r_k}F_{r_k} \right), \tag{3} \]
\[ r_k\in j_{1k},\quad \text{if } x_k^r\in(\alpha_k,\alpha_k+\delta_k), \]
\[ s_k\in j_{2k},\quad \text{if } x_k^s\in(\beta_k-\delta_k,\beta_k). \tag{4} \]
The set \(j_{1k}\) contains \(N_{1k}\) elements, the set \(j_{2k}\)—\(N_{2k}\) elements, and
\[ j_{1k}\cup j_{2k}=j,\qquad N_{1k}+N_{2k}=N. \]
In formulas (1)—(3) the following notation is used:
\[ \tau_k=t\cdot\delta_k,\quad t\geq 1, \]
\[ \delta=\frac{\beta_k-\alpha_k}{t+1}. \]
The scheme (1)—(3) can be written in matrix form
\[ \vec{B}^{\,m}=\vec{B}^{\,0}+\vec{\varepsilon}\,\vec{B}^{\,m-1}, \tag{5} \]
where \(\vec B^{\,0}=(b_1^0,\ldots,b_n^0)^T\) (\(T\) is the transpose symbol), and the elements of the matrix \(\varepsilon\) are defined as follows:
\[ \varepsilon_{kk}=1-\frac{1}{\tau_k}\left(\frac{1}{N_{2k}}\sum_{s_k} x_k^{s_k} -\frac{1}{N_{1k}}\sum_{r_k} x_k^{r_k}\right), \]
\[ \varepsilon_{ik}=-\frac{1}{\tau_k}\left(\frac{1}{N_{2k}}\sum_{s_k} x_i^{s_k} -\frac{1}{N_{1k}}\sum_{r_k} x_i^{r_k}\right),\quad i=\overline{1,n};\ i\ne k. \tag{6} \]
The quantities \(x_i^{s_k}\) and \(x_i^{r_k}\) are defined by relations (4) and together form the observation matrix \(\vec X=\|x_i^j\|\), \(i=\overline{1,n};\ j=1,N\).
Of practical interest are:
1) proof of convergence of the process;
2) obtaining probabilistic characteristics of the vector of coefficients \(B\);
3) estimating the number of computations \(N\) sufficient for convergence of the process under conditions of interference.
1. Convergence of the iteration process
Suppose that an interference \(\eta\)—a random variable with zero mathematical expectation and variance \(\sigma_\eta^2\)—is additively superimposed on the function \(F(\vec x)\). The function \(F(\vec x)\), taking into account the effect of the interference \(\eta\) at the point \(\vec x^{\,j}\), is equal to
\[ F(\vec x^{\,j})=b_0+\sum_{i=1}^{n} b_i x_i^j+\eta_j, \tag{7} \]
where \(\eta_j\) is a realization of the interference \(\eta\) at the moment of computing \(F(\vec x^{\,j})\).
Consider expression (3) for the coefficient \(b_k'\). Taking (7) into account, we shall have
\[ b_k^0=\frac{1}{\tau_k}\sum_{i=1}^{n} b_i \left(\frac{1}{N_{2k}}\sum_{s_k} x_i^{s_k} -\frac{1}{N_{1k}}\sum_{r_k} x_i^{r_k}\right)+\overline{\eta}_k, \tag{8} \]
\[ \overline{\eta}_k=\frac{1}{\tau_k}\left(\frac{1}{N_{2k}}\sum_{s_k}\eta_{s_k} -\frac{1}{N_{1k}}\sum_{r_k}\eta_{r_k}\right). \]
Or, in matrix form,
\[ \vec B^{\,0}=\vec B-\varepsilon \vec B+\vec{\overline{\eta}}, \tag{9} \]
where \(\vec{\overline{\eta}}=(\overline{\eta}_1,\ldots,\overline{\eta}_n)^T\) and \(M[\vec{\overline{\eta}}]=0\) (\(M\) is the symbol for mathematical expectation).
From [5] it follows that
\[ \vec B^{\,m}=\sum_{q=0}^{m}\varepsilon^q \vec B^{\,0}. \tag{10} \]
Substituting (9) into (10), we obtain the iteration scheme under conditions of interference:
\[ \vec B^{m}=\vec B-\vec\varepsilon^{\,m+1}\vec B+\sum_{q=1}^{m}\vec\varepsilon^{\,q}\vec\eta+\vec\eta . \tag{11} \]
It is known [2] that a series of type (11) converges when \(\vec\varepsilon^{\,\infty}=0\), and in this case
\[ \lim_{m\to\infty} M[\vec B^{m}] = \vec B+\sum_{q=1}^{\infty}\vec\varepsilon^{\,q}M[\vec\eta]+M[\vec\eta] = \vec B, \]
(or \(M[\vec\eta]=0\) by assumption).
Thus, the convergence of the iterations (1)—(3) to the true coefficients of the linear form \(F(\vec x)\) under conditions of interference has been proved.
As a consequence of (10), and using the formula for a convergent matrix series [2], we obtain an expression for the coefficients \(b_i\) in terms of \(b_i^0\).
\[ \vec B=\lim_{m\to\infty}\vec B^{m} = \sum_{q=0}^{\infty}\vec\varepsilon^{\,q}\vec B^{0} = (\vec E-\vec\varepsilon)^{-1}\vec B^{0}. \tag{12} \]
Substituting into (12) the expression (9) for \(\vec B^0\), we find that
\[ \lim_{m\to\infty}\vec B^{m} = \vec B+(\vec E-\vec\varepsilon)^{-1}\vec\eta . \tag{13} \]
It follows from this that if the number of observations \(N\) is sufficiently large, and the distribution of the random variable \(\vec\eta\) is symmetric, then the inverse matrix in (13) is close to the identity matrix, the variance of the components \(b_k^m\) of the coefficient vector \(\vec B^m\) is close to \(\sigma_{\eta_k}^{2}\) and has order (under the assumption
\[ N_{1k}-N_{2k}=\frac{1}{2}N. \]
\[ \sigma^{2}(b_k)\approx \sigma_{\eta_k}^{2}=\frac{4\sigma_{\eta}^{2}}{\tau_k^{2}N}. \tag{14} \]
It is not difficult to see that the order of estimate (14) is the same as in linear orthogonal design [3]. Thus, the promise of the integral identification methodology in problems of experiment planning and optimization under conditions of passive experiment is evident.
2. Statistical analysis of the relations of the integral identification method
It is of interest to obtain more accurate expressions for the variances \(\sigma^{2}(b_k)\) and covariances \(\operatorname{cov}(b_i,b_j)\), which are nonzero as a consequence of the statistical dependence between the coefficients \(b_k\).
Let us introduce, analogously to how this is done in [4], the covariance matrix.
\[ M\{[\vec{B}^{\,m}-M(\vec{B}^{\,m})][\vec{B}^{\,m}-M(\vec{B}^{\,m})]^{\mathrm T}\} =\vec{C}^{\,m}\sigma_\eta^{2}, \]
where
\[ \vec{C}^{\,m}=\sum_{j=0}^{m}\vec{\varepsilon}^{\,j}\vec{G}\sum_{j=0}^{m}(\vec{\varepsilon}^{\,\mathrm T})^{j}, \]
\(\vec{G}\) is a diagonal matrix with diagonal element
\[ g_{ij}=\frac{1}{r_i^2}\left(\frac{1}{N_{1i}}+\frac{1}{N_{2k}}\right). \]
As \(m\to\infty\), the covariance matrix of the coefficients \(\vec{C}^{\,m}\to\vec{C}\).
\[ \vec{C}=(\vec{E}-\vec{\varepsilon})^{-1}\vec{G}\bigl[(\vec{E}-\vec{\varepsilon})^{-1}\bigr]^{\mathrm T}. \]
If the free term \(b_0^m\) is also taken into account, then the covariance matrix \(C^m\) is supplemented by one more row and column.
\[ M\{[b_0^m-M(b_0^m)][\vec{B}^{\,m}-M(\vec{B}^{\,m})]\} =-\sigma_\eta^{2}\vec{C}^{\,m}\vec{a}^{\,\mathrm T}, \]
where
\[ \vec{a}=\left(\frac{1}{N}\sum_{j=1}^{N}x_1^j,\ldots,\frac{1}{N}\sum_{j=1}^{N}x_n^j\right)^{\mathrm T}; \]
\[ M\{b_0^m-M(b_0^m)\}^{2} =\sigma_\eta^{2}\left[\frac{1}{N}+\vec{a}\vec{C}^{\,m}\vec{a}^{\,\mathrm T}\right]. \]
3. On estimating the number of observations
The convergence of the iteration process in Sec. 2 was obtained under the assumption \(\vec{\varepsilon}^{\,\infty}=0\). This, in turn, is satisfied if any of the norms of the matrix \(\vec{\varepsilon}\) is less than 1. As the norm of the matrix \(\vec{\varepsilon}\), let us choose the set of eigenvalues of the matrix \(\vec{\varepsilon}\). For the eigenvalues \(\lambda_i\) of an arbitrary real nonsingular matrix \(\vec{\varepsilon}\) of order \(n\times n\), the estimate [5] holds:
\[ \max_{i=\overline{1,N}}\lambda_i^2\le w,\qquad w=S-(S^n-nd^2)(n-1)^{n-1}, \]
where
\[ S=\sum_{i,j=1}^{n}\varepsilon_{ij}^{2}, \]
\(d\) is the determinant of the matrix \(\vec{\varepsilon}\).
Let us find the distribution function of the random variable \(w\). We shall assume that \(x_i^j\) are independent and have one and the same symmetric distribution function. It can then be shown that \(\varepsilon_{ij}\) are uncorrelated, and for large \(n\) almost all of them are independent: namely, those are independent that
\(\varepsilon_{i_1 j_1}\) and \(\varepsilon_{i_2 j_2}\), for which \((i_1 \ne i_2) \wedge (j_1 \ne j_2) \wedge (i_1 \ne j_2) \wedge (i_2 \ne j_1)\)—there are such \(\varepsilon_{ij}\) in number \(n(n^2-1)/2 + 2n^3 + n^2 + n\) out of the total number of pairs \(n^2(n^2-1)/2\).
The number of independent pairs \(\varepsilon_{ij}\) is related to the number of dependent ones approximately as \(n/4\).
It follows from (6) that \(\varepsilon_{ik}\) has a distribution close to normal, with zero mathematical expectation and variance
\[
\sigma_\varepsilon^2 \approx \frac{4}{\tau^2 N}\,\sigma^2
\]
(\(\sigma^2\) is the variance of the random variable \(x_i^j\)). The quantity
\[
s_1=\frac{1}{\sigma_\varepsilon^2}\sum_{i,j=1}^{n}\varepsilon_{ij}^2
\]
by virtue of the independence of the \(\varepsilon_{ij}\) has a \(\chi^2\)-distribution and, consequently, the quantity \(s=\sigma_\varepsilon^2 s_1\) has the distribution density:
\[
f(s)=\frac{1}{2^{\frac{n^2}{2}}\Gamma\!\left(\frac{n^2}{2}\right)}
\cdot
\left(\frac{s}{\sigma^2}\right)^{\frac{n^2}{2}-1}
\exp\!\left(-\frac{s}{2\sigma_\varepsilon^2}\right).
\tag{15}
\]
The determinant \(d\) is the sum of \(n!\) independent normally distributed terms with variance
\[
\sigma_1^2=\left(\frac{4}{\tau^2}\sigma^2\right)^n
\]
and, consequently, \(d\) is normally distributed with variance
\[
n!\left(\frac{2\sigma}{\tau}\right)^{2n}
\]
and zero mathematical expectation, while the quantity \(z=nd^2(n-1)^{\,n-1}\) has the distribution density:
\[
f_z(z)=
\frac{1}{
\left(\frac{2}{\tau}\sigma\right)^n
\sqrt{2\pi n (n-1)^{n-1} n! z}
}
\cdot
e^{
-\frac{\tau z}{
2\,n!\left(\frac{2}{\tau}\sigma\right)^{2n}
}
}.
\tag{16}
\]
The distribution function of the quantity
\[
w=s-(s^n-z)^{\frac{1}{n}}
\]
is determined by formula (6):
\[
F_w(w)=\iint f(s,z)\,ds\,dz.
\tag{17}
\]
\[
s-(s^n-z)^{\frac{1}{n}}=w.
\]
Considering \(s\) and \(z\) independent and substituting (15) and (16) into (17), after simple transformations we shall have:
\[
F_w(w)=
\frac{1}{
2^{\frac{n^2}{2}}\cdot
\Gamma\!\left(\frac{n^2}{2}\right)
}
\int_{0}^{\infty}
\frac{s^{\frac{n^2}{2}-1}}{e^{\frac{s}{2\sigma^2}}}
\,
\Phi\!\left(
-
\frac{s^n-(s-w)^n}{
2n(n-1)^{n-1}n!\left(\frac{2\sigma}{\tau}\right)^{\frac{2}{n}}}
\right)\,ds.
\tag{18}
\]
Specifying \(n\), the distribution of \(x\), and the probability \(P\) with which procedure (1) is to converge, we obtain from (18) a transcendental equation for estimating the number of observations \(N\).
References
-
V. V. Zakharov. Identification of a static object by means of integral projections. In the present collection.
-
D. K. Faddeev, V. N. Faddeeva. Computational Methods of Linear Algebra. Moscow, Fizmatgiz, 1960.
-
V. V. Nalimov, N. A. Chernova. Statistical Methods of Experimental Design. Moscow, “Nauka,” 1965.
-
Yu. V. Linnik. The Method of Least Squares and the Foundations of the Mathematical-Statistical Theory of the Processing of Observations. Moscow, Fizmatgiz, 1962.
-
I. S. Berezin, N. P. Zhidkov. Methods of Computation. Vol. II, Fizmatgiz, 1960.
-
B. V. Gnedenko. A Course in Probability Theory. Fizmatgiz, 1961.
-
I. S. Gradshteyn, I. M. Ryzhik. Tables of Integrals, Sums, Series, and Products. Fizmatgiz, 1971.