2
$\begingroup$

I'm looking for an approach to minimize the distance in $\|\cdot\|_2$ between a pair of unknown points $\mathbf{P}_1, \mathbf{P}_2 \in \mathbb{R}^3$ and a preferred set of points $\mathbf{R}_1, \mathbf{R}_2 \in \mathbb{R}^3$.

There is a set of equality constraints, each one involving $\mathbf{P}_1$ and/or $\mathbf{P}_2$, which together form a linear system of vector equations.

In addition, these equality constraints contain unknown scalar variables (at least one in total, likely more).

Probably the simplest case is a square non-singular system of equations (i.e. the equality constraints) and a single unknown scalar variable. In that case, the problem amounts to optimizing the value of that scalar variable, in the sense that it minimises $\sum \|\mathbf{R}_i - \mathbf{P}_i\|_2$.

Consider for example the following equality constraints:

$$\left(\begin{array}{cc} a & b\\ c & d \end{array}\right) \left(\begin{array}{c} \mathbf{P_1}\\ \mathbf{P_2} \end{array}\right) = \left(\begin{array}{c} e\mathbf{Q_1} + \lambda(\mathbf{Q_2} - \mathbf{Q_1})\\ f\mathbf{Q_2} + \lambda(\mathbf{Q_3} - \mathbf{Q_2}) \end{array}\right),$$

with

  • $a$, $b$, $c$, $d$, $e$ and $f$ known values in $\mathbb{R}$,
  • $\mathbf{P_i}$, $i \in \{1,2\}$ unknown elements of $\mathbb{R}^3$,
  • $\mathbf{Q_j}$, $j \in \{1,2,3\}$ known elements of $\mathbb{R}^3$,
  • $\lambda$ an unknown value in $\mathbb{R}$.

Other cases are underdetermined systems of equations and overdetermined ones, both of which can occur within my context.

Different aspects of the problem seem to point into different directions (e.g. least squares, normal equations for solving under-/over-determined systems, Lagrange multipliers, ...). As I'm not sure how to proceed from here, references, hints or (partial) solutions would be most welcome.


[Edit] Updated formulation of the question (removed an aspect that was previously there and has been solved below).

$\endgroup$
1
$\begingroup$

Hint

So we have

$$\left(\begin{array}{cc} a & b\\ c & d \end{array}\right) \left(\begin{array}{c} \mathbf{P_1}\\ \mathbf{P_2} \end{array}\right) = \left(\begin{array}{c} e\mathbf{Q_1} + \lambda(\mathbf{Q_2} - \mathbf{Q_1})\\ f\mathbf{Q_2} + \lambda(\mathbf{Q_3} - \mathbf{Q_2}) \end{array}\right),$$

The main step is to choose a vectorization for the unknowns, for example $\left(\begin{array}{c} \mathbf{P_1}\\ \mathbf{P_2}\\\lambda \end{array}\right)$

Now try and rewrite your expression to one involving the vectorized unknowns with matrix multiplication and addition.


additional hint scalar multiplication $s{\bf A}$ is "syntactic sugar" for $(s{\bf I}){\bf A}$, in other words there is a hidden identity matrix involved.

If $3$ dimensional vectors we can write $$\left[\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}\right] \cdot s=\left[\begin{array}{ccc}s&0&0\\0&s&0\\0&0&s\end{array}\right]$$ but in general we want a Kronecker product : ${\bf I_N}\otimes s$.

It means inserting copies of $s$ into each element of $\bf I_N$ and multiplying with the scalar there.


I can solve it more completely later if you want me to, but it is a good exercise to try do the following procedure oneself.

$\endgroup$
  • $\begingroup$ Well, symbolically I could rewrite this as $$\left(\begin{array}{ccc} a & b & (\mathbf{Q_1} - \mathbf{Q_2})\\ c & d & (\mathbf{Q_2} - \mathbf{Q_3}) \end{array}\right) \left(\begin{array}{c} \mathbf{P_1}\\ \mathbf{P_2}\\ \lambda \end{array}\right) = \left(\begin{array}{c} e\mathbf{Q_1}\\ f\mathbf{Q_2} \end{array}\right),$$ though I'm not sure how useful this is as the matrix now contains both scalars and vectors (and re-writing the vectors as $3$ scalars each does not seem to make much sense, unless I'm missing something). $\endgroup$ – Ailurus Mar 6 '18 at 17:33
  • $\begingroup$ Comment was too long. Wanted to add the following — I'm curious about your approach (though additional hints are also welcome). $\endgroup$ – Ailurus Mar 6 '18 at 17:34
  • 1
    $\begingroup$ @Ailurus scalar multiplication on matrices/vectors involves a "hidden"/implicit identity matrix. That is often how multiplication by scalar is defined. $\endgroup$ – mathreadler Mar 6 '18 at 17:51
  • 1
    $\begingroup$ Ah, so I replace $a$ and other scalars by $aI$ in the matrix, turning it into a $6 \times 7$ matrix? That should work :) $\endgroup$ – Ailurus Mar 6 '18 at 20:42
  • $\begingroup$ However, using the approach based on normal equations now also requires an initial `guess' for $\lambda$, which influences the eventual solution (it finds the solution closest — in the sense of the 2-norm — to the initial guess). Any ideas on how to avoid this? $\endgroup$ – Ailurus Mar 6 '18 at 21:25

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.