patternMinor
Can you complete a basis in polynomial time?
Viewed 0 times
canbasispolynomialyoutimecomplete
Problem
Here is the problem: we are given vectors $v_1, \ldots, v_k$ lying in $\mathbb{R}^n$ which are orthogonal. We assume that the entries of $v_i$ are rational, with numerator and denominator taking $K$ bits to describe. We would like to find vectors $v_{k+1}, \ldots, v_n$ such that $v_1, \ldots, v_n$ is an orthogonal basis for $\mathbb{R}^n$.
I would like to say this can be done in polynomial time in $n$ and $K$. However, I'm not sure this is the case. My question is to provide a proof that this can indeed be done in polynomial time.
Here is where I am stuck. Gram-Schmidt suggests to use the following iterative process. Suppose we currently have the collection $v_1, \ldots, v_l$. Take the basis vectors $e_1, \ldots, e_n$, go through them through them one by one, and if some $e_i$ is not in the span of the $v_1, \ldots, v_l$, then set $v_{l+1} = P_{{\rm span}(v_1, \ldots, v_l)^\perp} e_i$ (here $P$ is the projection operator). Repeat.
This works in the sense that the number of additions and multiplications is polynomial in $n$. But what happens to the bit-sizes of the entries? The issue is that the projection of $e_i$ onto, say, $v_1$ may have denominators which need $2K$ bits or more to describe - because $P_{v_1}(e_i)$ is $v_1$ times its $i$'th entry, divided by $||v_1||$. Just $v_1$ times its $i$'th entry may already need $2K$ bits to describe.
By a similar argument, it seems that each time I do this, the number of bits doubles. By the end, I may need $2^{\Omega(n)}$ bits to describe the entries of the vector. How do I prove this does not happen? Or perhaps should I be doing things differently to avoid this?
I would like to say this can be done in polynomial time in $n$ and $K$. However, I'm not sure this is the case. My question is to provide a proof that this can indeed be done in polynomial time.
Here is where I am stuck. Gram-Schmidt suggests to use the following iterative process. Suppose we currently have the collection $v_1, \ldots, v_l$. Take the basis vectors $e_1, \ldots, e_n$, go through them through them one by one, and if some $e_i$ is not in the span of the $v_1, \ldots, v_l$, then set $v_{l+1} = P_{{\rm span}(v_1, \ldots, v_l)^\perp} e_i$ (here $P$ is the projection operator). Repeat.
This works in the sense that the number of additions and multiplications is polynomial in $n$. But what happens to the bit-sizes of the entries? The issue is that the projection of $e_i$ onto, say, $v_1$ may have denominators which need $2K$ bits or more to describe - because $P_{v_1}(e_i)$ is $v_1$ times its $i$'th entry, divided by $||v_1||$. Just $v_1$ times its $i$'th entry may already need $2K$ bits to describe.
By a similar argument, it seems that each time I do this, the number of bits doubles. By the end, I may need $2^{\Omega(n)}$ bits to describe the entries of the vector. How do I prove this does not happen? Or perhaps should I be doing things differently to avoid this?
Solution
The result of the Gram-Schmidt can be expressed in determinantal form, see Wikipedia. This shows that the output of the Gram-Schmidt process is polynomial size. This suggests that if you run the classical Gram-Schmidt process, then all intermediate entries are also polynomial size (even in LLL, all intermediate entries are polynomial size). However, even if it is not the case, then using efficient algorithms for computing the determinant (see my other answer), you can compute the Gram-Schmidt orthogonalization in polynomial time.
Context
StackExchange Computer Science Q#10906, answer score: 3
Revisions (0)
No revisions yet.