Finding the Quaternion that rotates a coordinate system to match another. Let's say I want to figure out the orientation of my cell phone. Assume that the phone has two internal sensors that report orientation (a quaternion), but both are a bit unreliable, so I'd like to use them together.
HOWEVER, the coordinate frames the sensors report a quaternion are not the same.
1) Sensor 1 reports q1, a quat in the following frame:
+x = up, +y = right, +z = forward
2) Sensor 2 reports q2, a quat in the following frame:
+x = down, +y = forward, +z = left
Note that both frames are right handed, and there exists a quaternion that rotates frame 1 to frame 2 (I think).
I'd like to apply a rotation to whatever orientation I'm getting from sensor 1, so the data roughly matches readings from sensor 2.
qx * q1 ~= q2
I'd like to figure out what qx is.
ALTERNATE SOLUTION:
I was able to convert q1 into q2 frame using:
q1_in_q2_frame = [-q1i, q1k, q1j, q1]
But, I'd like to achieve this result by figuring out what qx is, because the coordinate frames are not necessarily like what I said before, they could be more arbitrary. Imagine sensor 2 always resets its frame to whatever orientation the cell phone was in when you turn it on/off, so a new qx has to be calculated.
WHAT I'VE TRIED:
I thought I could just multiply the following equation by q1' from left:
qx * q1 ~= q2
qx * q1 * q1' = q2 * q1'
qx = q2 * q1'
While the above solution gives me a correct mapping for the current values of q1 and q2, qx becomes no longer valid when I rotate the cell phone.
UPDATE:
I think I made an error in my quaternion multiplications.
Instead of qx * q1 ~= q2, I should really have:
qx * q1 * qx' ~= q2
But given q1 and q2, how do I figure out qx now?
 A: There is a simple algebraic solution in terms of quaternions (to your revised question.)
If $v_1$ and $v_2$ are unit quaternions with real part zero, then $q=\frac{v_1(v_1+v_2)}{|v_1+v_2|}$ is a quaternion such that $\bar{q}v_1q=v_2$.  The caveat is, of course, that $v_1$ and $v_2$ do not point in opposite directions, so that the division is defined. If they point in opposite directions, well, you can take any 180 degree rotation in a plane containing the vectors to achieve your goal.
Why does this work? If you go digging, you'll find the formula for $q$ to rotate an element of $\mathbb R^3$ to another (both represented as pure imaginary quaternions with zero real part) then the way to do it is to compute $\cos(\theta/2)-\sin(\theta/2)v_3$ where $v_3$ is the (right hand) unit normal to the plane spanned by $v_1$ and $v_2$, and $\theta$ is the angle measured between $v_1$ and $v_2$.
Now it turns out that $v_1v_2=-\cos(\theta)+\sin(\theta)(v_1\times v_2)$ and since its negative also represents the same rotation, we can see we're not far off: our angle is just double what it needs to be. What to do then?
That's where $\frac{v_1+v_2}{|v_1+v_2|}$ comes in: it's a new vector which produces the same unit normal as before, but now the angle has been halved.
Now, you say, "but I don't want $q_1$ and $q_2$ to have zero real part, I want them to be arbitrary."  But that's OK, because when you conjugate with a unit quaternion, it leaves the real part alone. So all you need to do is to compute $q$ as I described for the pure quaternions parts of $q_1$ and $q_2$, and that will work to satisfy $\bar{q}q_1q=q_2$.
A: Are you familar with Direct Cosine Matrices? You are able to form the DCM by directly taking the dot product of the axes. You can then convert the DCM to a quaternion
Take a look at www.starlino.com/dcm_tutorial.html as an example. 
A: Not sure if I understand your question. But for your last update you are looking for quaternion $x$ such that the following equation holds for some quaternions $p$ and $q$.
$x q x^* = p$
S.t. $x x^* = 1$
As there is no algebraic solution to this equation the next thing to do is casting the problem to the language of linear algebra.
First notice that the equation $x q x^* = p$ is equivalent to 
$x q - p x = 0$
S.t. $x x^* = 1$
The product $x q$ can be expressed in linear algebra as a matrix multiplication of a $4 \times 4$ matrix $Q$ representing the quaternion $q$ and a $4 \times 1$ column vector $X$ representing quafernion $x$.
The product $p x$ can be expressed in linear algebra as a matrix multiplication of a $4 \times 4$ matrix $P$ representing the quaternion $p$ and a $4 \times 1$ column vector $X$ representing quafernion $x$.
So we have now:
$Q X - P X = 0$
S.t. $X^T X = 1$
Which is a pretty standard matrix equation. Factorizing the $X$ we get:
$(Q - P) X = 0$
S.t. $X^T X = 1$
We can see that the solution is in the null space of the matrix $A = Q - P$. Using the Simgular Value Decomposition (SVD) of the matrix $A$ we get that $A = U D V^T$ where $U$, $D$ and $V$ are $4 \times 4$ square matrices. $D$ is a diagonal matrix containing the singular values. 
If all values in the diagonal of $D$ are nonzero, then $A$ is full rank and no solution exists (the null space of $A$ is $0$). 
If only one value in the diagonal of $D$ is zero then there is only one solution for $X$ which is the column of $V$ corresponding to the zero diagonal value.
If more than one value is zero then there are multiple solutions for $X$. You should choose one.
The constraint $X^T X = 1$ is fulfilled by SVD since the matrix $V$ is orthonormal.
Finally I will define the $Q$ and $P$ matrices given quaternion $q = q_0 + q_x i + q_y j + q_z k$ and quaternion $p = p_0 + p_x i + p_y j + p_z k$:
$x q = Q X = \begin{bmatrix}
q_0&-q_x&-q_y&-q_z\\
q_x&q_0&q_z&-q_y\\
q_y&-q_z&q_0&q_x\\
q_z&q_y&-q_x&q_0
\end{bmatrix} X$
$p x = P X = \begin{bmatrix}
p_0&-p_x&-p_y&-p_z\\
p_x&p_0&-p_z&p_y\\
p_y&p_z&p_0&-p_x\\
p_z&-p_y&p_x&p_0
\end{bmatrix} X$
Note that $Q$ differs from $P$ in that the lower $3 \times 3$ submatrix is transposed. This is because the noncommutative nature of multiplication of quaternions.
