# Is the Frobenius norm minimizer the same as the $2$-norm minimizer?

Given matrices $$A \in \mathbb{R}^{n \times m}$$ and $$B \in \mathbb{R}^{n \times k}$$, consider the least-squares minimizer

$$\arg \min_{X \in \mathbb{R}^{m \times k}} \| AX - B \|_{\text{F}}$$

where $$\| M \|_{\text{F}} := \left( \sum_i \sum_j M_{ij}^2 \right)^{1/2}$$ denotes the Frobenius norm. I was wondering if this is identical to the minimizer

$$\arg \min_{X \in \mathbb{R}^{m \times k}} \| AX - B \|_2$$

where $$\| M \|_2 := \sigma_1 (M)$$ denotes the matrix $$2$$-norm. Since

$$\sqrt{\operatorname{rank}(M)} \cdot \| M \|_2 \geq \| M \|_F \geq \| M \|_2$$

I feel there must be a simple argument to show these minimizers are identical. If it is not so, can you please describe what assumptions on matrices $$A$$ and $$B$$ are necessary for the minimizers to be identical?

Good question. Yes there is a simple argument. Let $P_A$ denote the orthogonal projection matrix $A(A'A)^{-1}A'$ and $M_A=I-P_A$. Then

$$(AX-B)'(AX-B) - B'M_AB = (AX-B)'P_A(AX-B) \succeq 0,$$

where $\succeq 0$ means that the left hand side is positive semidefinite. Hence $X=(A'A)^{-1}A'B$ is the minimizer for both norms.

I'm using the minor simplifying assumptions that $A'A$ is invertible. Should that fail then you can achieve the same result using Moore Penrose inverses.

In response to comment:

If $Y-Z$ is positive semidefinite then $v'(Y-Z)v\geq 0$ for all vectors $v$. So if $v$ is an eigenvector of $Z$ normalized to length one and corresponding to an eigenvalue $\lambda$ then $v'Yv\geq v'Zv=\lambda$. Since this is true for all eigenvectors of $Z$, both the largest eigenvalue of $Z$ and the sum of $Z$'s eigenvalues are less than the corresponding quantities of $Y$.

• I somewhat can't see the point of this answer. Do you mean that $\|P_AR\|^2+\|(I-P_A)R\|^2=\|R\|^2$ is true for both the Frobenius norm and the 2-norm? May 27, 2014 at 10:57
• I've added a few lines to my answer. Hopefully they will clarify it.
– JPi
May 27, 2014 at 12:30