# Minimize $\arg \min_{A} {\| A x - b \|}_{2}$ (Least Squares Minimization on the Matrix)

I have a machine learning regression problem. I need to minimize

$$\sum_i \|Ax_i-b_i\|_2^2$$

However I am trying to find matrix $A$, not the usual $x$, and I have lots of example data for $x_i$ and $b_i$. In general $A$ has more rows than columns.

Additionally I would like a solution for minimizing the Mahalanobis distance version, where $C$ is the SPSD covariance matrix:

$$\sum_i(Ax_i-b_i)^TC^{-1}(Ax_i-b_i)$$

I'm thinking that my problem can be re-written into the usual least squares problem but not sure if I am doing it correctly.

• Did you mean $\|Ax_i-b_i\|^2$, or are you trying to minimize the L1 norm? Sep 18, 2012 at 0:52
• What norm are you using on the 'inside'? Is $C$ symmetric positive-definite? Sep 18, 2012 at 0:57
• I corrected the text to clarify the L2 norm. Sep 18, 2012 at 2:18

Yes. Expanding the sum we get

\begin{align*}\sum_i \|Ax_i-b_i\|^2 &= \sum_i \sum_j (Ax_i-b_i)_j^2\\ &= \sum_i \sum_j \left(\sum_k A_{jk}x_{ki} - b_{ji}\right)^2\\ &= \sum_i \sum_j \left(\sum_k x^T_{ik} A^T_{kj} - b^T_{ij}\right)^2\\ &= \sum_i \sum_j (x^T A^T_j - b^T_j)_i^2\\ &= \sum_j \|x^T A^T_j - b_j^T\|^2. \end{align*}

So you can solve the problem using regular least squares; your matrix $x^T$ has rows equal to your original known vectors $x_i$, the unknown vector $A_j^T$ is the $j$th row of $A$, and $b_1^T$ is the vector containing all of the first entries of the $b_i$, etc.

• The OP asks to minimize the L1 norm. Sep 18, 2012 at 0:46
• Fair point; I assumed that was a typo since linear regression is usually done with least squares. I'll ask for clarification. Sep 18, 2012 at 0:51
• Sorry about that it is supposed to be the L2 norm. Sep 18, 2012 at 2:07

For the second problem, note $$\frac{\rm d}{\rm{d} A}((Ax-b)^TC^{-1}(Ax-b))=-2xb^T{C^{-1}}^T+{C^{-1}}^TAxx^T+C^{-1}Axx^T$$ so if $C^{-1}$ is symmetric (hence $C$ is also symmetric), we have the normal equation for $\sum_i(Ax_i-b_i)^TC^{-1}(Ax_i-b_i)$ $$\sum_iAx_ix_i^T=\sum_iCx_ib_i^TC^{-1}$$ or $$\sum_ix_ix_i^TA^T=\sum_iC^{-1}b_ix_i^TC$$

So $A$ can be computed row by row, and let $a_j$ be the $j$-th column of $A^T$ ($j$-th row of $A$) and $d_j$ be the $j$-th column of $\sum_iC^{-1}b_ix_i^TC$, thus $a_j$ can be computed by solving $$\sum_ix_ix_i^Ta_j=d_j$$

• OK thats helpful, thanks. Sep 19, 2012 at 23:11

If you're really interested in the $L^1$ norm, then this is computationally nontrivial. Luckily there have been many recent advances in the last 10 years. Look at the key 2005 paper by Nesterov, Smooth minimization of nonsmooth functions.

Another competitive method is Bregman $L^1$ optimization, but I don't know very much about it.

• This is useful but I did intend the L2 norm, which is consistent with the second matrix equation. Sep 18, 2012 at 2:08