Computer Engineering Commons^™

Interval Computations And Interval-Related Statistical Techniques: Estimating Uncertainty Of The Results Of Data Processing And Indirect Measurements, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we only know the upper bound Δ on the measurement error: |Δx| ≤ Δ. In other words, we only know that the measurement error is located on the interval [−Δ, Δ]. The traditional approach is to assume that Δx is uniformly distributed on [−Δ, Δ]. In some situations, however, this approach underestimates the error of indirect measurements. It is therefore desirable to directly process this interval uncertainty. Such "interval computations" methods have been developed since the 1950s. In this paper, we provide a brief overview of related algorithms and results.

Asymptotically Optimal Algorithm For Checking Whether A Given Vector Is A Solution To A Given Interval-Quantifier Linear System, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we have a linear dependence between different quantities. In such situations, we often need to solve the corresponding systems of linear equations. Often, we know the parameters of these equations with interval uncertainty. In this case, depending on the practical problem, we have different notions of a solution. For example, if we determine parameters from observations, we are interested in all the unknowns which satisfy the given system of linear equations for some possible values of the parameters. If we design a system so that it does not exceed given tolerance bounds, then we need to …

Towards Interval Techniques For Model Validation, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

Most physical models are approximate. It is therefore important to find out how accurate are the predictions of a given model. This can be done by validating the model, i.e., by comparing its predictions with the experimental data. In some practical situations, it is difficult to directly compare the predictions with the experimental data, since models usually contain (physically meaningful) parameters, and the exact values of these parameters are often not known. One way to overcome this difficulty is to get a statistical distribution of the corresponding parameters. Once we substitute these distributions into a model, we get statistical predictions …

How To Tell When A Product Of Two Partially Ordered Spaces Has A Certain Property?, Francisco Zapata, Olga Kosheleva, Karen Villaverde

Departmental Technical Reports (CS)

In this paper, we describe how checking whether a givenproperty F is true for a product A₁ X A₂ of partiallyordered spaces can be reduced to checking several relatedproperties of the original spaces A_i.

This result can be useful in the analysis of propertiesof intervals [a,b] = {x: a <= x <= b}over general partially ordered spaces -- such as the spaceof all vectors with component-wise order or the set of allfunctions with component-wise ordering f <= g <-->for all x (f(x) <= g(x)). When we consider sets of pairs ofsuch objects A₁ X A₂, it is natural to define the orderon this set in terms of orders in A₁ and A₂ -- this is, e.g.,how ordering and intervals are defined on the set R² of all2-D vectors.

This result …

Theoretical Explanation Of Bernstein Polynomials' Efficiency: They Are Optimal Combination Of Optimal Endpoint-Related Functions, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

In many applications of interval computations, it turned out to be beneficial to represent polynomials on a given interval [x_-, x₊] as linear combinations of Bernstein polynomials (x- x _- )^k * (x₊ - x)^n-k. In this paper, we provide a theoretical explanation for this empirical success: namely, we show that under reasonable optimality criteria, Bernstein polynomials can be uniquely determined from the requirement that they are optimal combinations of optimal polynomials corresponding to the interval's endpoints.

Towards Fast And Accurate Algorithms For Processing Fuzzy Data: Interval Computations Revisited, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

Is It Possible To Have A Feasible Enclosure-Computing Method Which Is Independent Of The Equivalent Form?, Marcin Michalak, Vladik Kreinovich

Departmental Technical Reports (CS)

The problem of computing the range [y] of a given function f(x1, ..., xn) over given intervals [xi] -- often called the main problem of interval computations -- is, in general, NP-hard. This means that unless P = NP, it is not possible to have a feasible (= polynomial time) algorithm that always computes the desired range. Instead, interval computations algorithms compute an enclosure [Y] for the desired range. For all known feasible enclosure-computing methods -- starting with straightforward interval computations -- there exist two expressions f(x1, ..., xn) and g(x1, ..., xn) for computing the same function that lead …

