Actually you might use Gram Schmidt here.

Given a set of ortogonal vectors $x_1,x_2,\ldots,x_k$ you can use Gram-Shmidt algorithm for set of vectors $\{x_1,x_2,...,x_k,e_i}$ adding basis vector to system of ortogonalysed vectors (note that you need use Gram Schmidt procedure only to find last vector since first k vectors are already orthogonal). Then (since vectors $e_1,e_2,\ldots,e_{k+1}$ are linearly independent) for some i between 1 and k+1 Gram Schmidt will give you non-zero vector which is ortogonal to given vectors $x_1,x_2,\ldots,x_k$ 

So to find a guess you simply need to use Gram Schmidt procedure several times (no more than k+1 for the first guess and no more then two times for next guesses).

To simplify this procedure you can do this only with first $k+1$ coordinates of vectors, so you will find a vector of form $(y_1,y_2,\ldots,y_{k+1},0,0,\ldots)$. Answers of Kapil and Klaus are actually equivalent to using this route.