# Homework Help: Looking for tighter bound on symmetric PSD matrices products

Tags:
1. Sep 20, 2015

### Yossi

1. The problem statement, all variables and given/known data
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.

2. Relevant 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.

3. 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?

#### Attached Files:

• ###### Sym_PSD_matrices.pdf
File size:
55.8 KB
Views:
80
2. Sep 25, 2015

### Greg Bernhardt

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