Towards Faster Estimation Of Statistics And Odes Under Interval, P-Box, And Fuzzy Uncertainty: From Interval Computations To Rough Set-Related Computations, Vladik Kreinovich

Departmental Technical Reports (CS)

Interval computations estimate the uncertainty of the result of data processing in situations in which we only know the upper bounds $\Delta$ on the measurement errors. In interval computations, at each intermediate stage of the computation, we have intervals of possible values of the corresponding quantities. As a result, we often have bounds with excess width. One way to remedy this problem is to extend interval technique to rough-set computations, where on each stage, in addition to intervals of possible values of the quantities, we also keep rough sets representing possible values of pairs (triples, etc.).

A Broad Prospective On Fuzzy Transforms: From Gauging Accuracy Of Quantity Estimates To Gauging Accuracy And Resolution Of Measuring Physical Fields, Vladik Kreinovich, Irina Perfilieva

Departmental Technical Reports (CS)

Fuzzy transform is a new type of function transforms that has been successfully used in different application. In this paper, we provide a broad prospective on fuzzy transform. Specifically, we show that fuzzy transform naturally appears when, in addition to measurement uncertainty, we also encounter another type of localization uncertainty: that the measured value may come not only from the desired location x, but also from the nearby locations.

How To Take Into Account Dependence Between The Inputs: From Interval Computations To Constraint-Related Set Computations, With Potential Applications To Nuclear Safety, Bio- And Geosciences, Martine Ceberio, Scott Ferson, Vladik Kreinovich, Sanjeev Chopra, Gang Xiang, Adrian Murguia, Jorge Santillan

Departmental Technical Reports (CS)

In many real-life situations, in addition to knowing the intervals Xi of possible values of each variable xi, we also know additional restrictions on the possible combinations of xi; in this case, the set X of possible values of x=(x1,..,xn) is a proper subset of the original box X1 x ... x Xn. In this paper, we show how to take into account this dependence between the inputs when computing the range of a function f(x1,...,xn).

From Intervals To Domains: Towards A General Description Of Validated Uncertainty, With Potential Applications To Geospatial And Meteorological Data, Vladik Kreinovich, Olga Kosheleva, Scott A. Starks, Kavitha Tupelly, Gracaliz P. Dimuro, Antonio C. Da Costa Rocha, Karen Villaverde

Departmental Technical Reports (CS)

When physical quantities xi are numbers, then the corresponding measurement accuracy can be usually represented in interval terms, and interval computations can be used to estimate the resulting uncertainty in y=f(x1,...,xn).

In some practical problems, we are interested in more complex structures such as functions, operators, etc. Examples: we may be interested in how the material strain depends on the applied stress, or in how a physical quantity such as temperature or velocity of sound depends on a 3-D point.

For many such structures, there are ways to represent uncertainty, but usually, for each new structure, we have to perform …

Probabilities, Intervals, What Next? Extension Of Interval Computations To Situations With Partial Information About Probabilities, Vladik Kreinovich, Gennady N. Solopchenko, Scott Ferson, Lev Ginzburg, Richard Alo

Departmental Technical Reports (CS)

In many real-life situations, we are interested in the value of a physical quantity y that is difficult or impossible to measure directly. To estimate y, we find some easier-to-measure quantities x1,...,xn which are related to y by a known relation y=f(x1,...,xn). Measurements are never 100% accurate; hence, the measured values Xi are different from xi, and the resulting estimate Y=f(X1,...,Xn) is different from the desired value y=f(x1,...,x_n). How different?

Traditional engineering to error estimation in data processing assumes that we know the probabilities of different measurement error Dxi=Xi-xi.

In many practical situations, we only know the upper bound Di …

Fast Quantum Algorithms For Handling Probabilistic And Interval Uncertainty, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

No abstract provided.

