[Math] How to do (m)Gram-Schmidt orthogonalization with integers ? (real life problem) (“mathematicalized reformulation”)

linear algebramatricesna.numerical-analysis

New edition of the question, "mathematicalized" (thanks to Gerhard).

Consider and integer valued n*n matrix M, with integers elements in the range -N < m < N.
I want to find integer-valued approximate orthogonalization of this matrix X.
Means that values of X are integers in the same range and matrix is "close" to the honest Gram-Schmidt orthogonalization of initial matrix X_honest.

Is there some bound norm ( X- X_honest) > f( condition(M) ) ?
E.g. it is difficult to solve the problem if original matrix is ill-conditioned.

Is there way to find such matrix in reasonable complexity O(n^3) ?
(and not using sophistaced arithmetical representation of numbers e.g.
emulation of floating point or rational or Chinese remainder theorem is not allowed).

===========
Try to do orthogonalization of these column vectors.
Problem is that the 3-th and 4-th are almost the same.
Is there some nice solution ?
Or some no-go result can be proved that with integers I cannot do this ?
Or I can do it but not within reasonable complexity O(n^3) ?

[ 32768.000000 , 0.000000 , -1424.000000 , -1422.000000 ; …

24219.000000 , 10476.000000 , 3107.000000 , 3109.000000 ; …

-18861.000000 , -22098.000000 , 32768.000000 , 32768.000000 ; …

-20462.000000 , 32768.000000 , 3939.000000 , 3940.000000 ];

More details.
The processing units used in fast or low-energy computing devices like mobile phones, GPS, signal processors do not support floating point arithmetics.
I.e. they can work we integers e.g. -2^15 <= m <2^15-1
And when you do multiplication of such two must truncate result back to this region
before you can do any other operation.

The task is do Gram-Schmidt orthogonalization
of a matrix on such device.
When I do it I see that resulting vectors are far from orthogonal
Matrix of normalized scalar products is the following:

1.0000    0.0000    0.0000    0.1764

0.0000    1.0000    0.0000    0.5667

0.0000    0.0000    1.0000    0.4438

0.1764    0.5667    0.4438    1.0000

Is there some nice way to cure the problem or no ?
I would prefer that complexity (i.e. number of operations) is not much bigger that in standard algorithm. i.e. O(n^3).

Best Answer

Well, if your microprocessors can handle fixed point arithmetic then here is a matlab commercial that should do it: http://www.mathworks.com/products/fixed/demos.html?file=/products/demos/shipping/fixedpoint/cordicqr_demo.html

Gram-Schmidt is not numerically stable even when you can use floating point so my guess is that you will have many problems if you stay that course.

Related Question