7
$\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$
2
  • 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 '14 at 12:45
  • $\begingroup$ Thanks @AlgebraicPavel! May you please elaborate on this? Edit: Ok, now I see the answer of @JackD'Aurizio below... Thanks anyway! $\endgroup$ – nullgeppetto Sep 26 '14 at 12:47
6
$\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 '14 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 '14 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 '15 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 '15 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 '15 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 '16 at 11:18
  • $\begingroup$ Yes, the error is $\|A-B\|_F$ for any of these approximations. $\endgroup$ – john316 Mar 31 '16 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 '16 at 13:07
  • 1
    $\begingroup$ Divide the error by $\|A\|_F$, to get the relative error of the approximation. $\endgroup$ – john316 Apr 2 '16 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.