A New Differential Formalism For Interval-Valued Functions And Its Potential Use In Detecting 1-D Landscape Features, Vladik Kreinovich, Hung T. Nguyen, Gracaliz Pereira Dimuro, Antonio Carlos Da Rocha Costa, Benjamin Rene Callejas Bedregal

Departmental Technical Reports (CS)

In many practical problems, it is important to know the slope (derivative) dy/dx of one quantity y with respect to some other quantity x. For example, different 1-D landscape features can be characterized by different values of the derivative dy/dx, where y is an altitude, and x is a horizontal coordinate. In practice, we often know the values of y(x) for different x with interval uncertainty. How can we then find the set of possible values of the slope? In this paper, we formulate this problem of differentiating interval-values functions in precise terms, and we describe an (asymptotically) optimal algorithm …

Real-Time Algorithms For Statistical Analysis Of Interval Data, Berlin Wu, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

When we have only interval ranges [xi] of sample values x1,...,xn, what is the interval [V] of possible values for the variance V of these values? There are quadratic time algorithms for computing the exact lower bound V- on the variance of interval data, and for computing V+ under reasonable easily verifiable conditions. The problem is that in real life, we often make additional measurements. In traditional statistics, if we have a new measurement result, we can modify the value of variance in constant time. In contrast, previously known algorithms for processing interval data required that, once a new data …

A Full Function-Based Calculus Of Directed And Undirected Intervals: Markov's Interval Arithmetic Revisited, Juergen Wolff Von Gudenberg, Vladik Kreinovich

Departmental Technical Reports (CS)

This paper proposes a new interpretation of intervals as classes of functions having the same domain. Interval operations are seen as operations on these classes. This approach allows to recover Markov's directed interval arithmetic by taking into account the monotonicity of the functions.

Probabilities, Intervals, What Next? Optimization Problems Related To Extension Interval Computations To Situations With Partial Information About Probabilities, Vladik Kreinovich

Departmental Technical Reports (CS)

When we have only interval ranges [xi-,xi+] of sample values x1,...,xn, what is the interval [V-,V+] of possible values for the variance V of these values? We prove that the problem of computing the upper bound V+ is NP-hard. We provide a feasible (quadratic time) algorithm for computing the exact lower bound V- on the variance of interval data. We also provide feasible algorithms that computes V+ under reasonable easily verifiable conditions, in particular, in case interval uncertainty is introduced to maintain privacy in a statistical database.

We also extend the main formulas of interval arithmetic for different arithmetic operations …

Aerospace Applications Of Intervals: From Geospatial Data Processing To Fault Detection In Aerospace Structures, Vladik Kreinovich, Scott A. Starks

Departmental Technical Reports (CS)

This paper presents a brief introduction into interval computations and their use in aerospace applications.

Interval Computations As A Particular Case Of A General Scheme Involving Classes Of Probability Distributions, Scott Ferson, Lev Ginzburg, Vladik Kreinovich, Harry Schulte

Departmental Technical Reports (CS)

Traditionally, in science and engineering, measurement uncertainty is characterized by a probability distribution; however, we don't know this probability distribution exactly, so we must consider classes of probability distributions. Interval computations deal with a very specific type of such classes: classes of all distributions which are located on a given interval. We show that in general, we need all convex classes of probability distributions.

Aerospace Applications Of Soft Computing And Interval Computations (With An Emphasis On Simulation And Modeling), Scott A. Starks, Vladik Kreinovich

Departmental Technical Reports (CS)

This paper presents a brief overview of our research in applications of soft computing and interval computations to aerospace problems, with a special emphasis on simulation and modeling.

Aerospace Applications Of Soft Computing And Interval Computations (With An Emphasis On Multi-Spectral Satellite Imaging), Scott A. Starks, Vladik Kreinovich

Departmental Technical Reports (CS)

This paper presents a brief overview of our research in applications of soft computing and interval computations to aerospace problems, with a special emphasis on multi-spectralsatellite imaging.