×

Weak and strong compatibility in data fitting problems under interval uncertainty. (English) Zbl 1462.62767

Summary: For the data fitting problem under interval uncertainty, we introduce the concept of strong compatibility between data and parameters. It is shown that the new strengthened formulation of the problem reduces to computing and estimating the so-called tolerable solution set for interval systems of equations constructed from the data being processed. We propose a computational technology for constructing a “best-fit” linear function from interval data, taking into account the strong compatibility requirement. The properties of the new data fitting approach are much better than those of its predecessors: strong compatibility estimates have polynomial computational complexity, the variance of the strong compatibility estimates is almost always finite, and these estimates are rubust. An example considered in the concluding part of the paper illustrates some of these features.

MSC:

62R07 Statistical aspects of big data and data science
62F25 Parametric tolerance and confidence regions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barker-Plummer, D., Barwise, J. and Etchemendy, J. (2011). Language, Proof and Logic, 2nd edn. CSLI Publications, Stanford, CA. · Zbl 1318.03001
[2] Combettes, P. (1993). The foundations of set theoretic estimation. Proc. IEEE, 81(2): 182-208.
[3] Cramér, H. (1946). Mathematical Methods of Statistics.Editions of 1946-1999. Princeton University Press, Princeton.
[4] Demidenko, E. Z. (1990). Comment II to the Paper of A. P. Voshchinin, A. F. Bochkov, and G. R. Sotirov “A method of data analysis under interval nonstatistical error”. Ind. Lab., 56(7): 83-84 (in Russian). Available at: http://www.nsc.ru/interval/Library/Thematic/DataProcs/VosBochSoti.pdf.
[5] Gutowski, M. W. (2006). Interval experimental data fitting. Focus on Numerical Analysis, ed. Liu, J. P.. Nova Science Publishers Inc., New York, pp. 27-70.
[6] Iske, A. (2018). Approximation Theory and Algorithms for Data Analysis.Springer, Cham, Switzerland. · Zbl 1411.41001
[7] Jaulin, L., Kieffer, M., Didrit, O. and Walter, E. (2001). Applied Interval Analysis — With Examples in Parameter and State Estimation, Robust Control and Robotics.Springer, London. · Zbl 1023.65037
[8] Kantorovich, L. V. (1962). On some new approaches to numerical methods and processing observation data. Sib. Math. J., 3(5): 701-709(in Russian). Available at: http://www.nsc.ru/interval/Introduction/Kantorovich62.pdf.
[9] Kearfott, R. B., Nakao, M., Neumaier, A., Rump, S., Shary, S. P. and van Hentenryck, P. (2010). Standardized notation in interval analysis. Comput. Technol., 15(1): 7-13. · Zbl 1196.65088
[10] Kreinovich, V., Lakeyev, A., Rohn, J. and Kahl, P. (1998). Computational Complexity and Feasibility of Data Processing and Interval Computations.Kluwer Academic, Dordrecht and Springer Science + Business Media, Dordrecht. · Zbl 0945.68077
[11] Kreinovich, V. and Shary, S. P. (2016). Interval methods for data fitting under uncertainty: A probabilistic treatment. Reliab. Comput., 23: 105-140. Available at: http://interval.louisiana.edu/reliable-computing-journal/volume-23/reliable-computing-23-pp-105-140.pdf.
[12] Mayer, G. (2017). Interval Analysis and Automatic Result Verification.De Gruyter, Berlin. · Zbl 1373.65036
[13] Milanese, M., Norton, J., Piet-Lahanier, H. and Walter, E. (eds.) (1996). Bounding Approaches to System Identification.Plenum Press, New York. https://doi.org/10.1007/978-1-4757-9545-5 · Zbl 0845.00024
[14] Moore, R. E., Kearfott, R. B. and Cloud, M. J. (2009). Introduction to Interval Analysis.SIAM, Philadelphia. · Zbl 1168.65002
[15] Neumaier, A. (1986). Tolerance analysis with interval arithmetic. Freiburger Intervall-Berichte, 86(9): 5-19.
[16] Neumaier, A. (1990). Interval Methods for Systems of Equations.Cambridge University Press, Cambridge. · Zbl 0715.65030
[17] Nurminski, E. A. (1997). Separating plane algorithms for convex optimization. Math. Program., 76: 373-391. https://doi.org/10.1007/BF02614389 · Zbl 0872.90073
[18] Polyak, B. T. and Nazin, S. A. (2006). Estimation of parameters in linear multidimensional systems under interval uncertainty. J. Autom. Inf. Sci., 38(2): 19-33.
[19] Remez, E. Ya. (1962). General Computational Methods of Chebyshev Approximation: The Problems with Linear Real Parameters, , Vol. 4491. U. S. Atomic Energy Commission, Division of Technical Information, Oak Ridge, TN.
[20] Rohn, J. (1986). Inner solutions of linear interval systems. Interval Mathematics 1985, ed. Nickel, K., , Vol. 212. Springer-Verlag, Berlin. https://doi.org/10.1007/3-540-16437-5_15 · Zbl 0588.65024
[21] Rohn, J. (2005). A Handbook of Results on Interval Linear Problems.Czech Academy of Sciences, Prague. Available at: http://www.nsc.ru/interval/Library/Surveys/ILinProblems.pdf.
[22] Schrijver, A. (1998). Theory of Linear and Integer Programming.John Wiley & Sons, Chichester. · Zbl 0970.90052
[23] Schweppe, F. S. (1968). Recursive state estimation: Unknown but bounded errors and system inputs. IEEE Trans. Autom. Control, 13(1): 22-28.
[24] Sharaya, I. A.(2005a). Structure of the tolerable solution set of an interval linear system. Comput. Technol.10(5): 103-119(in Russian). · Zbl 1080.65034
[25] Sharaya, I. A. (2005b). On unbounded tolerable solution sets. Reliab. Comput., 11(5): 425-432. https://doi.org/10.1007/s11155-005-0049-9 · Zbl 1082.15006
[26] Sharaya, I. A. (2014). IntLinInc3D, a software package for visualization of solution sets to interval linear 3D systems of relations. Available at: http://www.nsc.ru/interval/sharaya/.
[27] Sharaya, I. A. (2018). Quantifier-free descriptions for quantifier solutions to interval linear systems of relations. Preprint, arXiv:1802.09199 [math.OC]. Available at: https://arxiv.org/abs/1802.09199.
[28] Sharaya, I. A. and Shary, S. P. (2016). Reserve of characteristic inclusion as recognizing functional for interval linear systems. Proc. 16th Int. Symp. Scientific Computing, Computer Arithmetic, and Validated Numerics: Revised Selected Papers. eds. M. Nehmeier, J. Wolff von Gudenberg and W. Tucker, Lecture Notes in Computer Science, Vol. 9553. Springer, Cham, pp. 148-167. · Zbl 1354.65087
[29] Shary, S. P. (1995a). On optimal solution of interval linear equations. SIAM J. Numer. Anal., 32(2): 610-630. · Zbl 0838.65023
[30] Shary, S. P. (1995b). Solving the linear interval tolerance problem. Math. Comput. Simul., 39: 53-85. https://doi.org/10.1016/0378-4754(95)00135-K
[31] Shary, S. P. (2002). A new technique in systems analysis under interval uncertainty and ambiguity. Reliab. Comput., 8(5): 321-418. https://doi.org/10.1023/A:1020505620702 · Zbl 1020.65029
[32] Shary, S. P. (2004). An interval linear tolerance problem. Autom. Remote Control, 65(10): 1653-1666. https://doi.org/10.1023/B:AURC.0000044274.25098.da · Zbl 1081.65042
[33] Shary, S. P. (2012). Solvability of interval linear equations and data analysis under uncertainty. Autom. Remote Control, 73(2): 310-322. https://doi.org/10.1134/S0005117912020099 · Zbl 1307.90215
[34] Shary, S. P. (2016). Maximum consistency method for data fitting under interval uncertainty. J. Glob. Optim., 66(1): 111-126. https://doi.org/10.1007/s10898-015-0340-1 · Zbl 1402.62146
[35] Shary, S. P. (2017). Strong compatibility in data fitting problems with interval data. Bull. South Ural State Univ. Ser. “Math. Mech. Phys.”, 9(1): 39-48. (in Russian). https://doi.org/10.14529/mmph170105 · Zbl 1400.62147
[36] Shary, S. P. (2018). Interval regularization for imprecise linear algebraic equations. Preprint, arXiv:1810.01481 [math.NA]. Available at: https://arxiv.org/abs/1810.01481.
[37] Shary, S. P. (2019). Finite-Dimensional Interval Analysis.Institute of Computational Technologies SB RAS, Novosibirsk(in Russian). Available at: http://www.nsc.ru/interval/Library/InteBooks/SharyBook.pdf.
[38] Shary, S. P. and Sharaya, I. A. (2013). Recognizing solvability of interval equations and its application to data analysis. Comput. Technol., 18(3): 80-109(in Russian). · Zbl 1420.65063
[39] Shary, S. P. and Sharaya, I. A. (2016). On solvability recognition for interval linear systems of equations. Optim. Lett., 10(2): 247-260. · Zbl 1333.65047
[40] Shor, N. Z. and Zhurbenko, N. G. (1971). Minimization method using operation of space dilatation in the direction of difference of two sequential gradients. Kibernetika, 3: 51-59(in Russain).
[41] Stetsyuk, P. I. (2014). Ellipsoids Methods and \(r\)-Algorithms.Eureca, Chişinâu, Moldova(in Russian). · Zbl 0945.65062
[42] Stetsyuk, P. I. (2017). Subgradient methods ralgb5 and ralgb4 for minimization of ravine convex functions. Comput. Technol., 22(2): 127-149(in Russian). · Zbl 1381.90088
[43] Vorontsova, E. (2016). Extended separating plane algorithm and NSO-solutions of PageRank problem. Proc. 9th Int. Conf., Discrete Optimization and Operations Research, eds. Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E. and Pardalos, P., , Vol. 9869. Springer International, Cham, Switzerland, pp. 547-560. https://doi.org/10.1007/978-3-319-44914-2.43
[44] Vorontsova, E. A. (2017). Linear tolerance problem for input-output models with interval data. Comput. Technol., 22(2): 67-84(in Russian). · Zbl 1396.91555
[45] Zhilin, S. I. (2005). On fitting empirical data under interval error. Reliab. Comput., 11(5): 433-442. https://doi.org/10.1007/s11155-005-0050-3 · Zbl 1081.65503
[46] Zhilin, S. I. (2007). Simple method for outlier detection in fitting experimental data under interval error. Chemom. Intell. Lab. Syst., 88(1): 60-68.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.