# Why does this optimization problem have a closed form solution that resembles least squares so much?

Consider the following optimization problem

$$\min_{\mathbf{Q}} \sum\limits_{i=1}^{n}{\|{{\mathbf{b}}_{i}}-{{\mathbf{Q}}^{T}}{{\mathbf{x}}_{i}}\|^2}+\lambda \|\mathbf{Q}\|^{2}$$

where $\mathbf{b_i}$ is an $r$-dimensional vector, $\mathbf{Q}$ is an $n \times r$ matrix and $\mathbf{x_i}$ is an $n$-dimensional vector. The closed form solution is

$$\mathbf{Q}={{(\mathbf{S}{{\mathbf{S}}^{T}}+\lambda \mathbf{I})}^{-1}}\mathbf{S}{{\mathbf{B}}^{T}}$$

Why does it resemble the least squares solution so much? How to conduct that?

• You can do vectorization on $\bf Q$ and represent multiplication from the right as well as transposition as matrix operations if you take a look at en.wikipedia.org/wiki/Kronecker_product under "Matrix Equations" Commented Aug 3, 2016 at 9:30
• I only know basic linear algebra and a few advanced linear algebra like SVD. Therefore I find it really hard to understand your answer, could you please give more specific suggestions?
– Long
Commented Aug 3, 2016 at 9:56
• You are missing a square on the norm in the sum (otherwise the statement is false) Commented Aug 3, 2016 at 11:21

Given $\mathrm A \in \mathbb R^{m \times n}$ and $\mathrm B \in \mathbb R^{m \times p}$, we form a matrix equation in $\mathrm X \in \mathbb R^{n \times p}$

$$\mathrm A \mathrm X = \mathrm B$$

If we want to find the least-squares solution, then we minimize $\| \mathrm A \mathrm X - \mathrm B \|_F$. However, if we do not want the norm of $\mathrm X$ to become too large, then we minimize the following objective function

$$\begin{array}{rl} \| \mathrm A \mathrm X - \mathrm B \|_F^2 + \lambda \|\mathrm X\|_F^2 &= \mbox{tr} ((\mathrm A \mathrm X - \mathrm B)^T (\mathrm A \mathrm X - \mathrm B)) + \lambda \,\mbox{tr} (\mathrm X^T \mathrm X)\\ &= \mbox{tr} (\mathrm X^T (\mathrm A^T \mathrm A + \lambda \mathrm I_n) \mathrm X - \mathrm B^T \mathrm A \mathrm X - \mathrm X^T \mathrm A^T \mathrm B + \mathrm B^T \mathrm B)\end{array}$$

where $\lambda > 0$. Differentiating with respect to $\mathrm X$, we obtain

$$2 (\mathrm A^T \mathrm A + \lambda \mathrm I_n) \mathrm X - 2 \mathrm A^T \mathrm B$$

Finding where the derivative vanishes, we obtain the matrix equation

$$(\mathrm A^T \mathrm A + \lambda \mathrm I_n) \mathrm X = \mathrm A^T \mathrm B$$

If $\lambda > 0$, then $\mathrm A^T \mathrm A + \lambda \mathrm I_n$ is always invertible. Hence, the unique minimizer is

$$\hat{\mathrm X} := (\mathrm A^T \mathrm A + \lambda \mathrm I_n)^{-1} \mathrm A^T \mathrm B$$

• To find the derivative of the trace with respect to a matrix, take a look at section 2.5 of The Matrix Cookbook: math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf Commented Aug 3, 2016 at 13:03
• I have this cookbook, was it important to know how to infer this? or is it enough to just make use of it ?
– Long
Commented Aug 3, 2016 at 13:49
• @Long Didn't you ask for a derivation? Commented Aug 3, 2016 at 14:15

First for convenience you could just stuff the ${\bf x}_i$ as columns into a $\bf X$ matrix and for ${\bf b}_i$ into ${\bf B}$ your objective function will become:

$$\min_{\bf Q}\|{{\bf B - Q}^T\bf X}\| + \lambda\|{\bf Q}\|$$

Where the norm is taken as the Frobenius-norm which is equivalent to least squares norm for matrices. Now we can start with the vectorization. If we take a look at the matrix equations (replacing ${\bf X}$ for ${\bf Y}$ to avoid confusion), we see the following

$${\bf AYB = C} \Leftrightarrow ({\bf B}^T {\bf \otimes A}) \, \mbox{vec} ({\bf Y}) = \mbox{vec} ({\bf C})$$

Now how can we substitute $\bf Q$ and $\bf X$ to for $\bf A,Y,B$ to get something we can use? Well we want to solve for $\bf Q$, so it should go into $\bf Y$. The $\bf X$ multiplication is from the right so it should be $\bf B$ and what remains is $\bf A$ from the left which must then be an identity matrix.

Now we need to express transposition of $\bf Q$ as a matrix multiplication - or we could change the definition of $\bf Q$ and just take the transpose after having solved it. Whatever is most convenient for us.

• I can almost fully understand what your words. However the answer so far was still not so convent for me. Sorry but I have very little matrix calculus experience. where can i find some problem set with solutions? I'd like to practice it.
– Long
Commented Aug 3, 2016 at 12:11
• Yes I should probably derive the minimization step all in all including differentiation and equalling zero, but Rodrigo seems to already have done a splendid job at that. Commented Aug 3, 2016 at 15:06