5
$\begingroup$

Was reading the paper "DETECTING AND ASSESSING THE PROBLEMS CAUSED BY MULTICOLLINEARITY:A USE OF THE SINGULAR-VALUE DECOMPOSITION" by David Belsley and Virginia Klema.

After performing SVD, while counting the number of non-zero singular values, it is stated in the paper that

problems arise because computers use finite arithmetic ...

More specifically, eigenvalues that are supposed to be zero are stored as non-zero eigenvalues due to arithmetic precision used by computer and rounding error.

Could someone please elaborate on this arithmetic precision and rounding error?

$\endgroup$
5
$\begingroup$

Floating point arithmetic is an approximation to arithmetic with real numbers. It's an approximation in the sense that all digits of a number aren't stored, but instead are truncated to a certain level of precision. This creates errors, because values like $\sqrt{2}$, which have an unending sequence of digits, can't be stored (because you don't have enough memory to store an unending sequence of digits). This what is meant by "finite-precision": only the largest digits are stored.

Floating point values are represented to within some tolerance, called machine epsilon or $\epsilon$, which is the upper bound of the relative error due to rounding.

When you compose multiple operations which have finite precision, these rounding errors can accumulate, resulting in larger differences.

In the case of zero singular values, this means that due to rounding error, some singular values which are truly zero will be stored as a nonzero value.

An example: some matrix $A$ has singular values $[2,1,0.5,0]$. But your SVD algorithm may return singular values 2.0, 1.0, 0.5, 2.2e-16 or a similarly small number. That final value is numerically zero; it's zero to within the numerical tolerance of the algorithm.

The floating point standard is governed by IEEE 754.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ +1. Please note that in most systems it is straightforward to find their machine zero. E.g. in Python: np.finfo(float).eps or in R: .Machine$double.eps. Also note that this epsilon is "relative"; i.e. if we are dealing with numbers in the 000's then our ability to distinguish goes from e-16 to e-14; (1000 + 1.2e-14) - 1000 equals zero but (1 + 1.2e-14) - 1 equals 1.199041e-14. $\endgroup$ – usεr11852 May 22 at 15:40
  • 1
    $\begingroup$ These are good notes. I've bolded the word "relative" to give it more emphasis. $\endgroup$ – Sycorax May 22 at 15:45
  • $\begingroup$ Oops... I missed it on the first read! :) $\endgroup$ – usεr11852 May 22 at 15:46
6
$\begingroup$

TLDR; In computers numbers are stored in finite slots of memory. For instance, an integer number in mathematics is whole number such as ...,-2,-1,0,1,2,3,... that can go in both directions from negative infinity to positive infinity. In a computer this number can be represented by a type such as int8_t (in C++) which spans from -128 to 127. The situation is even worse with real numbers, such as $\pi$ or $\sqrt 2$. That's what is meant by the author.

The long answer can be as long as you have time for. For instance, "What Every Computer Scientist Should Know About Floating-Point Arithmetic" is a required read for anyone who does numbers on a computer. I'll touch on three subjects.

Computer Integers lack some properties of mathematical integral numbers

Not only integer types are bounded, but they also lack some properties you expect from integral numbers. For instance, in math you expect given $a>0$ and $b>0$ that $a+b>0$ too. Yet, it may not be the case in computer math. For instance, the following code output 110 and not 111 as you'd expect:

#include <iostream>

int main() {
  short int a = 17000, b = 17000, r;
  std::cout << (a > 0);
  std::cout << (b > 0);
  r = a + b;
  std::cout << (r > 0);

}

Computer "real" numbers are countable

The real numbers in mathematics are not countable. That's the huge difference of real numbers from integral and rational numbers. It was a huge breakthrough for European math when Stevin introduced the notion of real numbers, e.g. $\sqrt 2$. They fill the gaps between rational numbers such as 1/3.

Although the number of both real and integral numbers is infinite, there are more real numbers than integral numbers. Weirder though the number of positive and negative whole numbers is the same in math :)

These properties are not preserved in computer math. For instance, there's exactly the same, and finite!, number of double precision real and long integer numbers in C++. It's $2^{64}$ numbers to be precise. So, the cardinality (power set) of what is supposed to be continuum is equal to that of integral (whole) numbers!

arbitrary precision math

Due to these limitation some esoteric math problems are impossible to work on using the standard machine arithmetic. So mathematicians creates libraries for so called arbitrary precision arithmetic libraries that can greatly expand the ranges of numbers stored in a computer. However, "arbitrary" is still a finite notion. When it comes to real numbers they approximate the math concept better than standard machine arithmetic, but they don't fully implement it.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oh man! Memory-lane stuff that paper! +1 $\endgroup$ – usεr11852 May 22 at 16:35
  • $\begingroup$ @usεr11852, you bet, I'm ancient $\endgroup$ – Aksakal May 22 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.