Let $\{x_i\}_{i = 1}^n$ be $n$ vectors of $d$ dimesnions.
We stack each $x_i$ as a row vector to form a matrix $X$ of dimension $\mathbb{R}^{n\times d}$
Let $\{y_i\}_{i = 1}^n$ be scalars (say all are $1$) and these are stacked to form a matrix $Y$ of dimension $\mathbb{R}^{n\times 1}$
We compute the following inner product
$$Y^TX(X^TX+ \lambda I)^{-2}X^TY$$
where $\lambda \gt 0$.
Can we show that this seems that does not grow at an order of $n$.
Experimantally it appears so
For $d = 3$ and $n$ running from $1$ to $1000$ we have
For $d = 10$ we have
and for $d=100$ we have
So it seems that for $n$ much greater than $d$ it seems that the hunch is correct.
Any idea on how to proceed.
Thanks
EDIT 1: Here is a proof that $$Y^TX(X^TX+ \lambda I)^{-1}X^TY$$ is $O(n)$
Let $X = U\Sigma V^T$ Then $$Y^TX(X^TX+ \lambda I)^{-1}X^TY = Y^T U \Sigma (\Sigma^T\Sigma + \lambda I)^{-1}\Sigma^T U^TY$$. Now we can note that diagonal elements of $\Sigma (\Sigma^T\Sigma + \lambda I)^{-1}\Sigma^T$ is less than 1. Therefore $$Y^T U \Sigma (\Sigma^T\Sigma + \lambda I)^{-1}\Sigma^T U^TY \leq Y^T UU^T Y$$ which is less than $n\|Y\|^2_\infty$
My hunch is that $Y^TX(X^TX+ \lambda I)^{-2}X^TY$ will be less than $d\|Y\|^2_\infty$. This is easy if $X^T X$ is diagonal. But is it true for general.
EDIT 2: This is another line of thought I was having, $$Y^TX(X^TX+ \lambda I)^{-2}X^TY \leq n\|Y\|^2_\infty tr(XX^T) tr ((X^TX)^{-2})$$ Now $tr(XX^T) = O(n)$. If I can say $tr ((X^TX + \lambda I)^{-2})$ is $O(n^{-2})$ Then I can be done. But is this true?
EDIT 3: So this is a line of thought from the previous update Let $\lambda_1,...\lambda_d$ be the eigenvalues of $X^TX + \lambda I$. Then the eigen values of $(X^TX + \lambda I)^{-2}$ are $\frac{1}{\lambda_1^2},...\frac{1}{\lambda_d^2}$. So we we have the following, $$\lambda_1 + \cdots + \lambda_d = O(n)$$,$\lambda_1,...\lambda_d$ are strictly positive. So we can have $$\lambda_1^2 + \cdots + \lambda_d^2 = O(n^2)$$.
Can we write from this step $$\frac{1}{\lambda_1^2}+ \cdots +\frac{1}{\lambda_d^2} = O(1/n^2)$$?
EDIT 4: I can show that $$\frac{1}{\lambda_1^2}+ \cdots +\frac{1}{\lambda_d^2} = \Omega(1/n^2)$$
$$\frac{1}{\lambda_1^2}+ \cdots +\frac{1}{\lambda_d^2} \geq \frac{d^2}{\lambda_1^2 + \cdots + \lambda_d^2}$$ by AM-HM inequality which is $\Omega(1/n^2)$.
So we have $trace((X^TX + \lambda I)^{-2})$ of the order $\Omega(1/n^2)$. Therefore $$Y^TX(X^TX+ \lambda I)^{-2}X^TY = O(n^2)\Omega(1/n^2)$$
Are my calculations correct? Can we have anything from here?