MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm looking for closed form solution for the following equation:

$argmin_{X,y}(\sum_i{\parallel{a_i-Xb_i-y}\parallel^2})$, where $X \in\mathbb R_{m\times n}$ is a matrix and $y\in\mathbb R_{m\times 1}$ is a vector, for sufficient $i$ to make those equations over-determined. As I understand there is a closed form solution to this least squares problem

of course it is possible to incorporate $y$ into $X$ to make it simpler:

$argmin_X(\sum_i{\parallel{a_i-Xb_i}\parallel^2})$, where $X=[X\space y] $ and $b_i=[b_i;1]$

Thank you

share|cite|improve this question

closed as off-topic by Noah Stein, Ricardo Andrade, Stefan Kohl, Andy Putman, Andrey Rekalo Dec 19 '13 at 18:02

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Noah Stein, Andy Putman
If this question can be reworded to fit the rules in the help center, please edit the question.

Your argmin notation suggests the unknown you are looking for is the matrix X, while a_i and b_i are a sequence of given vectors? – Andrew T. Barker Dec 19 '13 at 10:08
That is correct $a_i$ and $b_i$ are known, least squares problem is defined for finding matrix $X$ – genawas Dec 19 '13 at 10:12
As I know, in the least squares problem $a_i$ and $b_i$ are unknown with given $X,y$. – Boris Novikov Dec 19 '13 at 10:36
This is not a classical LSQ: argmin(norm(Ax+b)), where the solution for x is $(A^TA)^{-1}A^Tb$ – genawas Dec 19 '13 at 10:46

You simply need to recognize that this is already a linear least squares problem and then work through the notation to put it into a form that you can give to a suitable solver.

Begin with the problem in the form

$ \min_{X} \sum_{i=1}^{m} \| a_{i} - X b_{i} \|_{2}^{2} $

We'll assume that $X$ is a square matrix of size $n$ by $n$.

Next, look at an individual term $ \| a - X b \|_{2}^{2} $

Note that I've removed the subscript $i$ to simplify the notation in the following.

Reorganize $X$ by stacking columns of $X$ into a vector $x$, where $x_{1}=X_{1,1}$, $x_{2}=X_{2,1}$, $\ldots$, $x_{n}=X_{n,1}$, $x_{n+1}=X_{1,2}$, $\ldots$, $x_{n^{2}}=X_{n,n}$.

Now, write $Xb$ as $Ux$, where row $j$ of $U$ multiplied by $x$ gives the $j$th entry in $Xb$. The $j$th entry in $Xb$ comes from row $j$ of $X$ multiplied by the elements of $b$. That is, $\sum_{k=1}^{n} X_{j,k}b_{k}$ or $\sum_{k=1}^{n} x_{j+(k-1)n}b_{k}$. Thus

$ U_{j,j+(k-1)n}=b_{k} $

for $k=1, 2, \ldots, n$ and $j=1, 2, \ldots, n$.

The remaining entriesin $U$ are 0's. Thus $U$ is a very sparse matrix.

Repeat this process for each term, $i=1, 2, \ldots, m$ and call the resulting $U$ matrices $U_{1}$, $U_{2}$, $\ldots$, $U_{m}$. You now have the problem in the form

$ \min \sum_{i=1}^{m} \| a_{i} - U_{i} x \|_{2}^{2} $


$ W=\left[ \begin{array}{c} U_{1} \\ U_{2} \\ \vdots \\ U_{m} \end{array} \right] $


$v=\left[ \begin{array}{c} a_{1} \\ a_{2} \\ \vdots \\ a_{m} \end{array} \right] $

Now, your problem is a conventional least squares problem

$ \min_{x} \| v-Wx \|_{2}^{2} $

You can express the solution to this least squares problem using the normal equations as:

$ x=\left( W^{T}W \right)^{-1} W^{T}v $

However, in practice it is probably better to not explicitly form the $W^{T}W$ matrix and take its inverse. Given the sparsity of $W$, using an iterative method might be appropriate. There are also "sparse QR" factorization methods that might be appropriate.

share|cite|improve this answer
Thank you very much, Brian W is a sparse block matrix, with blocks that should appear in the diagonal... – genawas Dec 19 '13 at 17:23

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