7
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ May 27, 2014 at 10:57
  • $\begingroup$ I've added a few lines to my answer. Hopefully they will clarify it. $\endgroup$
    – JPi
    May 27, 2014 at 12:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .