Data fitting problem under interval uncertainty in data

We consider the data fitting problem under uncertainty, which is not described by probabilistic laws, but is limited in magnitude and has an interval character, i.e., is expressed by the intervals of possible data values. The most general case is considered when the intervals represent the measurement results both in independent (predictor) variables and in the dependent (criterial) variables. The concepts of weak and strong compatibility of data and parameters of functional dependence are introduced. It is shown that the resulting formulations of problems are reduced to the study and estimation of various solution sets for an interval system of equations constructed from the processed data. We discuss in detail the strong compatibility of the parameters and data, as more practical, more adequate to the reality and possessing better theoretical properties. The estimates of the function parameters, obtained in view of the strong compatibility, have a polynomial computational complexity, are robust, almost always have finite variability, and are also only partially affected by the so-called Demidenko paradox. We also propose a computational technology for solving the problem of constructing a linear functional dependence under interval data uncertainty and take into account the requirement of strong compatibility. It is based on the application of the so-called recognizing functional of the problem solution set — a special mapping, which recognizes, by the sign of the values, whether a point belongs to the solution set and simultaneously provides a quantitative measure of this membership. The properties of the recognizing functional are discussed. The maximum point of this functional is taken as an estimate of the parameters of the functional dependency under construction, which ensures the best compatibility between the parameters and data (or their least discrepancy). Accordingly, the practical implementation of this approach, named «maximum compatibility method», is reduced to the computation of the unconditional maximum of the recognizing functional — a concave non-smooth function. A specific example of solving the data fitting problem for a linear function from measurement data with interval uncertainty is presented.

1. Jaulin L., Kieffer M., Didrit O., Walter E. Applied Interval Analysis. — London, Springer, 2001. — 379 p. DOI: 10.1007/ 978-1-4471-0249-6.

2. Interval analysis and its applications. — A thematic web site, URL: http://www.nsc.ru/interval [in Russian].

3. Moore R. E., Kearfott R. B., Cloud M. J. Introduction to Interval Analysis. — Philadelphia: SIAM, 2009. — 223 p.

4. Shary S. P. Finite-dimensional Interval Analysis. — Novosibirsk: Institute of Computational Technologies SB RAS, 2019. — 631 p. An electronic book, accessible at http://www.nsc. ru/interval/InteBooks [in Russian].

5. Kearfott R. B., Nakao M., Neumaier A., Rump S., Shary S. P., van Hentenryck P. Standardized notation in interval analysis / Vychislit. Tekhnol. 2010. Vol. 15. B 1. P. 7 – 13.

6. Kantorovich L. V. On some new approaches to computational methods and observations processing / Sib. Matem. Zh. 1962. Vol. 3. N 5. P. 701 – 709 [in Russian].

7. Voshchinin A. P., Bochkov A. F., Sotirov G. R. A method of data analysis under interval non-statistical error / Zavod. Lab. 1990. Vol. 56. N 7. P. 76 – 81 [in Russian].

8. Voshchinin A. P. Interval data analysis: development and perspectives / Zavod. Lab. Diagn. Mater. 2002. Vol. 68. N 1. P. 118 – 126 [in Russian].

9. Skibitskiy N. V. Construction of direct and inverse static characteristics of the objects by interval data / Zavod. Lab. Diagn. Mater. 2017. Vol. 83. N 1. Part I. P. 87 – 93 [in Russian].

10. Sukhanov V. A. Study of Empirical Dependencies: Nonstatistical Approach. — Barnaul: Izd. Altai. Gos. Univ., 2007. — 290 p. [in Russian].

11. Oskorbin N. M., Maksimov A. V., Zhilin S. I. Construction and analysis of empirical dependencies by the method of uncertainty center / Izv. Altai. Gos. Univ. 1998. N 1. P. 37 – 40 [in Russian].

12. Zhilin S. I. On fitting empirical data under interval error / Reliable Computing. 2005. Vol. 11. P. 433 – 442. DOI: 10.1007/ s11155-005-0050-3.

13. Spivak S. I., Kantor O. G., Yunusova D. S. Identification and inf ormativity of models for quantitative analysis of multicomponent mixtures / Zh. Srednevolzh. Matem. Obsh. 2016. Vol. 18. N 3. P. 153 – 163 [in Russian].

14. Polyak B. T., Nazin S. A. Estimation of parameters in linear multidimensional systems under interval uncertainty / Journal of Automation and Information Sciences. 2006. Vol. 38. N 2. P. 1 – 5.

15. Kumkov S. I. Processing experimental data of ionic conduction of molten electrolyte by methods of interval analysis / Rasplavy. 2010. N 3. P. 79 – 89 [in Russian].

16. Pomerantsev A. L., Rodionova O. Ye. Construction of a multivariate calibration by the simple interval calculation method / Journal of Analytical Chemistry. 2006. Vol. 61. N 10. P. 952 – 966. DOI: 10.1134/S1061934806100030.

17. Podruzhko A. A., Podruzhko A. S. Interval Representation of Polynomial Regressions. — Moscow: Editorial URSS, 2003. – 47 p. [in Russian].

18. Shary S. P. Solvability of interval linear equations and data analysis under uncertainty / Automation and Remote Control. 2012. Vol. 73. P. 310 – 322. DOI: 10.1134/S0005117912020099.

19. Shary S. P., Sharaya I. A. Recognition of solvability of interval equations and its applications to data analysis / Vychisl. Tekhnol. 2013. Vol. 18. N 3. P. 80 – 109 [in Russian].

20. Shary S. P. Strong compatability in data fitting problems based on interval data / Vestn. Yuzhno-Ural. Gos. Univ. Ser. Matem. Mekh. Fiz. 2017. Vol. 9. N 1. P. 39 – 48 [in Russian].

21. Shary S. P. Strong compatibility in data fitting problem under interval uncertainty / Vychisl. Tekhnol. 2017. Vol. 22. N 2. P. 150 – 172 [in Russian].

22. Shary S. P. Maximum compatibility method for data fitting under interval uncertainty / Journal of Computer and Systems Sciences International. 2017. Vol. 56. Issue 6. P. 897 – 913. DOI: 10.1134/S1064230717050100.

23. Schweppe F. C. Recursive state estimation: unknown but bounded errors and system inputs / IEEE Trans. on Automatic Control. 1968. AC-13. P. 22 – 28.

24. Combettes P. L. Foundations of set-theoretic estimation / Proc. IEEE. 1993. Vol. 81. N 2. P. 182 – 208.

25. Milanese M., Norton J., Piet-Lahanier H., Walter E., eds. Bounding Approaches to System Identification. — New York: Plenum Press, 1996. — 567 p. DOI: 10.1007/978-1-4757-9545-5.

26. Lemeshko B. Yu., Postovalov S. P. On solving problems of statistical analysis of interval observations / Vychisl. Tekhnol. 1997. Vol. 2. N 1. P. 28 – 36 [in Russian].

27. Orlov A. I., Lutsenko E. V. System Fuzzy Interval Mathematics. — Krasnodar: Izd. Kuban Gos. Agrar. Univ., 2014. — 600 p. [in Russian].

28. Orlov A. I. Statistics of interval data (generalizing paper) / Zavod. Lab. Diagn. Mater. 2015. Vol. 81. N 3. P. 61 – 69 [in Russian].

29. Shary S. P. An interval linear tolerance problem / Automation and Remote Control. 2004. Vol. 65. P. 1653 – 1666. DOI: 10.1023/B: AURC. 0000044274. 25098. da.

30. Rohn J. Inner solutions of linear interval systems / Interval Mathematics 1985 / K. Nickel, ed. Lecture Notes in Computer Science 212. — Berlin: Springer, 1986. P. 157 – 158.

31. Schrijver A. Theory of Linear and Integer Programming. — Chichester-New York: Wiley, 1998. — 471 p.

32. Sharaya I. A. Is the tolerable solution set bounded? / Vychisl. Tekhnol. 2004. Vol. 9. N 3. P. 108 – 112 [in Russian].

33. Sharaya I. A. On unbounded tolerable solution sets / Reliable Computing. 2005. Vol. 11. N 5. P. 425 – 432. DOI: 10.1007/ s11155-005-0049-9.

34. Remez E. Ya. Principles of Numerical Methods of Chebyshev Approximation. — Kiev: Naukova Dumka, 1969. — 624 p. [in Russian].

35. Shary S. P. Interval regularization for imprecise linear algebraic equations. Deposited in arXiv.org Sept. 27, 2018, arXiv N 1810.01481. — 21 p. [in Russian].

36. Demidenko E. Z. Comment II on the article by A. P. Voshchinin, A. F. Bochkov, G. R. Sotirov «A method of data analysis under interval non-statistical error» / Zavod. Lab. 1990. Vol. 56. N 7. P. 83 – 84 [in Russian].

37. Shor N. Z., Zhurbenko N. G. A minimization method using the operation of extension of the space in the direction of the difference of two successive gradients / Cybernetics. 1971. Vol. 7. N 3. P. 450 – 459. DOI: 10.1007/BF01070454.

38. Stetsyuk P. I. Subgradient methods ralgb5 and ralgb4 for minimization of ravine-like convex functions / Vychisl. Tekhnol. 2017. Vol. 22. N 2. P. 127 – 149 [in Russian].

39. Nurminski E. A. Separating plane algorithms for convex optimization / Mathematical Programming. 1997. Vol. 76. P. 373 – 391. DOI: 10.1007/BF02614389.

40. Vorontsova E. A. Linear tolerance problem for input-output models with interval data / Vychisl. Tekhnol. 2017. Vol. 22. N 2. P. 67 – 84 [in Russian].