Estimating correlation under interval uncertainty

In many engineering situations, we are interested in finding the correlation ρρ between different quantities x and y based on the values xi and yi of these quantities measured in different situations i  . Measurements are never absolutely accurate; it is therefore necessary to take this inaccuracy into account when estimating the correlation ρρ. Sometimes, we know the probabilities of different values of measurement errors, but in many cases, we only know the upper bounds ΔxiΔxi and ΔyiΔyi on the corresponding measurement errors. In such situations, after we get the measurement results x˜i and y˜i, the only information that we have about the actual (unknown) values xi and yi is that they belong to the corresponding intervals [x˜i−Δxi,x˜i+Δxi] and [y˜i−Δyi,y˜i+Δyi]. Different values from these intervals lead, in general, to different values of the correlation ρρ. It is therefore desirable to find the range [ρ̲,ρ¯] of possible values of the correlation when xi and yi take values from the corresponding intervals. In general, the problem of computing this range is NP-hard. In this paper, we provide a feasible (=polynomial-time) algorithm for computing at least one of the endpoints of this interval: for computing ρ¯ when ρ¯>0 and for computing ρ̲ when ρ̲<0.

► In practice, it is often important to estimate correlation between quantities.
► Correlation ρρ is estimated based on the measurement results.
► Often, we only know the upper bound on the measurement errors.
► We then need to find the range [ρ̲;ρ¯] of possible value of ρρ; this is NP-hard.
► We show that a feasible algorithm is possible that computes ρ̲ or ρ¯.