0
$\begingroup$
  • $\vec{a}\cdot\vec{b} \approx c$
  • $\vec{\alpha} \cdot \vec{\beta} = c$
  • $\vec{\alpha}$ is close to $\vec{a}$ and $\vec{\beta}$ is close to $\vec{b}$

Given $\vec{a}$, $\vec{b}$ and c, how to find $\vec{\alpha}$, $\vec{\beta}$ quickly?

If necessary, I can assume distance between $\vec{\alpha}$ and $\vec{a}$ is usually much smaller than distance between $\vec{b}$ and $\vec{\beta}$.

Each vector has about 10 - 15 elements but I have to do this for about 10^4 vectors.

If probability should sum to 1 is the constraint, I can normalize the probabilty after each (or several) optimization step to control the numerical error. But I can't do the same thing for this constraint.

Lagrange multipliers and Linearization of the constraints give:

$ \vec{b} \cdot \vec{\alpha} + \vec{a} \cdot \vec{\beta} = \vec{\alpha} \cdot \vec{\beta} + \vec{a} \cdot \vec{b}$

$\vec {\alpha} + \lambda \vec{\beta} = \vec{a} $

$\vec {\beta} + \lambda \vec{\alpha} = \vec{b} $

This is still not a linear system because of the $\lambda \vec{\alpha}$ terms.

How to do this faster?

|cite|improve this question
$\endgroup$
  • $\begingroup$ If I use lagrange multipliers, I get a non-linear (quadratic) system. $\endgroup$ – R zu Oct 24 '18 at 17:17
  • $\begingroup$ Linearizing the constraint around $\vec a$ and $\vec b$ leads to 2N + 1 equations with 2N + 1 unknowns. $\endgroup$ – R zu Oct 24 '18 at 17:36
  • $\begingroup$ Maybe I can do two Newton iterations. Fix beta and find alpha and lambda. Then fix alpha and find beta and lambda. Alternate till converge. $\endgroup$ – R zu Oct 24 '18 at 18:13
  • 1
    $\begingroup$ This is an underdetermined problem so there are many many solutions. For example, just set $\alpha=a,\beta=bc/(a\cdot b)$. Since $a\cdot b\approx c$ you still get $\beta$ close to $b$. $\endgroup$ – Rahul Oct 24 '18 at 20:20
  • $\begingroup$ If close means least square, then the problem becomes the last 3 equations I wrote. It is a non-linear system with n equations and n unknowns. hmm. I might try your normalization. Any one of the solutions would work. $\endgroup$ – R zu Oct 24 '18 at 20:31
2
$\begingroup$

There are of course infinitely many vectors $\vec \alpha,\vec \beta$ that satisfy $\vec \alpha\cdot\vec \beta=c$. So if you want to have a particular pair of vectors, you will have to be precise when stating what you mean that $\vec \alpha,\vec \beta$ should be "close" to $\vec a,\vec b$.

One pair that satisfies this is $$ \vec \alpha = \vec a, \qquad \qquad \vec \beta = \frac{c}{\vec a \cdot \vec b}\;\vec b. $$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I should have read the comments first -- this is of course exactly @Rahul's solution. $\endgroup$ – Wolfgang Bangerth Oct 24 '18 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.