0

Let $\mathbf{D}$ be a diagonal matrix of size $n\times n$ defined over a field $\mathbb{R}$, and $\mathbf{X}$ be a matrix of $n \times n$ for which $\text{rank}(\mathbf{X}) = 1$.

Let $$F_\mathbf{D}(\mathbf{X}) = \sum_{i = 1}^{ n}\sum_{j = 1}^{ n}(d_{ij} -x_{ij})^2$$ Find $\min{F_\mathbf{D}(\mathbf{X})}$ for an arbitrary diagonal matrix $\mathbf{D}$.

Attempt

By Eckart–Young–Mirsky theorem, the best low-rank approximation in terms of Frobenius' norm can be obtained by a singular value decomposition (as if $F_\mathbf{D}{(\mathbf{X} )}$ is in fact a Frobenius' norm $\mid \mathbf{D}-\mathbf{X} \mid$). SVD of a diagonal matrix is the same matrix with its entries sorted in descending order, which is multiplied by permutation matrices.

If this is the case, then the best rank-one approximation is simply the matrix where all the elements except for the largest one are zeroed out. Hence, $\text{min}\space F$ is a sum of squares of $n - 1$ smallest diagonal entries.

  1. Is this correct?

  2. Is there a proof that does not rely on SVD? This concept is outside the scope of the exam program.

Inter Veridium
  • 299
  • Yes you're right; just keep in mind that the entry that we do not zero out is the largest in magnitude. As for an alternative approach, I'm not sure. Are there any theorems that we can use from the program that might be applicable here? – Ben Grossmann May 15 '20 at 01:46
  • We could prove the EYM theorem (and hence this result) using the Weyl inequalities, for instance – Ben Grossmann May 15 '20 at 01:47
  • Maybe there's a way to take advantage of the fact that we're only talking about rank-1 matrices – Ben Grossmann May 15 '20 at 01:55
  • @Omnomnomnom Yes, about in magnitude -- I forgot to mention it. I suppose the answer will still be accepted despite the theorem not being mentioned in the programme, so any of the proposed methods would be fine. – Inter Veridium May 15 '20 at 02:35

1 Answers1

1

Sketch of Proof: For any unit vector $\mathbf u$, we can consider the rank-1 matrices $\mathbf X$ whose column space is spanned by $\mathbf u$. Verify that among these matrices, the matrix that minimizes $F_{\mathbf D}(\mathbf X)$ is $\mathbf u \mathbf u ^T\mathbf D$ (you might want to make use of the fact that the projection $\mathbf u \mathbf u^T \mathbf x$ minimizes $\|\mathbf u - \mathbf x\|^2$). Now, to find the rank-1 matrix $\mathbf X$ that minimizes $F_{\mathbf D}(\mathbf X)$, it suffices to compute $$ \min_{\|\mathbf u\| = 1} F_{\mathbf D}(\mathbf u \mathbf u^T\mathbf D) = \|\mathbf D\|_F^2 - \mathbf u^T \mathbf D^2 \mathbf u. $$ That is, we must maximize $\mathbf u^T \mathbf D^2 \mathbf u$. Verify that if $j = \arg \max_{i} |d_i|$, then this maximum is attained with $\mathbf u = \mathbf e_j$, the $j$th standard basis vector (i.e. the $j$th column of the identity matrix).

Ben Grossmann
  • 225,327