3
$\begingroup$

I'm trying to solve for a vector $\bf x$ of size n, such that given a vector $\bf y$ and nxn matrix $\bf A$ we have:

\begin{equation} \dfrac{\textbf{xA}}{\sqrt{\textbf{xAx}^T}} = \textbf{y} \end{equation}

Essentially this ends up being a system of n equalities, with n degrees of freedom. Further it is scale-invariant in that for any solution $\bf x$ then $k\bf x$ would yield the same result.

So far I've tried to "simplify" it as such:

\begin{equation} \textbf{xA}\circ\textbf{xA} = \textbf{xAx}^T\textbf{y}^2 \end{equation}

I originally hoped I could then proceed to cancel out a pair of $\bf xA$ from each side but it seems that isn't applicable as the underlying multiplication operation is different (Hadamard vs vector/matrix multiply); $\textbf{xAx}^T$ produces a scalar while clearly $\textbf{x}^T$ would leave a vector in its place. One can also rewrite that term as $(\textbf{x} \otimes \textbf{x})\text{vec}(\textbf{A})$ but that doesn't seem very fruitful.

I've tried to solve a small n=5 problem numerically (in R & Matlab), and both produced solutions with a decent amount of error and were also fairly different. Not sure if I've missed something simple but this leads me to suspect that there might be no analytical solution to the problem?

$\endgroup$
4
  • $\begingroup$ Ah yes, that should probably be $\textbf{y} \circ \textbf{y}$. $\endgroup$
    – Charles
    Commented May 3, 2017 at 12:28
  • $\begingroup$ Is $A$ a positive definite matrix? (Otherwise it may be a trouble with $xAx^T\le 0$.) $\endgroup$
    – A.Γ.
    Commented May 3, 2017 at 12:32
  • $\begingroup$ Yes it is - it is actually a correlation matrix so also symmetric. $\endgroup$
    – Charles
    Commented May 3, 2017 at 12:39
  • $\begingroup$ By expanding out the terms I can solve for a single element $x_i$ such that the equation yields $y_i$. It ends up being a quadratic problem though, and not sure how to go about solving a system of simultaneous quadratic equations... $\endgroup$
    – Charles
    Commented May 3, 2017 at 13:14

1 Answer 1

0
$\begingroup$

Assuming $A$ to be positive definite and denoting $t=\sqrt{xAx^T}\ne 0$ we get \begin{align} xA=ty\quad\Rightarrow\qquad (\text{multiply by } A^{-1})\quad x&=tyA^{-1}\qquad\text{and}\\(\text{multiply by } x^T)\quad t^2&=xAx^T=tyx^T\quad\Rightarrow\quad t=yx^T. \end{align} Substitute $x$ from the first line to the second one $$ t=yx^T=tyA^{-1}y^T\quad\Leftrightarrow\quad \fbox{$yA^{-1}y^T=1$}. $$ This is the necessary and sufficient condition for a solution to exist. Then all solutions are given by $$ x=tyA^{-1},\quad t\in\Bbb R. $$

$\endgroup$
5
  • $\begingroup$ Thanks for this. At the moment $\textbf{y}\textbf{A}^{-1}$ is the closest I've got, but it yields solutions with more error than numerical approaches. The problem is the remaining $t$ term on the rhs which is itself a function of $x$... $\endgroup$
    – Charles
    Commented May 3, 2017 at 13:23
  • $\begingroup$ @Charles The equation is scaling invariant, I guess you need more constraints to eliminate the error. Maybe to minimize the error along the line $tyA^{-1}$ with respect to $t$? $\endgroup$
    – A.Γ.
    Commented May 3, 2017 at 13:25
  • $\begingroup$ As a small concrete example, I tested $A = (1\,0.5;\,0.5\,1)$ and $y = (0.5\,0.9)$. If I use straight $\textbf{y}\textbf{A}^{-1}$, I get $x = (0.0667\,0.8667)$, which yields an actual $y = (0.5544\,0.9979)$. If I use a numerical solver it produces the rather different $x = (0\, 0.5639)$, which yields $y = (0.5\,1)$. Neither hit the target (I guess it is not possible but don't understand why mathematically), and the error in the latter is smaller. $\endgroup$
    – Charles
    Commented May 3, 2017 at 13:57
  • $\begingroup$ Ah I missed your point about the condition necessary for a solution to exist. Indeed in cases where I select $y$ such that it satisfies that property, I get an exact solution. Otherwise it seems to produce a solution that is fairly close to but generally not as close as using numerical methods, but perhaps that is unavoidable. $\endgroup$
    – Charles
    Commented May 3, 2017 at 14:17
  • $\begingroup$ @Charles If the condition is not satisfied, one can try a least-square kind of approximation, that is $$ \min_x\left\|\frac{xA}{\sqrt{xAx^T}}-y\right\|=\min_{xAx^T=1}\|xA-y\|. $$ Maybe easier to do the unitary diagonalization of $A$ first. $\endgroup$
    – A.Γ.
    Commented May 3, 2017 at 14:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .