9
$\begingroup$

The following question is similar to this one, but I think that it is not straightforward to move from one to the other, so please take a look. Otherwise, please let me know and I will delete it.

Let $A,B\in\Bbb{R}^{n\times n}$ two square real $n\times n$ matrices with the additional properties that $A$ is also symmetric, and $B$ is diagonal with entries $\{b_i\colon b_i\in\Bbb{R}, i=1,\ldots,n\}$, that is, $B=\operatorname{diag}(b_1,\ldots,b_n)$.

We want to minimize the Frobenius norm of the difference of $A$, $B$ with respect to the matrix $B$. Let $B^{\star}$ denote the minimizer of the aforementioned norm, that is $$ B^{\star} = \underset{B} {\mathrm{argmin}} \left\| A- B \right\|_F, $$ where $\lVert A\rVert_F$ denotes the Frobenius norm of an $n\times n$ real symmetric matrix $A=\big(a_{ij}\big)_{i,j=1}^n$, and is given by $$ \lVert A\rVert_F = \left(\sum_{i,j=1}^n \left\| a_{ij} \right\|^2\right)^{\frac{1}{2}} = \sqrt{\operatorname{tr}(A^\top A)} = \sqrt{\operatorname{tr}(AA^\top)}. $$

$\endgroup$
1
  • 2
    $\begingroup$ $B^*$ is given by the diagonal part of $A$, which zeroes out the contributions from diagonals to the Frobenius norm. $\endgroup$
    – Algebraic Pavel
    Sep 26, 2014 at 12:45

2 Answers 2

Reset to default
8
$\begingroup$

Since $$\|A-B\|_F^2 = 2\sum_{i>j}|a_{ij}|^2 + \sum_{i=1}^{n}|a_{ii}-b_{ii}|^2 $$ it follows that the minimum is attained when $b_{ii}=a_{ii}$ for any $i\in[1,n]$.

$\endgroup$
4
  • 1
    $\begingroup$ Thanks a lot! I didn't find out it was that clear! $\endgroup$
    – nullgeppetto
    Sep 26, 2014 at 12:52
  • $\begingroup$ Actually, (first, sorry for coming back, even though I wrote the above comment), but could you elaborate more on this? May you give some explanation why you wrote this relation above (does it hold because of the diagonality of $B$ or does it hold in general)? Moreover, what if $B=bI_n$? How could your form fit this case? Thanks a lot again! $\endgroup$
    – nullgeppetto
    Sep 27, 2014 at 12:16
  • 1
    $\begingroup$ @nullgeppetto Picture the graph of a function $d_A(i)$, where this is the $i^{th}$ element on the diagonal of $A$. Since your $B$ is diagonal, no matter how it changes, it won't affect the off diagonal elements. Since the Frobenius norm squares and then sums each element, you want $B$ to modify the diagonal of $A$ so they contribute as little as possible. When $B$ was any diagonal matrix, taking $d_B(i):=d_A(i)$ gave $d_A(i)-d_B(i)=0$, so they contributed nothing. When $d_B(i)=b$, $d_A(i)-d_B(i)$ will slide the diagonal elements of $A$ up and down equally. $\endgroup$
    – Travis Bemrose
    Dec 3, 2015 at 4:26
  • 1
    $\begingroup$ @nullgeppetto Those diagonal elements will contribute the smallest square sum when their average is 0 (when they are "on average" as close to zero as they can get). Thus taking $b = \mathop{avg}\limits_{i} \{d_A(i)\}$, so that $B$ subtracts off the average of the diagonal of $A$, will minimize this case. $\endgroup$
    – Travis Bemrose
    Dec 3, 2015 at 4:30
5
$\begingroup$

You can write the objective function in terms of the Frobenius product, then it is a simple matter to find its differential and gradient $$\eqalign{ f &= (B-A):(B-A) \cr df &= 2(B-A):d(B-A) \cr &= 2(B-A):dB \cr \frac{\partial f}{\partial B} &= 2(B-A) \cr }$$ Note that the above gradient is for the general case, with no constraints on $B$.

The diagonal constraint can be enforced by Hadamard multiplication with the identity matrix $$\eqalign{ \frac{\partial f}{\partial B} &= 2I\circ(B-A) \cr &= 2\,(B - I\circ A) \cr }$$ Setting the constrained gradient to zero and solving for $B$ yields $$\eqalign{ B &= I\circ A \cr }$$ To address the question in your comment, where $B$ is constrained to be a scalar multiple of the identity, we have $$\eqalign{ B &= bI \cr dB &= I\,db \cr }$$

Substitute these into the unconstrained differential expression $$\eqalign{ df &= 2(B-A):dB \cr &= 2(bI-A):I\,db \cr &= 2\,\big(b\,{\rm tr}(I)-{\rm tr}(A)\big)\,db \cr \frac{\partial f}{\partial b} &= 2\,(bn-{\rm tr}(A)) \cr }$$ Setting this gradient to zero and solving for the scalar $b$ yields $$\eqalign{ b &= \frac{{\rm tr}(A)}{n} \cr }$$

$\endgroup$
5
  • $\begingroup$ This is VERY nice, but I must admit I have no idea how you did it. I see what you're doing, but not how. In your very second line, how do you differentiate the Frobenius inner product without first converting it to some other notation and then trying to figure out how to convert back? $\endgroup$
    – Travis Bemrose
    Dec 4, 2015 at 15:52
  • $\begingroup$ Thank you very much for your answer. May I ask you another question? What is the error of such approximation? Just the $\|A-bI_n\|_F$? $\endgroup$
    – nullgeppetto
    Mar 31, 2016 at 11:18
  • $\begingroup$ Yes, the error is $\|A-B\|_F$ for any of these approximations. $\endgroup$
    – john316
    Mar 31, 2016 at 19:19
  • $\begingroup$ Thank you very much. Just a final question, if you may. Let's say we have two different such approximations, for two matrices in different spaces (let's say the first is $n\times n$ and the second is $m\times m$). How could we "normalize" the errors such that they are comparable; in the sense that we may say that the first approximation is "better" than the second? Actually, is such a comparison possible? Does it make any difference if $n\gg m$, for instance? I tried to divide by the $\sqrt{n}$ and $\sqrt{m}$, respectively. Is this right? Thanks again for your time. $\endgroup$
    – nullgeppetto
    Apr 1, 2016 at 13:07
  • 1
    $\begingroup$ Divide the error by $\|A\|_F$, to get the relative error of the approximation. $\endgroup$
    – john316
    Apr 2, 2016 at 3:16

You must log in to answer this question.

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