Lower bounding $v^TA^{\dagger}v$ where A is a sum of rank-1 matrices

Question

This is related to a previous question I asked (Upper bounding $v^TAv$ where $A$ is the inverse of a sum of rank-$1$ matrices and $v$ is a vector). Let $(x_i)_{1 \leq i \leq n}$ be vectors of $\mathbb{R}^d$ such that at least one of them is not the zero vector. Let $A=\sum_{i}x_ix_i^T$ and $v \in \operatorname{Im}(A)$ .

In the previous post, I show that when $A$ is invertible, a lower bound of $v^TA^{-1}v$ can be found by noticing that $A \preceq \left(\sum_{i} x_i^Tx_i\right)I_d$, which yields $A^{-1} \succeq \left(\sum_{i} x_i^Tx_i\right)^{-1}I_d$ and $$v^TA^{-1}v \geq \left(\sum_{i} x_i^Tx_i\right)^{-1}v^Tv.$$

I would like to generalize this result to the case where $A$ is not necessarily invertible (replacing the true inverse by the pseudo-inverse). I understand this won't be true for every vector $v$ because of this negative result (Is it true that $A\geq B$ implies $B^{\dagger}\geq A^{\dagger}$ for singular positive semi-definite matrices?), but I wonder if my additional assumption $v \in \operatorname{Im}(A)$ is enough to make it work.

Answer 1

Since $v \in \operatorname{Im}(A)$, there exists $y \in \mathbb{R}^d$ such that $v=Ay$. We have $v^TA^{\dagger}v=y^TAA^{\dagger}Ay=y^TAy.$ Let $\lambda_1 \geq \dots \lambda_d \geq 0$ be the eigenvalues of $A$. Since $A$ is symmetric, there is an orthonormal basis $\left(e_1,\dots,e_d\right)$ of eigenvectors of $A$, and we can write $y=\sum_{i=1}^{d} \alpha_ie_i.$

Then, $v=Ay=\sum_{i=1}^d \alpha_i\lambda_ie_i$ which gives $y^TAy=\sum_{i=1}^d \alpha_i^2 \lambda_i$ and $v^Tv=\sum_{i=1}^d \alpha_i^2\lambda_i^2$. Furthermore, $v^Tv=\sum_{i=1}^d \alpha_i^2\lambda_i^2 \leq \sum_{i=1}^d \alpha_i^2\lambda_i\lambda_1=\lambda_1y^TAy$ and we finally get $$v^TA^{\dagger}v \geq \lambda_1^{-1}v^Tv \geq Tr(A)^{-1}v^Tv = \left(\sum_{i=1}^n x_i^Tx_i\right)^{-1}v^Tv.$$