Looking for tighter bound on symmetric PSD matrices products

[Yossi]

Homework Statement

Let K and L be symmetric PSD matrices of size N*N, with all entries in [0,1]. Let i be any number in 1...N and K’, L’ be two new symmetric PSD matrices, each with only row i and column i different from K and L. I would like to obtain an upper bound of the equation below: where .∗ is an element-wise multiply.

Homework Equations

|[sum(K' .∗ L') − sum(K .∗ L)] − (2/N)*[sum(K'L'') − sum(KL)] + (1/N*N)*[sum(K')sum(L') − sum(K)sum(L)]|

See attached for equation in LaTex/PDF.

The Attempt at a Solution

Using simple triangular inequality and bounding the three square brackets respectively,
I can bound the above with 12N − 13.
However, this is extremely loose.
Empirical experiments show that the constant coefficient should be much lower, probably closer to 1N.

Can you suggest any linear algebra properties connecting the equation's parts - which may help me get a tighter bound?

 

[Ray Vickson]

Homework Statement

Let K and L be symmetric PSD matrices of size N*N, with all entries in [0,1]. Let i be any number in 1...N and K’, L’ be two new symmetric PSD matrices, each with only row i and column i different from K and L. I would like to obtain an upper bound of the equation below: where .∗ is an element-wise multiply.

Homework Equations

|[sum(K' .∗ L') − sum(K .∗ L)] − (2/N)*[sum(K'L'') − sum(KL)] + (1/N*N)*[sum(K')sum(L') − sum(K)sum(L)]|

See attached for equation in LaTex/PDF.

The Attempt at a Solution

Using simple triangular inequality and bounding the three square brackets respectively,
I can bound the above with 12N − 13.
However, this is extremely loose.
Empirical experiments show that the constant coefficient should be much lower, probably closer to 1N.

Can you suggest any linear algebra properties connecting the equation's parts - which may help me get a tighter bound?

Does $\sum(A)$ mean $\sum_i \sum_j a_{ij}$ for matrix $A = (a_{ij})$? When you say that each of $K', L'$have only row $i$ and column $i$ different from $K,L$, do you mean that $K'$ has both its row and column $i$ different from $K$ and that $L'$ has both its row and its column $i$ different from $L$? I think that is what you mean, but it is worth checking. Are all the elements of $K', L'$ also in $[0,1]$?