Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this 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
add comment

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.

1 Answer

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} $

Let

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

Let

$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|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
add comment

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