Meaningful upper bound on $\sum_{i=1}^n v_i^T \Big(\sum_{i=1}^n v_i v_i^T\Big)^{-1} v_i$

73 Views Asked by At

Let $v_1, \dots, v_n \in \mathbb{R}^d$ and $n \ge d$. Assume that the matrix $A$ is invertible. $$ A = \sum_{i=1}^n v_i v_i^T $$

Is it possible to simplify the expression $$\sum_{i=1}^n v_i^T A^{-1} v_i?$$

Or obtain a simple upper bound in terms of $v_i$'s.

For the case when $d=1$ it is straightforward to see that the expression simplifies and is always equal to $1$. I wonder what tricks there are in understanding the behavior of this function.

1

There are 1 best solutions below

1
On BEST ANSWER

$$\sum_{j=1}^n v_j^T A^{-1} v_j = \sum_{j=1}^n ⟨ A^{-1}∣ v_jv_j^T⟩ = ⟨ A^{-1}∣ \sum_{j=1}^n v_jv_j^T⟩ = ⟨ A^{-1}∣ A ⟩ $$

And we can apply Cauchy-Schwartz

$$|⟨ A^{-1}∣ A ⟩| ≤ ‖A^{-1}‖⋅‖A‖ = κ(A)$$

However, since $A$ is symmetric by definition, we even have

$$⟨ A^{-1}∣ A ⟩ = ⟨ A^⊤ A^{-1}∣ _d⟩ = ⟨ A A^{-1}∣ _d⟩ = ⟨ _d ∣ _d⟩ = d$$