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]##?