Convert Least Square equations to matrix form

Question

I want to minimize following equation using Least Square:

$$ f = min\sum_{j=1}^{m} \sum_{i=1}^{n}(p_{ij}a_{i} + q_{ij}b_{i} + r_{ij}tx_{j} + s_{ij}ty_{j})^{2} $$

with respect to $a_{i}$, $b_{i}$, $tx_{j}$, $ty_{j}$.

And $p_{ij}$,$q_{ij}$,$r_{ij}$, $s_{ij}$ are known.

What I did is to take the partial derivative of f with respect to $a_{i}$, $b_{i}$, $tx_{j}$, $ty_{j}$ respectively and set those partial derivative to $0$ to get all the equations.

For example, for partial derivate of f wrt $a_{i}$:

$$ \sum_{j=1}^{m} \sum_{i=1}^{n}2(p_{ij}a_{i} + q_{ij}b_{i} + r_{ij}tx_{j} + s_{ij}ty_{j})p_{ij} = 0 $$

My question is how can I convert all the equations I got from those partial derivatives and convert them to a Matrix form to solve for all the $a_{i}$, $b_{i}$, $tx_{j}$, $ty_{j}$ parameters.

For example, the final matrix form should be some Matrix A multiply vector X,

$$ AX=0 $$

where X:

$$ X=\begin{bmatrix} a_{1}\\ a_{2}\\ .\\ .\\ .\\ a_{n}\\ b_{1}\\ b_{2}\\ .\\ .\\ .\\ b_{n}\\ tx_{1}\\ tx_{2}\\ .\\ .\\ .\\ tx_{m}\\ ty_{1}\\ ty_{2}\\ .\\ .\\ .\\ ty_{m}\\ \end{bmatrix} $$

How can I get A? Thanks very much.

Answer 1

Problem statement

Given four matrices $$ \mathbf{P}, \mathbf{Q}, \mathbf{R}, \mathbf{S} \in \mathbb{C}^{m\times n}, $$

Find the four solution vectors $$ a, b, x, y \in \mathbb{C}^{n} $$ which solve the equation $$ \mathbf{P} a + \mathbf{Q} b + \mathbf{R} x + \mathbf{S} y = 0. $$ By assumption, there is no exact solution.

The observation of @littleO is to create a block formulation: $$ \left[ \begin{array}{cccc} \mathbf{P} & \mathbf{Q} & \mathbf{R} & \mathbf{S} \end{array} \right] % \left[ \begin{array}{c} a \\ b \\ x \\ y \end{array} \right] = \mathbf{O} $$ where $\mathbf{0}$ has dimension $4n\times 1$.

The problem is now one of reduction to find the null space.

The method of least squares

A careful statement of the least squares problem starts with the linear system $$ \mathbf{A} x = b $$ with $$ \mathbf{A}\in\mathbb{C}^{m\times n},\, x \in \mathbb{C}^{n},\, b \in \mathbb{C}^{m}. $$ The problem provides the matrix $\mathbf{A}$, the data vector $b$, and asks for the solution vector $x$.

In this case $$ \mathbf{A} = \left[ \begin{array}{cccc} \mathbf{P} & \mathbf{Q} & \mathbf{R} & \mathbf{S} \end{array} \right] $$ And the matrix maps data in measurement space, an $n-$space, onto an affine parameter space, an $m-$space. The goal is to find the least squares solution defined as $$ x_{LS} = \left\{ x \in \mathbb{C}^{n} \colon \lVert \mathbf{A} x - b \rVert_{2}^{2} \text{ is minimized} \right\} $$ The full statement of the least squares requirement is that the data vector is not in the null space: $$ b \notin \mathcal{N}\left( \mathbf{A} \right) $$ This demand insures existence of a solution.

Changing the problem

To conclude: as written we do not have a least squares problem, we have the challenge of finding a span for the null space of the block matrix $\mathbf{A}$. If you were to stir in a nonzero $m-$vector, say, $\beta \notin \mathcal{N}\left( \mathbf{A} \right)$, we would have a least squares problem: $$ \left[ \begin{array}{cccc} \mathbf{P} & \mathbf{Q} & \mathbf{R} & \mathbf{S} \end{array} \right] % \left[ \begin{array}{c} a \\ b \\ x \\ y \end{array} \right] = \beta $$

Answer 2

Building on what @dantopia wrote, the problem is that the RHS of

$$ \left[ \begin{array}{cccc} \mathbf{P} & \mathbf{Q} & \mathbf{R} & \mathbf{S} \end{array} \right] % \left[ \begin{array}{c} a \\ b \\ x \\ y \end{array} \right] = \mathbf{O} $$ is 0, or in short form $$ \mathbf{X}\boldsymbol{\beta}=\mathbf{y}\,. $$ Wouldn't the resolution to the problem be to define a set of related variables which would simply yield a non-zero RHS, like this $$ \boldsymbol{\beta}' \equiv \left[ \begin{array}{c} a' \\ b' \\ x' \\ y' \end{array} \right] \equiv \left[ \begin{array}{c} a+1 \\ b+1 \\ x +1 \\ y +1 \end{array} \right] = \boldsymbol{\beta} + \boldsymbol{1} $$

I've picked a vector of 1s here, but it could be any constant offset that is known and doesn't make the RHS 0. Then the top equation becomes

$$ \left[ \begin{array}{cccc} \mathbf{P} & \mathbf{Q} & \mathbf{R} & \mathbf{S} \end{array} \right] % \left[ \begin{array}{c} a \\ b \\ x \\ y \end{array} \right] = \left[ \begin{array}{c} \mathbf{P}\cdot 1 \\ \mathbf{Q}\cdot 1 \\ \mathbf{R} \cdot 1\\ \mathbf{S} \cdot 1 \end{array} \right] $$

Thus we would solve for the primed quantities in the least squares, and then back out the desired un-primmed ones from this equation. The equation to minimize then becomes in the standard least squares form $$ \mathbf{X}\boldsymbol{\beta}'=\mathbf{y}\,. $$

This allows us to employ the standard method of least squares to an overdetermined system of equations $$ \hat{\boldsymbol{\beta}}' = (\mathbf{X}^{{\rm T}}\mathbf{X})^{-1}\mathbf{X}^{{\rm T}}\mathbf{y}\,. $$

Finally, your solution is $$ \hat{\boldsymbol{\beta}} = \hat{\boldsymbol{\beta}}' - \boldsymbol{1} $$