Reconstructed rotation matrix is not the same as the original one I need a little help.
I rotated the vector $s$ using the rotation matrix $R$ and got a new vector $S$.
Now I want to reconstruct the rotation matrix from vectors $s$ and $S$ using the Rodrigues formula.
https://en.wikipedia.org/wiki/Rodrigues%27_rotation_formula See Matrix Notation
The algorithm is standard: I calculate the angle between the vectors $\theta$, the axis of rotation $k$ and the rotation matrix $Q$ using the Rodrigues formula.

Resulting matrix $Q$ does not match the original one $R$. Why? Am I wrong somewhere?
 A: Given two vectors $s$ and $S$, there are multiple rotations taking $s$ to $S$. given $R$ such that $Rs=S$, we can choose any rotation $R'$ such that $R's=s$ and $RR'$ will also satisfy $(RR')s=S$.
More information is needed to uniquely determine the original rotation.
Edit: determining $R$ from two pairs of vectors
First, note that the cross product $\times$ is preserved up to sign by rotations:
$$
R(u\times v)=\begin{cases}
(Ru)\times(Rv) & R\text{ is a proper rotation} \\
-(Ru)\times(Rv) & R\text{ is an improper rotation}
\end{cases}
$$
Suppose we have vectors $s,t,S,T$ with $s,t$ linearly independent and we know that $Rs=S$ and $Rt=T$ for some rotation $R$. Since $s,t$ are linearly independent, $s,t,s\times t$ forms a basis for $\mathbb{R}^3$. The same is true of $S,T,S\times T$, since rotations preserve liner independence. Thus we have
$$
R[s,t,s\times t]=[S,T,\pm S\times T]
$$
where $[u,v,w]$ is the matrix whose columns are vectors $u,v,w$. Since bases form invertible matrices, we have
$$
R=[S,T,\pm S\times T][s,t,s\times t]^{-1}
$$
where choosing $+$ will give a proper rotation and choosing $-$ will give an improper rotation.
A: $
\def\m#1{\left[\begin{array}{r}#1\end{array}\right]}
\def\s#1{{\sqrt #1}}
\def\ss#1#2{{\sqrt\frac{#1}{#2}}}
\def\o{{\tt1}}
\def\tr{\operatorname{Tr}}
$Your
main problem is that you did not calculate the correct axis-angle!
The unit vector representing the axis should be unaffected by the rotation matrix, however multiplying your $k$ vector by the $R$ matrix yields
$$\eqalign{
R\cdot k &= \m{0.354 & 0.612 & 0.707 \\
0.354 & 0.612 & -0.707 \\
-0.866 & 0.500 & 3.062e{-17}}\cdot\m{0.707 \\
0.707 \\
0.000} =
\m{0.683 \\
0.683 \\
-0.259} \ne k \\
}$$
The correct axis-angle are
$$\eqalign{
\theta &= 1.5878, \qquad
k &= \m{
 0.60364 \\
 0.78668 \\
-0.12943} \\
}$$
The Rodrigues formula with these parameters will reproduce the rotation matrix.
The other problem that you're fighting is round-off error in the rotation matrix itself.
The exact rotation matrix is
$$
R = \frac 14\m{
 \s{ 2}&\s{6}& \s{8} \\
 \s{ 2}&\s{6}&-\s{8} \\
-\s{12}&\s{4}&    0  \\
}\\
$$
The most reliable way to obtain the axis is to calculate the Eigenvalue decomposition of $R$. It will have one real eigenvalue (equal to unity) and two imaginary eigenvalues (conjugate pairs). The eigenvector corresponding to unity is the axis of rotation.
The angle can be reliably calculated using the simple formula
$$\theta = \operatorname{acos}\left(\frac{\tr(R)-\o}{2}\right)\\$$

Update
Here's a way to compute the axis of rotation which doesn't require an Eigenvalue Decomposition.
$$\eqalign{
{\tt(1)}\quad &\lambda &= \tr(R) - \o \\
{\tt(2)}\quad &s &= \{random\;vector\} \\
{\tt(3)}\quad &v &= \left(R^T+R-\lambda I\right)s \\
{\tt(4)}\quad &{\rm if}&\,v\approx 0,\;{\rm goto\,step\,}{\tt(2)} \\
{\tt(5)}\quad &k &= \frac{\pm v}{\|v\|} \\
}$$
You can choose $s=\m{0\\0\\1}$ in Step $(\tt2)$, if you wish.
