most recent 30 from http://mathoverflow.net 2013-05-21T17:04:36Z http://mathoverflow.net/feeds/question/79290 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79290/how-to-do-mgram-schmidt-orthogonalization-with-integers-real-life-problem Alexander Chervov 2011-10-27T17:47:25Z 2012-01-17T04:22:12Z

<p>New edition of the question, "mathematicalized" (thanks to Gerhard).</p> <p>Consider and integer valued n*n matrix M, with integers elements in the range -N &lt; m &lt; 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.</p> <p>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.</p> <p>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).</p> <p>=========== 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) ?</p> <p>[ 32768.000000 , 0.000000 , -1424.000000 , -1422.000000 ; ... </p> <p>24219.000000 , 10476.000000 , 3107.000000 , 3109.000000 ; ... </p> <p>-18861.000000 , -22098.000000 , 32768.000000 , 32768.000000 ; ...</p> <p>-20462.000000 , 32768.000000 , 3939.000000 , 3940.000000 ];</p> <p>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 &lt;= m &lt;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.</p> <p>The task is do <a href="http://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt" rel="nofollow">Gram-Schmidt orthogonalization</a> 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:</p> <pre><code>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 </code></pre> <p>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).</p>

http://mathoverflow.net/questions/79290/how-to-do-mgram-schmidt-orthogonalization-with-integers-real-life-problem/80343#80343 rcompton 2011-11-07T23:31:58Z 2011-11-07T23:31:58Z

<p>Well, if your microprocessors can handle fixed point arithmetic then here is a matlab commercial that should do it: <a href="http://www.mathworks.com/products/fixed/demos.html?file=/products/demos/shipping/fixedpoint/cordicqr_demo.html" rel="nofollow">http://www.mathworks.com/products/fixed/demos.html?file=/products/demos/shipping/fixedpoint/cordicqr_demo.html</a></p> <p>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.</p>